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

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

قرارداد داده و سیاست آموزشی

هر ردیف سه فیلد دارد: id متن یکتای یک تا چهل نویسه از حرف لاتین، رقم لاتین، خط تیره یا زیرخط؛ name متنِ پس از حذف فاصلهٔ دو سر، بین دو تا هشتاد واحد UTF-16؛ و score عدد متناهی بین صفر و بیست. شناسه را به عدد تبدیل نمی‌کنیم و بزرگی و کوچکی حروف در آن مهم است. ردیف‌ها حداکثر هزار عددند. این سقف و آستانهٔ پذیرشِ نمرهٔ ده، سیاست آموزشی همین پروژه‌اند؛ به مقررات همهٔ دانشگاه‌های ایران نسبت داده نمی‌شوند.

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

طراحی مسیر؛ پاک‌سازی را از محاسبه جدا کنید

cleanRows یک نسخهٔ مستقل و محدود به فیلدهای مجاز می‌سازد. makeReport یک بار روی آن می‌گذرد و شمارنده‌ها را به‌روز می‌کند. findStudent شناسهٔ دقیق را خطی جست‌وجو می‌کند و برای نبود پاسخ null می‌دهد. rankStudents با مرتب‌سازی درجی، نمره را نزولی و در تساوی، شناسه را صعودی می‌چیند. همهٔ توابع عمومی مستقلاً اعتبارسنجی می‌کنند؛ برای این پروژهٔ کوچک، روشن‌بودن قرارداد را به حذف چند پیمایش ترجیح داده‌ایم. در API واقعیِ پرترافیک، طراحی مدلِ یک‌بار اعتبارسنجی‌شده تصمیم جداگانه‌ای است.

REPORT(input)
    rows <- VALIDATE_AND_COPY(input)
    total <- 0; passed <- 0; min <- NONE; max <- NONE
    FOR EACH row IN rows
        total <- total + row.score
        IF row.score >= 10 THEN passed <- passed + 1
        UPDATE min AND max USING row.score
    IF length(rows) = 0 THEN mean <- NONE
    ELSE mean <- total / length(rows)
    RETURN count, passed, count-passed, mean, min, max

فایل اصلی؛ کد کامل قابل اجرا

پوشهٔ project را از بستهٔ همراه باز کنید؛ grade-report.mjs دقیقاً کد زیر را دارد. پسوند mjs اجازه می‌دهد از export و import استفاده کنیم. اجرای مستقیم این فایل چیزی چاپ نمی‌کند، چون فقط توابع را تعریف و صادر می‌کند؛ این رفتار عادی است. در ردگیری makeReport، بعد از هر ردیف، total مجموع دیده‌شده‌ها و passed شمار نمره‌های دست‌کم ده در همان پیشوند است. برای نخستین ردیف، null بودن min و max باعث مقداردهی از دادهٔ واقعی می‌شود.

// Educational policy: 0..20 scores, pass >= 10; synthetic records only.
export function cleanRows(input) {
  if (!Array.isArray(input) || input.length > 1000) {
    throw new TypeError('فهرست باید آرایه‌ای با حداکثر ۱۰۰۰ ردیف باشد.');
  }
  const seen = new Set();
  const rows = [];
  for (const row of input) {
    if (!row || typeof row !== 'object' || Array.isArray(row)) {
      throw new TypeError('هر ردیف باید شیء باشد.');
    }
    if (!['id', 'name', 'score'].every(key => Object.hasOwn(row, key))) {
      throw new TypeError('شناسه، نام و نمره الزامی‌اند.');
    }
    const { id, name, score } = row;
    if (typeof id !== 'string' || !/^[A-Za-z0-9_-]{1,40}$/.test(id)) {
      throw new TypeError('شناسه باید متن ۱ تا ۴۰ حرف لاتین، رقم، خط تیره یا زیرخط باشد.');
    }
    if (seen.has(id)) throw new RangeError('شناسهٔ تکراری پذیرفته نمی‌شود.');
    if (typeof name !== 'string' || name.trim().length < 2 || name.trim().length > 80) {
      throw new TypeError('نام باید متن ۲ تا ۸۰ واحد UTF-16 باشد.');
    }
    if (!Number.isFinite(score) || score < 0 || score > 20) {
      throw new RangeError('نمره باید عدد متناهی بین صفر و بیست باشد.');
    }
    seen.add(id);
    rows.push({ id, name: name.trim(), score: score === 0 ? 0 : score });
  }
  return rows;
}

export function makeReport(input) {
  const rows = cleanRows(input);
  let total = 0;
  let passed = 0;
  let min = null;
  let max = null;
  for (const row of rows) {
    total += row.score;
    if (row.score >= 10) passed += 1;
    if (min === null || row.score < min) min = row.score;
    if (max === null || row.score > max) max = row.score;
  }
  return {
    count: rows.length,
    passed,
    failed: rows.length - passed,
    mean: rows.length === 0 ? null : total / rows.length,
    min,
    max
  };
}

export function findStudent(input, id) {
  const rows = cleanRows(input);
  if (typeof id !== 'string') throw new TypeError('شناسهٔ جست‌وجو باید متن باشد.');
  for (const row of rows) if (row.id === id) return row;
  return null;
}

export function rankStudents(input) {
  const rows = cleanRows(input);
  function before(a, b) {
    return a.score > b.score || (a.score === b.score && a.id < b.id);
  }
  for (let i = 1; i < rows.length; i += 1) {
    const current = rows[i];
    let j = i - 1;
    while (j >= 0 && before(current, rows[j])) {
      rows[j + 1] = rows[j];
      j -= 1;
    }
    rows[j + 1] = current;
  }
  return rows;
}

به شرط before در مرتب‌سازی توجه کنید: اگر نمرهٔ جاری بیشتر باشد جلو می‌رود؛ اگر برابر باشد، شناسهٔ کوچک‌تر جلو می‌رود. این مقایسه روی شناسهٔ محدودِ لاتین و رقم است و ادعای ترتیب الفبایی نام فارسی ندارد. مثلاً s10 از نظر متن قبل از s2 می‌آید؛ شناسه‌ها را برای نمونه با طول یکسان مثل s01 بسازید، یا اگر ترتیب عددی می‌خواهید قرارداد دیگری بنویسید. مرتب‌سازی درجی روی نسخهٔ تازه انجام می‌شود؛ بنابراین ترتیب ورودی و ردیف‌های آن عوض نمی‌شود.

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

برای سه ردیفِ نمونه، ابتدا هشت اضافه می‌شود: شمار یک، مجموع هشت، پذیرفته‌شده صفر، کمینه و بیشینه هشت. با شانزدهٔ بعدی، مجموع بیست‌وچهار و شمار پذیرفته‌شده یک می‌شود. با شانزدهٔ سوم، مجموع چهل و شمار پذیرفته‌شده دو است. تقسیم چهل بر سه میانگین تقریباً ۱۳٫۳۳ می‌دهد. مقدار مدل گرد نمی‌شود؛ اگر برای نمایش دو رقم اعشار می‌خواهید، قالب‌بندی را در لایهٔ نمایش انجام دهید. رتبه‌بندی باید s01، سپس s02 و بعد s03 باشد.

فایل demo.mjs مستقل از مرورگر است و در همان پوشه کنار فایل اصلی قرار می‌گیرد. آن را با node demo.mjs یا npm start اجرا کنید. این مثال هم گزارش معمولی و هم فهرست خالی را نشان می‌دهد و در پایان یک ورودی عمداً نامعتبر را داخل try/catch بررسی می‌کند. پیام آخرِ «خطای مورد انتظار» شکست نصب یا خراب‌بودن پروژه نیست؛ نشان می‌دهد مرز ورودی مطابق قرارداد، متن را به نمره تبدیل نکرده است. ارقام نمایشی کنسول، معیار واحد نمره را تغییر نمی‌دهند.

import { makeReport, findStudent, rankStudents } from './grade-report.mjs';

const rows = [
  { id: 's03', name: 'دانشجوی ج', score: 8 },
  { id: 's02', name: 'دانشجوی ب', score: 16 },
  { id: 's01', name: 'دانشجوی الف', score: 16 }
];
console.log('گزارش نمونه:', JSON.stringify(makeReport(rows)));
console.log('جست‌وجو:', JSON.stringify(findStudent(rows, 's02')));
console.log('ترتیب:', rankStudents(rows).map(row => row.id).join(', '));
console.log('دادهٔ خالی:', JSON.stringify(makeReport([])));
try {
  makeReport([{ id: 's04', name: 'نمونه', score: '18' }]);
} catch (error) {
  console.log('خطای مورد انتظار:', error.message);
}

در خروجی، گزارش count برابر ۳، passed برابر ۲، failed برابر ۱، min برابر ۸ و max برابر ۱۶ دارد؛ mean در JSON به صورت 13.333333333333334 دیده می‌شود. جست‌وجو رکورد s02 را برمی‌گرداند و ترتیب چاپ‌شده s01, s02, s03 است. گزارش خالی، سه مقدار آماری null و شمارهای صفر دارد. این دو نمونه کنار هم نشان می‌دهند چرا گذاشتن صفر به‌جای میانگین خالی، معنای گزارش را خراب می‌کند. برای تمرین، یک نمرهٔ دقیقاً ده اضافه کنید و انتظار را پیش از اجرا حساب کنید.

نصب، اجرا و آزمون روی ویندوز یا لینوکس

Node.js نسخهٔ ۲۴ یا بالاتر را نصب و node --version را بررسی کنید. راهنمای ویندوز: https://www.darsavand.com/courses/nodejs-windows-backend-start . در پوشهٔ دارای package.json، npm test آزمون‌ها، npm run check نحو و npm start نمونه را اجرا می‌کند. وابستگی بیرونی نداریم و npm install لازم نیست. دوبار کلیک روی mjs یا قراردادن آن داخل HTML جای ترمینال را نمی‌گیرد.

node --version
cd project
npm run check
npm test
npm start

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

دیباگ؛ از پیام خطا به ورودی مشخص برسید

برای MODULE_NOT_FOUND، محل و نام فایل‌ها را بررسی کنید؛ demo.mjs باید کنار grade-report.mjs باشد. نبود package.json معمولاً یعنی پوشهٔ جاری اشتباه است. برای شکست اعتبارسنجی، یک ردیف ساختگیِ کوچک با همان مشکل بسازید. در خطای منطقی، نخستین دوری را پیدا کنید که شمارنده‌ها با محاسبهٔ دستی فرق دارند. دادهٔ واقعی افراد را در گزارش خطا نگذارید.

هزینه و محدودهٔ استفادهٔ پروژه

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

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

سؤال 1: برای نمره‌های ۸،۱۶،۱۶ گزارش و ترتیب خروجی چه می‌شود؟ اگر آستانهٔ آموزشی به ۱۲ تغییر کند، کدام قسمت‌ها باید بازبینی شوند؟

پاسخ: تعداد سه، پذیرفته‌شده دو، ردشده یک، مجموع چهل و میانگین چهل تقسیم بر سه است؛ کمینه هشت و بیشینه شانزده. در تساوی شانزده، s01 پیش از s02 می‌آید و s03 آخر است. با تغییر آستانه، شرط makeReport، توضیح قرارداد و آزمون‌های مرزی همگی باید تغییر کنند. مرتب‌سازی نمره لزوماً تغییر نمی‌کند؛ آستانه و ترتیب دو سیاست جدا هستند. عدد دوازده را به‌عنوان قانون واقعی دانشگاه معرفی نکنید.

سؤال 2: چرا یک ردیفِ دارای score برابر متن «۱۸» یا شناسهٔ تکراری، کل گزارش را متوقف می‌کند؟ آیا حذف خاموش آن بهتر نیست؟

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

سؤال 3: اگر خروجی رتبه‌بندی را ویرایش کنیم، چرا ورودی نباید عوض شود؟ چرا برای این پروژه یک کپی سطحیِ خود ردیف کافی است؟

پاسخ: توابع قول داده‌اند دادهٔ ورودی را دست‌نخورده نگه دارند. cleanRows هم آرایه و هم شیءهای ردیف را تازه می‌سازد و فقط id، name و score را نگه می‌دارد. این سه فیلد مقدارهای اولیه‌اند و شیء تو در تو ندارند؛ پس کپی همین ردیف‌ها برای قرارداد فعلی کافی است. اگر بعداً مشخصاتِ تو در تو اضافه شود، قرارداد کپی و آزمون هویت مرجع باید بازبینی شود. صرفِ [...input] ردیف‌ها را مستقل نمی‌کند و این تعهد را به‌تنهایی برآورده نمی‌سازد.

معیار تحویل: دو نمونه را دستی حساب و سه دستور npm را اجرا کنید. آزمونی برای نمره‌های مساوی و نمایش دو رقم اعشار بدون تغییر مدل اضافه کنید. در توسعهٔ فیلتر گروه، میانگین را با برچسب «نتایج فیلترشده» نشان دهید. کمک‌مرجع: #array، #function و #validation-contracts .

منابع بررسی و مطالعهٔ بیشتر

Node.js 24 — Test runner: https://nodejs.org/docs/latest-v24.x/api/test.html
MDN — Array.sort، قرارداد مقایسه و پایداری: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
MIT 6.0001 — Testing و Decomposition: https://ocw.mit.edu/courses/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/pages/lecture-slides-code/
تألیف، کد و پاسخ‌های مستقل: تحریریه درس‌آوند. داده‌ها ساختگی‌اند؛ آستانه و محدودیت‌ها برای همین تمرین تعریف شده‌اند.

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