اعداد فیبوناچی
Fibonacci Numberدر دنباله Fibonacci هر عدد از جمع دو عدد قبلی ساخته می‌شود؛ معمولاً دنباله با 0 و 1 شروع می‌شود.
اول این مفهوم را در ذهن نگه دار
در دنباله Fibonacci هر عدد از جمع دو عدد قبلی ساخته می‌شود؛ معمولاً دنباله با 0 و 1 شروع می‌شود.
چطور کار می‌کند؟ ساده و مرحله‌ای
Recursion ساده زیرمسئله‌های یکسان را بارها حساب می‌کند و رشد نمایی دارد.
نسخه iterative فقط دو مقدار قبلی را نگه می‌دارد و به O(n) زمان و O(1) حافظه می‌رسد.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
خاصیت یا رابطه ریاضی را واضح بگو.
محدوده اعداد و representation را مشخص کن.
رابطه را به computation تبدیل و precision/overflow را بررسی کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای اعداد فیبوناچی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function fibonacci(n) {
let a = 0, b = 1;
for (let i = 0; i < n; i++) {
[a, b] = [b, a + b];
}
return a;
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(n) iterative / O(2ⁿ) naive recursion
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی خاصیت ریاضی می‌تواند brute force را حذف کند از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- نادیده گرفتن precision ممیز شناور یا دامنه integer.
- استفاده از فرمول خارج از فرض‌های معتبرش.
مدل یک پاسخ حرفه‌ای
Fibonacci مثال خوبی برای overlapping subproblem، memoization و تفاوت recursion زیبا با recursion کارآمد است.
اعداد فیبوناچی چه مسئله‌ای را حل می‌کند؟
در دنباله Fibonacci هر عدد از جمع دو عدد قبلی ساخته می‌شود؛ معمولاً دنباله با 0 و 1 شروع می‌شود.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(n) iterative / O(2ⁿ) naive recursion است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نادیده گرفتن precision ممیز شناور یا دامنه integer.