فاکتوریل
Factorialفاکتوریل n یا n! حاصل‌ضرب اعداد 1 تا n است و طبق تعریف 0! برابر 1 است.
اول این مفهوم را در ذهن نگه دار
فاکتوریل n یا n! حاصل‌ضرب اعداد 1 تا n است و طبق تعریف 0! برابر 1 است.
چطور کار می‌کند؟ ساده و مرحله‌ای
در جایگشت، ترکیب و فرمول‌های احتمال زیاد دیده می‌شود.
پیاده‌سازی iterative overhead recursion ندارد؛ برای n بزرگ Number خیلی زود precision را از دست می‌دهد و ممکن است BigInt لازم شود.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
خاصیت یا رابطه ریاضی را واضح بگو.
محدوده اعداد و representation را مشخص کن.
رابطه را به computation تبدیل و precision/overflow را بررسی کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای فاکتوریل هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function factorial(n) {
if (!Number.isInteger(n) || n < 0) throw new Error("n must be a non-negative integer");
let result = 1;
for (let i = 2; i <= n; i++) result *= i;
return result;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی خاصیت ریاضی می‌تواند brute force را حذف کند از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- نادیده گرفتن precision ممیز شناور یا دامنه integer.
- استفاده از فرمول خارج از فرض‌های معتبرش.
مدل یک پاسخ حرفه‌ای
base case و O(n) را بگو و برای ورودی بزرگ به overflow/precision توجه کن؛ دامنه عددی را بی‌نهایت فرض نکن.
فاکتوریل چه مسئله‌ای را حل می‌کند؟
فاکتوریل n یا n! حاصل‌ضرب اعداد 1 تا n است و طبق تعریف 0! برابر 1 است.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نادیده گرفتن precision ممیز شناور یا دامنه integer.