مبانی کامپیوتر و الگوریتم؛ از حل مسئله تا پروژهٔ عملی

وقتی مسئلهٔ برنامه بزرگ می‌شود، نوشتن یک زنجیرهٔ بلند از دستورها دیگر کافی نیست. فرض کنید گزارشی آموزشی باید کسرها را ساده کند و شماره‌های اول را تشخیص دهد. این دو خواسته هر دو با عدد سروکار دارند، اما ورودی، خروجی و روش حل یکسانی ندارند. آن‌ها را به دو تابع با مسئولیت روشن تقسیم می‌کنیم. هدف این درس حفظ‌کردن دو فرمول نیست؛ می‌خواهیم یاد بگیریم چگونه یک مسئله را به جزءهایی بشکنیم که بتوان جدا توضیح داد، اجرا کرد و آزمود.

قرارداد تابع؛ قبل از بدنه چه چیزی را مشخص کنیم؟

قرارداد یعنی روشن کنیم تابع چه ورودی‌هایی می‌پذیرد، چه نتیجه‌ای برمی‌گرداند و در حالت نامعتبر چه می‌کند. برای تابع gcd، ورودی دو عدد صحیح امن و نامنفی است؛ دست‌کم یکی باید غیرصفر باشد. خروجی بزرگ‌ترین مقسوم‌علیه مشترک مثبت است. در قرارداد این درس جفت صفر و صفر رد می‌شود، چون هر عدد مثبت، مقسوم‌علیه هر دو است و بزرگ‌ترین عددی وجود ندارد. بعضی کتابخانه‌ها بنا بر قرارداد مقدار صفر می‌دهند؛ این تفاوت باید صریح باشد، نه تصادفی.

تابع خالص در این مثال‌ها، با ورودی یکسان نتیجهٔ یکسان می‌دهد و وضعیت بیرون را تغییر نمی‌دهد. نام gcd بیانگر محاسبه است؛ قرار نیست هم‌زمان فرم بسازد یا فایلی ذخیره کند. آرگومان، مقدار واقعی هنگام فراخوانی است و پارامتر نامی است که در تعریف می‌خوانیم. اگر این واژه‌ها تازه‌اند، #function و #return را مرور کنید. جداسازی محاسبه از چاپ باعث می‌شود همان جواب در صفحهٔ وب، آزمون یا برنامهٔ خط فرمان قابل استفاده باشد.

اقلیدس؛ از بررسی همهٔ مقسوم‌علیه‌ها به باقی‌مانده

برای ۴۸ و۱۸ می‌توان همهٔ عددهای کوچک‌تر را امتحان کرد، اما اقلیدس مسئله را کوتاه‌تر می‌کند: مجموعهٔ مقسوم‌علیه‌های مشترک a و b، با مجموعهٔ مقسوم‌علیه‌های مشترک b و باقی‌ماندهٔ تقسیم a بر b یکسان است. دلیل را از رابطهٔ a=q×b+r ببینید. هر عددی که a و b را تقسیم کند، r=a−q×b را هم تقسیم می‌کند؛ عکس این استدلال نیز برقرار است. پس می‌توان جفت ورودی را عوض کرد، بدون اینکه پاسخ مسئله عوض شود.

gcd(a, b):
    اگر ورودی خارج از قرارداد بود: خطا
    تا زمانی که b ≠ 0:
        r ← باقی‌ماندهٔ a بر b
        a ← b
        b ← r
    برگردان a

جفت (۴۸،۱۸) ابتدا به (۱۸،۱۲) می‌رسد، چون باقی‌ماندهٔ ۴۸ بر۱۸ برابر۱۲ است. سپس جفت (۱۲،۶) و بعد (۶،۰) داریم. در این نقطه پاسخ۶ است. محاسبهٔ r باید قبل از تغییر a و b انجام شود؛ اگر زودتر a را برابرb بگذارید، ورودی لازم برای باقی‌مانده را از دست می‌دهید. این همان اهمیت متغیر موقت در ردگیری درس سوم است. جدول زیر وضعیت ابتدای هر بررسی حلقه را نشان می‌دهد؛ سطر آخر دیگر بدنه را اجرا نمی‌کند.

گام      a      b      r در صورت اجرای بدنه
۰        48     18     12
۱        18     12     6
۲        12     6      0
۳        6      0      پایان؛ خروجی 6

در فایل 07-gcd.mjs، نمونهٔ زیر را ذخیره کنید و با node 07-gcd.mjs اجرا کنید. assert شرط مورد انتظار را می‌سنجد و هنگام شکست خطا می‌دهد. برنامه علاوه بر حالت معمول، صفر، جابه‌جایی ورودی‌ها و چند ورودی نامعتبر را بررسی می‌کند. این آزمون‌ها درستی همهٔ ورودی‌ها را اثبات نمی‌کنند؛ استدلال حفظ پاسخ و کاهش باقی‌مانده، بخش دیگری از توضیح درستی است. مقدار متنی «۴۸» نیز بدون تبدیل بی‌اعلام پذیرفته نمی‌شود.

import assert from 'node:assert/strict';
function gcd(a, b) {
  if (!Number.isSafeInteger(a) || !Number.isSafeInteger(b) || a < 0 || b < 0) {
    throw new RangeError('Expected nonnegative safe integers');
  }
  if (a === 0 && b === 0) throw new RangeError('gcd(0, 0) is outside this contract');
  while (b !== 0) {
    const remainder = a % b;
    a = b;
    b = remainder;
  }
  return a;
}
assert.equal(gcd(48, 18), 6);
assert.equal(gcd(18, 48), 6);
assert.equal(gcd(0, 18), 18);
assert.equal(gcd(18, 0), 18);
assert.equal(gcd(17, 13), 1);
assert.equal(gcd(7, 7), 7);
assert.throws(() => gcd(0, 0), RangeError);
assert.throws(() => gcd(-4, 2), RangeError);
assert.throws(() => gcd('48', 18), RangeError);
assert.throws(() => gcd(2.5, 5), RangeError);
assert.throws(() => gcd(Number.MAX_SAFE_INTEGER + 1, 2), RangeError);
assert.throws(() => gcd(NaN, 2), RangeError);
console.log(`gcd(48, 18) = ${gcd(48, 18)}`);

خروجی نمایشی برنامه gcd(48, 18) = 6 است. تغییر پارامترهای عددی داخل تابع، متغیرهای عددی فراخواننده را تغییر نمی‌دهد. اگر gcd(0,18) را صدا بزنید، نخستین باقی‌مانده صفر می‌شود و۱۸ برمی‌گردد؛ gcd(18,0) اصلاً وارد حلقه نمی‌شود. همین دو مورد، ارزش نوشتن شرط خاتمه را نشان می‌دهند. اگر کد برای ورودی مثبت کار می‌کند ولی صفر را اشتباه پاسخ می‌دهد، یک شرط اضافی تصادفی نگذارید؛ ابتدا ببینید قرارداد و ترتیب دستورها چه می‌گویند.

عدد اول؛ تعریف را به آزمون قابل اجرا تبدیل کنیم

عدد اول، عدد صحیح بزرگ‌تر از یک است که جز یک و خودش مقسوم‌علیه مثبت دیگری ندارد. بنابراین یک، صفر و عددهای منفی در این تعریف اول نیستند. تابع این درس عدد صحیح بین صفر و یک میلیارد می‌پذیرد؛ صفر ویک نتیجهٔ false می‌دهند و ورودی منفی یا خارج از سقف، خطای قرارداد است. سقف یک میلیارد انتخاب تمرین برای محدودکردن کار است و تعریف ریاضی عدد اول را عوض نمی‌کند. ورودی بسیار بزرگ، الگوریتم مناسب‌تری می‌خواهد.

چرا تا خود n همهٔ مقسوم‌علیه‌ها را بررسی نکنیم؟ اگر n حاصل ضرب دو عدد مثبت غیرواحد باشد، نمی‌توان هر دو عامل را بزرگ‌تر از ریشهٔ n داشت، چون حاصل ضربشان از n بزرگ‌تر می‌شود. پس برای عدد مرکب، دست‌کم یک عامل تا ریشه وجود دارد. شرط d <= n/d همین مرز را بدون محاسبهٔ d×d بیان می‌کند. در محدودهٔ کوچک این تمرین، هر دو شکل قابل محاسبه‌اند، اما شکل تقسیم، وابستگی غیرضروری به مربع‌کردن عدد را حذف می‌کند.

isPrime(n):
    اگر n خارج از قرارداد بود: خطا
    اگر n < 2: برگردان نادرست
    d ← 2
    تا زمانی که d <= n / d:
        اگر باقی‌ماندهٔ n بر d صفر است: برگردان نادرست
        d ← d + 1
    برگردان درست

برای۱۷، مقسوم‌علیه‌های۲،۳ و۴ بررسی می‌شوند و هیچ‌کدام باقی‌ماندهٔ صفر ندارند؛ سپس حلقه پایان می‌یابد. برای۴۹، باید۷ هم بررسی شود؛ به همین دلیل مرز شرط شامل برابری است. برای۲، شرط ورود به حلقه از ابتدا نادرست است، اما این به معنی شکست نیست: هیچ مقسوم‌علیه غیرواحدی برای امتحان باقی نمانده و تابع true می‌دهد. برداشت «حلقه اجرا نشد، پس برنامه خراب است» اغلب از روشن‌نبودن قرارداد ناشی می‌شود.

import assert from 'node:assert/strict';
function isPrime(n) {
  if (!Number.isSafeInteger(n) || n < 0 || n > 1_000_000_000) {
    throw new RangeError('Expected an integer from 0 to 1000000000');
  }
  if (n < 2) return false;
  for (let d = 2; d <= n / d; d += 1) {
    if (n % d === 0) return false;
  }
  return true;
}
for (const n of [2, 3, 17, 97, 997]) assert.equal(isPrime(n), true);
for (const n of [0, 1, 4, 9, 25, 49, 100, 1_000_000_000]) {
  assert.equal(isPrime(n), false);
}
for (const n of [-1, 2.5, '17', NaN, 1_000_000_001]) {
  assert.throws(() => isPrime(n), RangeError);
}
console.log(`17: ${isPrime(17)}, 49: ${isPrime(49)}, 1: ${isPrime(1)}`);

فایل 07-prime.mjs در پایان، 17: true, 49: false, 1: false چاپ می‌کند. آزمون چند مربعِ عدد اول، خطای مرز را شکار می‌کند. خروج زودهنگام پس از یافتن یک مقسوم‌علیه کافی است؛ برای اعلام مرکب‌بودن، لازم نیست همهٔ عامل‌ها پیدا شوند. اما برای اعلام اول‌بودن، باید همهٔ گزینه‌های لازم رد شده باشند. این تفاوت میان «یک شاهد برای رد» و «پایان کامل بررسی برای پذیرش»، در جست‌وجو و اعتبارسنجی نیز کاربرد دارد.

استفادهٔ دوباره و انتخاب مسئولیت درست

برای ساده‌سازی کسر، ابتدا اعتبار صورت و مخرج را در تابع مخصوص کسر بررسی کنید؛ سپس gcd را فراخوانی و هر دو را بر نتیجه تقسیم کنید. gcd نباید بداند کسر قرار است چگونه نمایش داده شود. در گزارش دیگری نیز می‌توان بدون دست‌کاری همان تابع، بخش‌پذیری چند مقدار را بررسی کرد. این استفادهٔ دوباره زمانی قابل اعتماد است که قرارداد زیرتابع ثابت باشد؛ افزودن چاپ، دریافت ورودی یا تغییر متغیر سراسری داخل آن، آزمودن و استفادهٔ بعدی را سخت می‌کند.

در مدل ساده‌ای که عملیات روی عددهای محدودهٔ ثابت را یک گام می‌گیریم، بررسی اول‌بودن در بدترین حالت تا حدود ریشهٔn پیش می‌رود و حافظهٔ کمکی آن ثابت است. اقلیدس به‌جای بررسی تمام عددها، با باقی‌مانده‌ها پیش می‌رود؛ تحلیل دقیق تعداد گام‌های آن به بحث جداگانه نیاز دارد. از کوتاه‌ترشدن چند خروجی نمونه نتیجه نگیرید که «این کد در همهٔ محیط‌ها چند برابر سریع‌تر است». درس هزینهٔ اجرا فرق شمارش عملیات، اندازهٔ ورودی و اندازه‌گیری زمان واقعی را توضیح می‌دهد.

تمرین‌ها را ابتدا با مداد حل کنید و سپس ورودی را در فایل تغییر دهید. اگر assert شکست خورد، مقدارها را در همان مرحلهٔ حلقه یادداشت کنید؛ حذف آزمون، رفع خطا نیست. راهنمای اجرا در دورهٔ Node.js ویندوز آمده است: https://www.darsavand.com/courses/nodejs-windows-backend-start . برای نحو تابع، مرور دورهٔ نخست جاوااسکریپت کافی است: https://www.darsavand.com/courses/javascript-from-zero-to-project . در اینجا هدف طراحی الگوریتم است و وابستگی جدید یا نصب کتابخانه لازم ندارید.

نمونه‌سؤال‌های تألیفی و پاسخ تشریحی

سؤال۱: با ردگیری اقلیدس، ب.م.مِ ۸۴ و ۳۰ را به دست آورید و خاتمه را توضیح دهید.

پاسخ۱: جفت‌ها به‌ترتیب (۸۴،۳۰)، (۳۰،۲۴)، (۲۴،۶)، (۶،۰) هستند. پس پاسخ ۶ است. در هر گام، باقی‌مانده از مقسوم‌علیه مثبت قبلی کوچک‌تر است؛ بنابراین دنبالهٔ عددهای نامنفی نمی‌تواند برای همیشه کاهش پیدا کند. آزمایش صرفِ بخش‌پذیری هر دو عدد بر ۶، بزرگ‌ترین‌بودن را اثبات نمی‌کند؛ حفظ مجموعهٔ مقسوم‌علیه‌های مشترک همراه با خاتمه دلیل کامل‌تری است.

سؤال۲: چرا حلقهٔ عدد اول باید مرز d <= n / d را شامل کند؟ با ۴۹ یک ضد‌مثال بسازید.

پاسخ۲: اگر فقط d < n / d بررسی شود، در n=49 و d=7 شرط نادرست می‌شود و مقسوم‌علیه ۷ بررسی نمی‌شود. بنابراین برنامه ممکن است مربع یک عدد اول را اول اعلام کند. با <=، مرحلهٔ d=7 وارد حلقه می‌شود و باقی‌ماندهٔ صفر را می‌یابد. این نمونه نشان می‌دهد تست مربع‌ها مانند ۴،۹،۲۵ و ۴۹ برای پوشش مرز لازم است؛ تنها چند عدد اول برای آزمون کافی نیست.

سؤال۳: تابع ساده‌سازی کسرِ با صورت صفر و مخرج مثبت چه قراردادی لازم دارد؟ پاسخ ۰/۱۲ را توضیح دهید.

پاسخ۳: صورت و مخرج را جدا اعتبارسنجی کنید؛ صورت عدد صحیح نامنفی و مخرج عدد صحیح مثبت باشد. d=gcd(0,12)=12 و خروجی صورت ۰ و مخرج۱ می‌شود. پیش از فراخوانی gcd، مخرج صفر را رد کنید؛ تعریف رفتار gcd برای یک جفت عدد، مجوز تقسیم بر صفر در کسر نیست. چاپ نتیجه نیز در لایهٔ نمایش بماند و تابع، دو عدد ساده‌شده را برگرداند.

مطالعهٔ تکمیلی و معیار یادگیری

هنگام تحویل تمرین، قرارداد ورودی، یک اجرای دستی و دلیل خاتمه را کنار کد بنویسید. باید بتوانید توضیح دهید چرا gcd چاپ نمی‌کند، چرا جفت صفر و صفر رد می‌شود، و چرا مربع عدد اول در آزمون‌ها حضور دارد. برای بررسی بیشترِ نقش قرارداد و تابع، منابع رسمی زیر را بخوانید؛ مثال‌ها و توضیح فارسی این درس تألیف مستقل تحریریه درس‌آوند است، نه ترجمهٔ متن یا بازنشر کد منابع.

MIT 6.0001 — Decomposition, Abstraction, Functions: https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/6ba59859535f1566dd57a7279aeba5d1_MIT6_0001F16_Lec4.pdf
Princeton — Euclid: https://introcs.cs.princeton.edu/java/23recursion/Euclid.java.html
Princeton — Prime: https://introcs.cs.princeton.edu/java/13flow/Prime.java.html
MDN — Number.isSafeInteger: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/isSafeInteger

فایل مثال‌ها، راهنمای فارسی اجرا و عیب‌یابی، پروژهٔ گزارش نمره‌ها و آزمون جمع‌بندی تألیفی با پاسخ تشریحی، رایگان در صفحهٔ بستهٔ تمرین همین دوره ارائه می‌شود:
https://www.darsavand.com/resources/computer-algorithms-practice-kit
تألیف و مثال‌های اختصاصی: تحریریه درس‌آوند.