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

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

اندیس، مقدار و طول سه چیز متفاوت‌اند

در آرایهٔ چهارعضوی، طول چهار است، ولی اندیس‌ها در قرارداد این دوره صفر، یک، دو و سه هستند. در خانهٔ صفر ممکن است مقدار هشتاد باشد؛ صفر جایگاه است و هشتاد داده. دستور خواندن values[i] این دو را به هم وصل می‌کند. وقتی پاسخ سؤال «کدام خانه؟» است، اندیس برمی‌گردانیم و وقتی «چه مقدار؟» است، خود داده را می‌خواهیم. نام متغیر و نوع خروجی را روشن انتخاب کنید تا عددِ پاسخ به شکل مبهم میان این دو معنا جابه‌جا نشود.

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

مثال حل‌شدهٔ اول؛ گزارش عددی در یک پیمایش

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

total ← 0
maximum ← «هنوز مقداری ندیده‌ایم»
برای i از 0 تا length - 1:
    value ← values[i]
    اگر value نامعتبر است، خطا
    total ← total + value
    اگر هنوز مقداری ندیده‌ایم یا value > maximum:
        maximum ← value
اگر length = 0 آنگاه mean ← null
وگرنه mean ← total / length
خروجی: length، total، maximum و mean

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

i        value        total پس از دور        maximum
0        -8           -8                     -8
1        -3           -11                    -3
2        -5           -16                    -3
3        -3           -19                    -3
mean = -19 / 4 = -4.75

بلوک بعدی را در 06-number-report.mjs اجرا کنید. دو خط JSON گزارش فهرست نمونه و فهرست خالی چاپ می‌شود. آزمون ثابت‌ماندن values عمدی است؛ تابع گزارش قرار نیست داده را مرتب یا ویرایش کند. شرط maximum برابر null فقط نشان می‌دهد هنوز هیچ مقدار معتبری دیده نشده است. در قرارداد حاضر null دادهٔ مجاز نیست، بنابراین نشانه با یک مقدار واقعی اشتباه نمی‌شود. این الگو را تنها وقتی به مسئلهٔ تازه ببرید که دامنهٔ داده را دوباره بررسی کرده باشید.

import assert from 'node:assert/strict';

function describeNumbers(values) {
  if (!Array.isArray(values) || values.length > 100) {
    throw new TypeError('An array of at most 100 numbers is required');
  }
  let total = 0;
  let maximum = null;
  for (let i = 0; i < values.length; i += 1) {
    const value = values[i];
    if (!Number.isFinite(value) || Math.abs(value) > 1000) {
      throw new RangeError('Each value must be finite and in -1000..1000');
    }
    total += value;
    if (maximum === null || value > maximum) maximum = value;
  }
  return {
    count: values.length,
    total,
    maximum,
    mean: values.length === 0 ? null : total / values.length
  };
}

const values = [-8, -3, -5, -3];
assert.deepEqual(describeNumbers(values), { count: 4, total: -19, maximum: -3, mean: -4.75 });
assert.deepEqual(values, [-8, -3, -5, -3]);
assert.deepEqual(describeNumbers([]), { count: 0, total: 0, maximum: null, mean: null });
assert.throws(() => describeNumbers([1, NaN]), RangeError);
console.log(JSON.stringify(describeNumbers(values)));
console.log(JSON.stringify(describeNumbers([])));

در هر دور، total جمعِ بخش دیده‌شده و maximum بیشینهٔ همان بخش است. پس از آخرین خانه، بخش دیده‌شده برابر کل آرایه می‌شود و گزارش کامل است. تعداد از طول می‌آید، چون هیچ داده‌ای فیلتر نشده است. اگر بعداً بگوییم فقط عددهای مثبت را گزارش کن، دیگر تقسیم بر طول کل درست نیست؛ باید تعداد پذیرفته‌شده را جدا بشماریم. این نمونه نشان می‌دهد تغییر کوچکی در صورت سؤال می‌تواند معنای یک متغیر ظاهراً بدیهی را عوض کند.

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

برای جست‌وجو، فهرست شناسه‌های متنی را از چپ به راست می‌خوانیم. اگر مقدار خانه با هدف برابر بود، اندیس همان خانه را برمی‌گردانیم؛ اگر فهرست تمام شد، منفی یک نشان‌دهندهٔ یافت‌نشدن است. ورودی لازم نیست مرتب باشد. تکراری‌بودن هم ممنوع نیست، چون سیاست ما نخستین وقوع است. شناسهٔ «۰۷» را به عدد تبدیل نمی‌کنیم؛ در نمونهٔ اجرایی «07» با «7» تفاوت دارد. همین انتخاب کوچک برای شمارهٔ پرونده یا کد کالا می‌تواند جلوی اشتباه داده را بگیرد.

برای i از 0 تا length - 1:
    اگر ids[i] = target آنگاه خروجی i و پایان
خروجی -1

ردگیری ids = ["07", "12", "07"] و target = "07":
i=0: برابر است؛ خروجی 0؛ خانه‌های بعدی برای یافتن پاسخ لازم نیستند.
اگر target = "7": هیچ تساوی رخ نمی‌دهد؛ خروجی -1.

در کاربردی نزدیک، برای ساخت گزارش فعالیت‌ها فقط سه دستهٔ lecture، lab و practice داریم. برای هر دسته یک شمارندهٔ صفر می‌گذاریم و در هر دور دقیقاً یکی را زیاد می‌کنیم. اگر نام ناشناخته برسد، آن را بی‌خبر حذف نمی‌کنیم؛ خطا می‌دهیم تا مجموع گزارش گمراه‌کننده نشود. برای دسته‌های پویا بعدها Map مناسب‌تر است، اما وقتی دامنهٔ مسئله کوچک و ثابت است، همین تصمیم‌های صریح برای یادگیری کافی‌اند. فهرست خالی هم گزارش معتبر با سه صفر می‌دهد.

import assert from 'node:assert/strict';

function firstIndexOfId(ids, target) {
  if (!Array.isArray(ids) || typeof target !== 'string') {
    throw new TypeError('An array and a string target are required');
  }
  for (let i = 0; i < ids.length; i += 1) {
    if (typeof ids[i] !== 'string') throw new TypeError('IDs must be strings');
  }
  for (let i = 0; i < ids.length; i += 1) {
    if (ids[i] === target) return i;
  }
  return -1;
}

function countKinds(kinds) {
  if (!Array.isArray(kinds)) throw new TypeError('An array is required');
  const counts = { lecture: 0, lab: 0, practice: 0 };
  for (const kind of kinds) {
    if (kind === 'lecture') counts.lecture += 1;
    else if (kind === 'lab') counts.lab += 1;
    else if (kind === 'practice') counts.practice += 1;
    else throw new RangeError('Unknown kind');
  }
  return counts;
}

assert.equal(firstIndexOfId(['07', '12', '07'], '07'), 0);
assert.equal(firstIndexOfId(['07', '12', '07'], '7'), -1);
assert.equal(firstIndexOfId([], '07'), -1);
assert.throws(() => firstIndexOfId(['07', 12], '07'), TypeError);
assert.deepEqual(countKinds(['lab', 'lecture', 'lab']), { lecture: 1, lab: 2, practice: 0 });
assert.deepEqual(countKinds([]), { lecture: 0, lab: 0, practice: 0 });
assert.throws(() => countKinds(['seminar']), RangeError);
console.log(firstIndexOfId(['07', '12', '07'], '07'));
console.log(JSON.stringify(countKinds(['lab', 'lecture', 'lab'])));

در 06-search-and-count.mjs دو خط چاپ می‌شود: نخست صفر و سپس گزارشی با lecture یک، lab دو و practice صفر. نخستین تابع، پیش از جست‌وجو همهٔ شناسه‌ها را اعتبارسنجی می‌کند؛ پس اگر همان خانهٔ اول پاسخ باشد، کل زمان این نسخه صرفاً ثابت نیست. بخش جست‌وجوی روی دادهٔ معتبر می‌تواند زود تمام شود، ولی بررسی کامل نوع داده یک پیمایش دارد. این تفاوت میان هزینهٔ الگوریتم هسته و هزینهٔ تابع کامل را هنگام مقایسهٔ روش‌ها روشن نگه دارید.

چرا گاهی باید همهٔ خانه‌ها را دید؟

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

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

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

پرسش 1 — آرایهٔ [-9, -2, -6] چه بیشینه و اندیسی برای نخستین بیشینه دارد؟ چرا شروع بیشینه از صفر غلط است؟

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

پرسش 2 — در فهرست شناسه‌های ["03", "8", "03"] جست‌وجوی "03" و "3" چه خروجی دارد؟ آیا -1 اندیس معتبر است؟

پاسخ تشریحی — برای "03" پاسخ صفر است و نخستین وقوع را برمی‌گردانیم؛ برای "3" پاسخ منفی یک است، زیرا شناسهٔ متنی با صفر ابتدایی قرارداد دیگری دارد. منفی یک در این تابع نشانهٔ یافت‌نشدن است و اندیس معتبر فهرست نیست. آن را پیش از دسترسی به خانه بررسی کنید؛ تبدیل بی‌اعلام شناسه به عدد، دو شناسهٔ متفاوت را یکی می‌کند.

پرسش 3 — برای ورودی خالی گزارش عددی و شمارش دسته‌ها را مشخص کنید. چرا میانگین و بیشینه را صفر نمی‌گذاریم؟

پاسخ تشریحی — گزارش عددی count و total صفر، ولی mean و maximum برابر null دارد. در شمارش دسته‌های ازپیش‌تعریف‌شده، هر سه شمارنده صفر می‌مانند. بیشینهٔ صفر می‌تواند یک دادهٔ واقعی باشد و میانگین صفر هم برای فهرستی مانند منفی یک و یک ممکن است؛ null تفاوت نبود داده با نتیجهٔ واقعی صفر را حفظ می‌کند.

تمرین تکمیلی: تابع نخستین اندیس را به شمارندهٔ وقوع هدف تبدیل کنید. پاسخ راهنما این است که return داخل شاخهٔ تطبیق را بردارید، count را ابتدا صفر بگذارید و فقط هنگام تساوی افزایش دهید؛ بعد از پایان حلقه همان count را برگردانید. برای ["07", "12", "07"] و هدف "07" پاسخ دو است. معیار تحویل، ثابت‌ماندن ورودی، حفظ تفاوت "07" و "7"، پاسخ صفر برای فهرست خالی و توضیح دلیل پیمایش کامل است.

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

مدخل‌های #array، #for-loop، #return و #function برای خواندن کدهای اجرایی مفیدند. این درس بر طراحی پیمایش تمرکز داشت؛ برای رفتار دقیق روش‌های آماده، کپی و تحلیل سرعت، آموزش مستقل آرایه‌ها را به‌عنوان مطالعهٔ بعدی بخوانید: https://www.darsavand.com/resources/javascript-nodejs-arrays-performance. در درس بعد، همین قراردادهای کوچک را به تابع‌هایی تبدیل می‌کنیم که یک مسئلهٔ بزرگ‌تر را مرحله‌به‌مرحله حل می‌کنند.

منابع رسمی برای مطالعهٔ تکمیلی:
Harvard CS50، توضیح جست‌وجوی خطی: https://cs50.harvard.edu/x/notes/3/
MDN، آرایه و تفاوت خانه‌های آن: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array
MDN، حلقه و پیمایش: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Loops_and_iteration
تألیف، مثال‌ها و پرسش‌های مستقل: تحریریه درس‌آوند.

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