فیبوناچی برگشته است

دنباله اعداد فیبوناچی فرمول F است_n = F_n-1 + F_n-2بشربه عبارت دیگر ، شماره بعدی مجموع دو مورد قبلی است.

ابتدا دو عدد 1 ، سپس 2 (1+1) ، سپس 3 (1+2) ، 5 (2+3) و غیره: 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21.

اعداد فیبوناچی مربوط به نسبت طلایی و بسیاری از پدیده های طبیعی در اطراف ما است.

یک فیبر تابعی (N) بنویسید که شماره N-Th Fibonacci را برمی گرداند.

نمونه ای از کار:

عملکرد فیبر (N)هشدار (فیبر (3)) ؛// 2 هشدار (فیبر (7)) ؛// 13 هشدار (FIB (77)) ؛// 552793970084757

پ. عملکرد باید سریع باشد. تماس با فیبر (77) نباید بیش از کسری از ثانیه طول بکشد.

راه حل

اولین راه حلی که می توانیم در اینجا امتحان کنیم ، نسخه بازگشتی است.

اعداد فیبوناچی با تعریف بازگشتی هستند:

عملکرد فیبر (N)

... اما برای مقادیر بزرگ N بسیار کند است. به عنوان مثال ، FIB (77) ممکن است موتور را برای مدتی آویزان کند و تمام منابع CPU را بخورد.

این به این دلیل است که این عملکرد خرده فروشی های زیادی را ایجاد می کند. همان مقادیر دوباره و دوباره ارزیابی می شوند.

به عنوان مثال ، بیایید یک قطعه از محاسبات برای FIB (5) را ببینیم:

بشرفیبر (5) = فیبر (4) + فیبر (3) فیبر (4) = فیبر (3) + فیبر (2). 

در اینجا می توانیم ببینیم که مقدار فیبر (3) برای هر دو فیبر (5) و فیبر (4) لازم است. بنابراین فیبر (3) دو بار کاملاً مستقل فراخوانی و ارزیابی می شود.

در اینجا درخت کامل بازگشت:

ما به وضوح می توانیم توجه کنیم که فیبر (3) دو بار ارزیابی می شود و فیبر (2) سه بار ارزیابی می شود. مقدار کل محاسبات بسیار سریعتر از N رشد می کند و حتی برای N = 77 آن را بسیار زیاد می کند.

ما می توانیم با به یاد آوردن مقادیر ارزیابی شده از قبل بهینه سازی کنیم: اگر یک مقدار Say FIB (3) یک بار محاسبه شود ، می توانیم فقط در محاسبات آینده از آن استفاده مجدد کنیم.

نوع دیگر این است که از بازگشت و استفاده از یک الگوریتم کاملاً متفاوت مبتنی بر حلقه استفاده کنید.

به جای رفتن از n به پایین به مقادیر پایین ، می توانیم حلقه ای را تهیه کنیم که از 1 و 2 شروع شود ، سپس به عنوان مبلغ آنها ، فیبر (3) دریافت می شود ، سپس فیبر (4) به عنوان مجموع دو مقدار قبلی ، سپس فیبر (5)و بالا و بالا می رود ، تا زمانی که به مقدار مورد نیاز برسد. در هر مرحله فقط باید دو مقدار قبلی را به خاطر بسپاریم.

در اینجا مراحل الگوریتم جدید در جزئیات آورده شده است.

// a = fib (1) ، b = fib (2) ، این مقادیر با تعریف 1 اجازه می دهند a = 1 ، b = 1 ؛// دریافت c = فیبر (3) به عنوان مبلغ آنها اجازه می دهد c = a + b ؛/ * اکنون ما فیبر (1) ، فیبر (2) ، فیبر (3) a b c 1 ، 1 ، 2 */

اکنون می خواهیم فیبر (4) = فیبر (2) + فیبر (3) را بدست آوریم.

بیایید متغیرها را تغییر دهیم: A ، B فیبر (2) ، فیبر (3) و C جمع خود را دریافت می کند:

a = b ؛// اکنون a = fib (2) b = c ؛// اکنون b = fib (3) c = a + b ؛// c = فیبر (4)/ * اکنون دنباله ای داریم: A B C 1 ، 1 ، 2 ، 3 */

مرحله بعدی شماره دنباله دیگری را نشان می دهد:

a = b ؛// اکنون a = fib (3) b = c ؛// اکنون b = fib (4) c = a + b ؛// c = فیبر (5)/ * اکنون دنباله (یک عدد دیگر) است: A B C 1 ، 1 ، 2 ، 3 ، 5 */

... و غیره تا زمانی که ارزش لازم را بدست آوریم. این بسیار سریعتر از بازگشت است و هیچ محاسباتی کپی را شامل نمی شود.

عملکرد فیبر (N)هشدار (فیبر (3)) ؛// 2 هشدار (فیبر (7)) ؛// 13 هشدار (FIB (77)) ؛// 552793970084757

حلقه با i = 3 شروع می شود ، زیرا مقادیر دنباله اول و دوم در متغیرهای a = 1 ، b = 1 کدگذاری می شوند.< Pan> مرحله بعدی شماره دنباله دیگری را ارائه می دهد: