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

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

شمارنده با انباره فرق دارد

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

برای جمع، مقدار اولیهٔ صفر طبیعی است؛ جمع هیچ داده‌ای صفر است. همین استدلال برای بیشینه کار نمی‌کند و صفر را نباید بی‌فکر برای هر متغیر گزارش گذاشت. پیش از نوشتن حلقه، پاسخ حالت صفر بار اجرا را تعیین کنید. در حلقهٔ while شرط پیش از بدنه بررسی می‌شود، پس ممکن است هیچ دوری نداشته باشیم. در مدل do...while بدنه دست‌کم یک بار اجرا می‌شود؛ این تفاوت باید از نیاز مسئله بیاید، نه از کوتاه‌ترشدن کد.

مثال حل‌شدهٔ اول؛ جمع یک تا n

قرارداد ورودی، عدد صحیح n از صفر تا یک میلیون است و خروجی مجموع عددهای یک تا خود n خواهد بود. برای صفر، مجموعهٔ داده خالی است و پاسخ صفر می‌شود. سقف آموزشی دو فایده دارد: تعداد تکرارها بی‌دلیل بزرگ نمی‌شود و بیشترین مجموع، یعنی ۵۰۰۰۰۰۵۰۰۰۰۰، هنوز در محدودهٔ عدد صحیح امن جاوااسکریپت است. در کاربرد عمومی نمی‌توان از درست‌بودن تک‌تک عددهای ورودی نتیجه گرفت هر مجموعی هم دقیق می‌ماند؛ محدودیت جمع باید جدا توجیه شود.

الگوریتم جمعِ شامل n
ورودی: n صحیح، 0 <= n <= 1000000
total ← 0
i ← 1
تا وقتی i <= n تکرار کن:
    total ← total + i
    i ← i + 1
خروجی: total

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

پیش از دور       i       total       پس از افزودن
1                1       0           1
2                2       1           3
3                3       3           6
4                4       6           10
بررسی پایانی     5       10          بدنه اجرا نمی‌شود

فایل 05-sum-through.mjs را با بلوک زیر بسازید و اجرا کنید. خروجی ده و صفر در دو خط است. آزمون یک میلیون، فقط بررسی سقف قرارداد و مجموع دقیق آن است؛ از مدت اجرای یک نوبت نتیجهٔ کلی دربارهٔ سرعت رایانه نمی‌گیریم. اگر در حال یادگیری هستید، ابتدا نمونهٔ چهار را روی کاغذ ردگیری کنید و بعد آن را اجرا کنید. هدف این نیست که کنسول جای فکرکردن به مسیر حلقه را بگیرد.

import assert from 'node:assert/strict';

function sumThrough(n) {
  if (!Number.isInteger(n) || n < 0 || n > 1_000_000) {
    throw new RangeError('n must be an integer in 0..1000000');
  }
  let total = 0;
  let i = 1;
  while (i <= n) {
    total += i;
    i += 1;
  }
  return total;
}

assert.equal(sumThrough(0), 0);
assert.equal(sumThrough(1), 1);
assert.equal(sumThrough(4), 10);
assert.equal(sumThrough(1_000_000), 500000500000);
assert.throws(() => sumThrough(-1), RangeError);
assert.throws(() => sumThrough(2.5), RangeError);
console.log(sumThrough(4));
console.log(sumThrough(0));

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

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

مثال حل‌شدهٔ دوم؛ پایان با نشانهٔ جدا از داده

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

ورودی: دنباله‌ای حداکثر 1000 عضوی؛ هر داده صحیح بین 0 و 1000000
نشانگر پایان: -1
total ← 0
count ← 0
برای هر value به ترتیب:
    اگر value = -1 آنگاه خروجی (total, count) و پایان
    اگر value دادهٔ معتبر نیست آنگاه خطا
    total ← total + value
    count ← count + 1
اگر دنباله تمام شد ولی نشانگر نرسید، خطا

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

import assert from 'node:assert/strict';

function totalBeforeEnd(values) {
  if (!Array.isArray(values) || values.length > 1000) {
    throw new TypeError('An array of at most 1000 values is required');
  }
  let total = 0;
  let count = 0;
  for (const value of values) {
    if (value === -1) return { total, count };
    if (!Number.isSafeInteger(value) || value < 0 || value > 1_000_000) {
      throw new RangeError('Use an integer in 0..1000000, or -1 to end');
    }
    total += value;
    count += 1;
  }
  throw new Error('Missing end marker');
}

assert.deepEqual(totalBeforeEnd([12, 0, 8, -1, 99]), { total: 20, count: 3 });
assert.deepEqual(totalBeforeEnd([-1]), { total: 0, count: 0 });
assert.throws(() => totalBeforeEnd([]), /Missing end marker/);
assert.throws(() => totalBeforeEnd([2, -2, -1]), RangeError);
assert.throws(() => totalBeforeEnd([2, 3]), /Missing end marker/);
console.log(JSON.stringify(totalBeforeEnd([12, 0, 8, -1, 99])));
console.log(JSON.stringify(totalBeforeEnd([-1])));

خروجی دو خط JSON است: در نخست total بیست و count سه، و در دوم هر دو صفر هستند. برای اجرای بلوک، فایل 05-sentinel-total.mjs بسازید. بیشترین مجموع این قرارداد از یک میلیارد بیشتر نمی‌شود؛ حداکثر هزار عضو، هرکدام حداکثر یک میلیون، داریم. پس جمع عدد صحیح امن باقی می‌ماند. در دادهٔ واقعاً جریانی باید سقف تعداد یا مجموع و سیاست قطع جریان جدا پیاده شود؛ محدودیت طول آرایهٔ حاضر، جای آن طراحی را برای هر منبع ورودی نمی‌گیرد.

شرط ادامه، دادهٔ خالی و خطای یک‌واحدی

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

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

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

پرسش 1 — در جمع یک تا n، اگر شرط i < n باشد چه ورودی کوچکی خطا را آشکار می‌کند؟

پاسخ تشریحی — برای n برابر یک، حلقه حتی یک بار اجرا نمی‌شود و صفر می‌دهد؛ پاسخ باید یک باشد. اگر قرارداد جمعِ شامل n است، شرط i <= n لازم است. برای n برابر چهار نیز خروجی شش به‌جای ده می‌شود. با تغییر قرارداد به جمعِ کمتر از n، همان شرط ممکن است درست باشد؛ بنابراین علامت مقایسه را باید با صورت سؤال سنجید.

پرسش 2 — برای ورودی [5, 0, -1, 9] مجموع و تعداد چیست؟ چرا میانگین دو و نیم است؟

پاسخ تشریحی — فقط پنج و صفر داده‌اند؛ نشانگر منفی یک و مقدار پس از آن وارد گزارش نمی‌شوند. مجموع پنج و تعداد دو است، پس میانگین ۲٫۵ می‌شود. اگر صفر را به بهانهٔ «چیزی به جمع اضافه نمی‌کند» از شمارش حذف کنید، میانگین به‌اشتباه پنج خواهد شد. صفر یک دادهٔ معتبر است، نه نشانهٔ پایان.

پرسش 3 — با حذف i += 1 از جمع یک تا n، آیا همهٔ ورودی‌ها بی‌نهایت اجرا می‌شوند؟ اصلاح و دلیل را بنویسید.

پاسخ تشریحی — خیر؛ برای n برابر صفر، شرط اولیه نادرست است و حلقه اجرا نمی‌شود. برای هر n مجاز حداقل یک، i روی یک می‌ماند و شرط همیشه درست است؛ برنامه خاتمه نمی‌یابد. افزایش i پس از پردازش لازم است. معیار خاتمه، کم‌شدن تعداد مقدارهای پردازش‌نشده است؛ فقط تغییر total تضمینی برای پایان نیست.

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

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

مدخل‌های #for-loop، #while-loop و #variable به نحو اجرا کمک می‌کنند. برای تفاوت هزینهٔ محاسباتی و زمان اندازه‌گیری‌شده، پس از این فصل درس مستقل درس‌آوند را بخوانید: https://www.darsavand.com/resources/javascript-runtime-cost-complexity. در درس بعد، همین انباره‌ها و شرط‌های توقف را روی فهرست‌های مشخص به کار می‌بریم و تفاوت جایگاه داده با خود مقدار آن را روشن می‌کنیم.

منابع رسمی برای مطالعهٔ تکمیلی:
MIT 6.0001، ترتیب مباحث تکرار و بررسی برنامه: 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/Loops_and_iteration
MDN، قرارداد عدد صحیح امن: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/isSafeInteger
تألیف، مثال‌ها و پرسش‌های مستقل: تحریریه درس‌آوند.

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