تمرین 12: تابع فیبوناچی با برنامه نویسی دینامیک

یکی از همکاران شما از تمرین 10 و 11 در حال استفاده از الگوریتم فیبوناچی بازگشتی شما بود که متوجه می شود این الگوریتم برای محاسبه ی اعداد بزرگ فیبوناچی بسیار کند عمل می کند! همکار شما در خفا از شما می خواهد که یک تابع جدید بنویسید که بتواند اعداد بزرگ دنباله ی فیبوناچی را سریع تر محاسبه کند و به خوانایی تابع بازگشتی باشد!

در این تمرین از برنامه نویسی دینامیک استفاده می کنیم تا از ناکارآمدی های حلقه های بازگشتی جلوگیری کنیم. مراحل زیر را دنبال کنید تا این تمرین را به پایان برسانید:

1- فایل fibonacci.py را از تمرین قبل مجددا باز کنید.

2- یک تابع به نام fibonacci_dynamic ایجاد کنید که یک آرگومان positional دریافت می کند که نمایانگر المان مورد نظر از دنباله است. یک دیکشنری نیز در کنار این تابع ایجاد کنید تا در صورت محاسبه ی هر المان دنباله ی فیبوناچی توسط fibonacci_dynamic ، شماره و مقدار آن را به عنوان کلید و مقدار در دیکشنری قرار دهید.

3- تابع fibonacci_dynamic را بررسی کنید!

دقت کنید که محاسبه ی المان 10000ام دنباله ی فیبوناچی با تکرار و یا بازگشت میتواند بسیار به طول بیانجامد اما محاسبه ی آن به صورت دینامیک سریع ترین حالت ممکن برای رسیدن جواب است.

البته برنامه نویسی دینامیک منجر به مصرف بیشتر حافظه می شود.