دنباله اعداد فیبوناچی

[Son of anarchy]

فکر می کنید به چند طریق می‌توانید از یک پلکان که دارای n پله است، بالا بروید، در صورتی که در هر گام فقط بتوانید یک یا دو پله را طی کنید؟ برای یافتن پاسخ این مسأله، ابتدا یک حالت ساده را در نظر می‌گیریم. فرض کنید که پلکان چهار پله دارد. شما می‌توانید با چهار گام کوچک ( یک پله ای ) مسیر را طی کنید و یا این که دو گام بزرگ ( دو پله ای ) یا یک گام بلند و دو گام کوچک بردارید. کلیه ی حالت های ممکن در شکل زیر نمایش داده شده است. پله هایی که با علامت مشخص شده اند، پله هایی هستند که روی آن قدم گذاشته اید.

دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.


در واقع این مسأله را با یک استراتژی بسیار ساده می‌توان حل کرد. کافی است مسأله را کمی کوچک یاساده کنیم. آخرین گام یک گام کوچک یا یک گام بزرگ است. در واقع تعداد راه هایی که می‌توان پلکان را طوری طی کرد که به پله ماقبل آخر رسید، حل مسأله برای یک پله کم تر ( n-1 پله ) است و تعداد راه هایی که می‌توان از آن به دو پله پایین تر رسید، حل مسأله برای دو پله کم تر ( n-2 پله ) خواهد بود. در مثال بالا سه مسیر مختلف وجود دارد که به پله ی سوم می‌رسد و دو مسیر وجود دارد که به پله ی دوم منتهی می‌شود. حال باید مسأله را برای این دو حالت کوچک تر حل کنیم. ما دوباره هر یک از این دو حالت را به حالات کوچک تر مشابه تقسیم می‌کنیم. این روش را "حل بازگشتی " می‌نامند. در واقع ما هر بار مسأله را به مسأله ای شبیه خودش - اما کوچک تر از آن - تبدیل می‌کنیم. تعداد کل مسیرها برابر مجموع مسیرهایی که به پله ی ماقبل آخر رسیده و همین طور مسیرهایی که به دو پله قبل از پله ی آخر منتهی شده اند، می‌باشد. می‌توانید بگویید چرا؟
اگر همین طور مسأله را به مسأله های کوچک تر تقسیم کنیم، در پایان به جایی می‌رسیم که حل آن برای ما بسیار ساده است: به چند طریق می‌توان دو پله را طی کرد؟ و پس از حل آن، دوباره مسیری را که برای حل مسأله طی کرده ایم، باز می‌گردیم.

دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.


این مسأله را می‌توان با دنباله ی اعداد فیبوناچی نیز حل کرد. دنباله ی فیبوناچی یک دنباله ی بازگشتی است که در آن اعداد اول و دوم برابر یک می‌باشند. هر عدد این دنباله از جمع کردن دو عدد قبلی به دست می‌آید.
چند عدد ابتدایی این دنباله عبارتند از:.... و 13و 8 و 5 و 3 و 2 و 1 و 1، چون:
...و13=5+8 و 8=3+5 و 5=2+3 و 3=1+2 و 2=1+1

اگر عدد n ام این دنباله را با fn نشان دهیم، آن گاه می‌توان دنباله را با فرمول بازگشتی زیر مشخص نمود:
fn=fn-1+fn-2 , f1=1 , f2=1
اگر دقت کنید متوجه می‌شوید که f1 دقیقاً برابر تعداد راه های ممکن برای بالا رفتن از یک پله، f2 برابر راه های ممکن برای دو پله و به همین ترتیب fn تعداد مسیرهای ممکن برای رسیدن به بالای یک پلکان n تایی است.
علامت سوالآیا می‌توانید توضیح دهید که چرا تساوی بالا برقرار است؟
مسائل بسیاری را می‌توان با استفاده از دنباله ی اعداد فیبوناچی حل نمود. این دنباله در سال 1202 میلادی توسط یک ایتالیایی به نام " لئوناردو فیبوناچی " (Leonardo Fibonacci) ابداع شد. در واقع او در جستجوی راه حل یک مسأله بود. مسأله به این صورت است که :
" اگر هر جفت خرگوش در هر ماه یک جفت خرگوش جدید به دنیا بیاورند و خرگوش های جدید نیز پس از گذشت یک ماه، به دوران باروری برسند ( با فرض این که هیچ خرگوشی نمیرد )، تعداد خرگوش ها را در ماه n ام به دست آورید. "

دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.




بعدها، یوهان کپلر (Johannes Kepler) خاصیت جالب دیگری از این دنباله را کشف کرد. او نسبت دو جمله ی متوالی این دنباله را محاسبه نمود و متوجه شد که این نسبت به عدد فیبوناچی نزدیک می‌شود. این نسبت، عددی شناخته شده بود که " عدد طلایی " نامیده می‌شد.
علامت سوالدر مورد عدد طلایی و خواص آن تحقیق کنید .
اعداد فیبوناچی را در بسیاری از موارد طبیعی نیز می‌توانید مشاهده کنید. آرایش برگ‌ها و گل های بسیاری از گیاهان به صورت دو پیچه (spiral) است. معمولاً تعداد پیچه های ساعت گرد با تعداد پیچه های پادساعت گرد تفاوت دارد. این دو عدد در اغلب مواقع دو عدد متوالی از رشته ی فیبوناچی هستند. به شکل زیر توجه کنید:

دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.


دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.