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

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

از شرط بولی تا تصمیم قابل بررسی

شرط عبارتی است که در مدل مسئله درست یا نادرست می‌شود. «مبلغ مثبت است» یک گزارهٔ مشخص است، ولی «مبلغ خوب است» تا وقتی خوب‌بودن تعریف نشده، برای الگوریتم کافی نیست. در شبه‌کد از اگر، وگرنه‌اگر و وگرنه استفاده می‌کنیم. شاخه‌های یک زنجیره به ترتیب بررسی می‌شوند و نخستین شرط درست، مسیر را تعیین می‌کند. چند دستور اگرِ مستقل رفتار دیگری دارند: ممکن است بیش از یک بدنه اجرا شود. بنابراین شکل ظاهری کوتاه‌تر همیشه همان تصمیم قبلی را حفظ نمی‌کند.

پیش از دسته‌بندی، ورودی را معتبر کنید. در این درس نمره باید یک عدد متناهی بین صفر و بیست باشد؛ متن «۱۷» هنوز عدد مدل نیست. تبدیل متن فرم، از جمله رقم فارسی، مسئله‌ای جداست و نباید پنهانی داخل الگوریتم دسته‌بندی انجام شود. مفهوم #validation-contracts را کنار #if-else بخوانید. رد ورودی نامعتبر با پاسخ معمول تفاوت دارد: نباید نمرهٔ بیست‌ویک را به نزدیک‌ترین مرز بچسبانیم و وانمود کنیم دادهٔ اصلی درست بوده است.

مثال حل‌شدهٔ اول؛ بیشینهٔ سه عدد و مسئلهٔ تساوی

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

الگوریتم بیشینهٔ سه مقدار
ورودی: a، b و c، همگی عدد متناهی
best ← a
اگر b > best آنگاه best ← b
اگر c > best آنگاه best ← c
خروجی: best

برای ورودی a برابر منفی هشت، b برابر منفی سه و c برابر منفی پنج، نخست best منفی هشت است. شرط اول درست می‌شود و best به منفی سه تغییر می‌کند. شرط دوم نادرست است، زیرا منفی پنج از منفی سه بزرگ‌تر نیست. خروجی منفی سه خواهد بود. نقطهٔ مهم، مقدار اولیه است: اگر صفر بگذاریم، برنامه روی همین داده پاسخ اشتباه می‌دهد؛ حتی با اینکه هر مقایسه به‌تنهایی از نظر نحوی صحیح است.

مرحله              نامزد best        دلیل
آغاز               -8                نخستین مقدار ورودی
بررسی b=-3         -3                -3 > -8
بررسی c=-5         -3                -5 > -3 نادرست
خروجی              -3                بزرگ‌ترین مقدار

فایل 04-maximum-three.mjs را با کد بعدی بسازید و با Node.js اجرا کنید. assert انتظارهای ما را به بررسی واقعی تبدیل می‌کند؛ اگر نتیجه فرق کند، اجرای فایل با خطا متوقف می‌شود. استفاده از Number.isFinite در این پیاده‌سازی، متن عددی و NaN را نمی‌پذیرد. سپس فقط دو مقدار نمونه چاپ می‌شود. این یک تابع کوچک و مستقل است و دادهٔ بیرونی را تغییر نمی‌دهد؛ برای تمرین لازم نیست صفحهٔ وب یا سرور راه بیندازید.

import assert from 'node:assert/strict';

function maximumOfThree(a, b, c) {
  if (![a, b, c].every(Number.isFinite)) {
    throw new TypeError('Three finite numbers required');
  }
  let best = a;
  if (b > best) best = b;
  if (c > best) best = c;
  return best;
}

assert.equal(maximumOfThree(-8, -3, -5), -3);
assert.equal(maximumOfThree(7, 7, 2), 7);
assert.equal(maximumOfThree(4, 4, 4), 4);
assert.throws(() => maximumOfThree(2, NaN, 4), TypeError);
console.log(maximumOfThree(-8, -3, -5));
console.log(maximumOfThree(7, 7, 2));

خروجی دو خط، به ترتیب منفی سه و هفت است. اکنون جای a و c را عوض کنید؛ مقدار بیشینه باید ثابت بماند. این بررسی کمکی، رابطه‌ای میان ورودی‌ها را می‌سنجد، ولی اثبات کامل درستی نیست. برای استدلال، بعد از بررسی هر مقدار می‌گوییم best بزرگ‌ترین مقدارِ دیده‌شده تا این نقطه است. در پایان همهٔ سه مقدار دیده شده‌اند؛ پس همان نامزد، پاسخ مسئلهٔ کامل است. این فکر ساده در پیمایش آرایه نیز به کار می‌آید.

مثال حل‌شدهٔ دوم؛ جدول تصمیم نمرهٔ تمرین

سیاست آموزشی این مثال ساختگی است و مقررات رسمی دانشگاه‌ها را بیان نمی‌کند: نمرهٔ کمتر از ده نیازمند تمرین، از ده تا کمتر از هفده قبول و از هفده تا بیست عالی است. به‌جای عبارت مبهم «بین ده و هفده»، باز یا بسته‌بودن هر سر بازه را می‌نویسیم. ابتدا همهٔ ورودی‌های خارج از صفر تا بیست رد می‌شوند، بعد دسته‌ها تعیین می‌شوند. با این جداسازی، هر نمرهٔ مجاز دقیقاً یک پاسخ دارد و بررسی دستهٔ آخر به حدس وابسته نیست.

شرط ورودی                      نتیجه
نوع عددی نیست یا متناهی نیست     خطای نوع
score < 0 یا score > 20         خطای محدوده
17 <= score <= 20               excellent
10 <= score < 17                passed
0 <= score < 10                 needs-practice

می‌توانیم شرط بزرگ‌تر را ابتدا بررسی کنیم: اگر score حداقل هفده بود، نتیجهٔ عالی را برگردان؛ وگرنه اگر حداقل ده بود، قبول را برگردان؛ وگرنه نیازمند تمرین است. در شاخهٔ دوم می‌دانیم شرط اول نادرست بوده، پس score کمتر از هفده است. این دانسته، بخشی از استدلال الگوریتم است. اگر ترتیب دو شرط را جابه‌جا کنیم، نمرهٔ هجده در شاخهٔ قبول متوقف می‌شود و نتیجهٔ مورد نظر از بین می‌رود.

import assert from 'node:assert/strict';

function practiceBand(score) {
  if (typeof score !== 'number' || !Number.isFinite(score)) {
    throw new TypeError('A finite numeric score is required');
  }
  if (score < 0 || score > 20) throw new RangeError('Score must be 0..20');
  if (score >= 17) return 'excellent';
  if (score >= 10) return 'passed';
  return 'needs-practice';
}

assert.equal(practiceBand(0), 'needs-practice');
assert.equal(practiceBand(9.99), 'needs-practice');
assert.equal(practiceBand(10), 'passed');
assert.equal(practiceBand(16.99), 'passed');
assert.equal(practiceBand(17), 'excellent');
assert.equal(practiceBand(20), 'excellent');
assert.throws(() => practiceBand('17'), TypeError);
assert.throws(() => practiceBand(21), RangeError);
console.log([9.99, 10, 17, 20].map(practiceBand).join(', '));

خروجی نمونه عبارت needs-practice, passed, excellent, excellent است. آزمون‌های ۹٫۹۹، ده، ۱۶٫۹۹، هفده و بیست عمدی‌اند؛ درست‌بودن نتیجه برای نمرهٔ دوازده دربارهٔ مرز هفده اطلاعات کافی نمی‌دهد. همچنین نوع متن «17» و عدد بیست‌ویک جداگانه آزموده می‌شوند. خطای نوع و خطای محدوده دو علت متفاوت دارند. در رابط واقعی می‌توان برای هرکدام پیام فارسی روشنی نشان داد و مقدار واردشده را برای اصلاح نگه داشت.

ترکیب شرط‌ها و خطای رایج منطق

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

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

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

پرسش 1 — الگوریتم بیشینه با best برابر صفر برای ورودی‌های منفی چه ایرادی دارد؟ یک مثال نقض و اصلاح بنویسید.

پاسخ تشریحی — برای ورودی‌های منفی ۸-، ۳- و ۵- هیچ مقدار از صفر بزرگ‌تر نیست؛ بنابراین صفر برمی‌گردد، درحالی‌که صفر عضو ورودی نیست. best را از نخستین مقدار معتبر، یعنی a، مقداردهی کنید و دو مقدار باقی‌مانده را با آن مقایسه کنید. نتیجهٔ درست ۳- است. آزمون فقط با اعداد مثبت این خطا را آشکار نمی‌کند.

پرسش 2 — اگر شرط score >= 10 پیش از score >= 17 قرار بگیرد، نمرهٔ ۱۸ چه می‌شود؟ قرارداد فعلی را اصلاح کنید.

پاسخ تشریحی — در زنجیره‌ای که هر شاخه نتیجه را برمی‌گرداند، نمرهٔ ۱۸ در شرط نخست پذیرفته و passed می‌شود؛ شاخهٔ excellent اجرا نمی‌شود. مرزهای بزرگ‌تر را ابتدا بررسی کنید، یا بازه‌های ناپوشا مانند 10 <= score < 17 بنویسید. اعتبارسنجی ۰ تا ۲۰ باید همچنان پیش از دسته‌بندی بماند؛ تغییر ترتیب جای آن را نمی‌گیرد.

پرسش 3 — برای سه عدد برابر، آیا پاسخ بیشینه یکتا است؟ اگر سؤال «شمارهٔ نخستین برنده» باشد چه چیزی باید به قرارداد اضافه شود؟

پاسخ تشریحی — مقدار بیشینه یکتا است و همان مقدار مشترک برمی‌گردد، اما جایگاه‌های دارای آن مقدار می‌توانند چندتا باشند. برای نخستین برنده باید قرارداد خروجی را از مقدار به اندیس تغییر دهید و در تساوی جایگاه قبلی را نگه دارید؛ مقایسهٔ سخت > چنین سیاستی را در پیمایش ترتیب‌دار پشتیبانی می‌کند. برای آخرین برنده، سیاست دیگری لازم است؛ آزمون تساوی باید تفاوت را نشان دهد.

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

منابع و ادامهٔ مسیر

برای نحو اجرایی به مدخل‌های #boolean، #if-else و #number مراجعه کنید. در درس بعد همین تصمیم‌های روشن را داخل تکرار به کار می‌بریم؛ پیش از آن باید تشخیص دهید کدام شرط ورودی را رد می‌کند و کدام شرط یک ورودی مجاز را دسته‌بندی می‌کند. اگر اجرای فایل mjs برایتان تازه است، راهنمای محیط ویندوز درس‌آوند کمک می‌کند: https://www.darsavand.com/courses/nodejs-windows-backend-start

منابع رسمی برای مطالعهٔ تکمیلی، نه متن ترجمه‌شدهٔ این درس:
MIT 6.0001، موضوع Branching and Iteration: https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/pages/lecture-slides-code/
MDN، کنترل جریان و شرط‌ها: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Control_flow_and_error_handling
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
تألیف و مثال‌های اختصاصی: تحریریه درس‌آوند.