مسئله نردبان / پله‌ها (Staircase problem)
چند روش وجود دارد که 1000 پله رو بری بالا؟
نکته: در هر مرحله فقط میتونی یک پله یا دو پله بری بالا
جواب:
برای درک بهتر تعداد پله رو ابتدا 4 تا در نظر میگیریم و سپس مسئله را تعمیم میدهیم برای اینکه بتوانیم 4 تا پله رو بریم جلو چند راه وجود دارد: راه اول= 1+1+1+1 -> هربار یه پله راه دوم= 1+1+2 راه سوم= 1+2+1 راه چهارم=2+1+1 راه پنجم= 2+2
5 راه وجود دارد تا بتوانیم 4 تا پله رو بریم بالا
برای اینکه به پله 4 برسی آخرین کاری که کردی یه پله اومدی بالا (از پله 3 رسیدی) دو پله اومدی بالا (از پله 2 رسیدی) پس اگه بدونی چند راه هست برای رسیدن به پله 3 و چند راه هست برای رسیدن به پله 2 با جمع اینا میتونی بفهمی چند راه برای رسیدن به 4 پله وجود دارد. f(4)=f(3)+f(2)
برای رسیدن به 1000 پله از فرمول f(n)=f(n-1)+f(n-2) استفاده می کنیم.
این فرمول جمع مقادیر قبلی تابع است یعنی دنباله فیبوناچی
f(1)=f(1)=1
f(2)= f(1)+f(0)=1+1=2
f(3)= f(2)+f(1)= f(1)+f(0) + f(1)=1+1=2
f(4)=f(3)+f(2)=f(2)+f(1) + f(1)+f(0)=f(1)+f(0)+f(1) + f(1)+f(0)=3+2=5
توجه: f(0)=1 هیچ کاری نکنی