یافتن n امین عدد فیبوناچی با برنامه نویسی پویا

به نام خدا

سلام خدمت امیگویی های عزیز. با یه مقاله دیگه از پایتون

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

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

احتمال داره شما با کد زیر این کار رو بکنید:

num = int(input("Enter n: "))

def fibo(num):
  if num == 1:
    return 0
  elif num == 2:
    return 1
  return fibo(num-1)+fibo(num-2)

print(fibo(num))

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

برنامه چون فیبو 5 رو نمی دونه میره سراغ فیبو 4

برنامه چون فیبو 4 رو نمی دونه میره سراغ فیبو 3

برنامه چون فیبو 3 رو نمی دونه میره سراغ فیبو 2

برنامه فیبو 2 رو می دونه پس فیبو 3 رو هم محاسبه می کنه

برنامه باز میره سراغ 5. چون فیبو 5 رو نمی دونه میره سراغ فیبو 4

برنامه چون فیبو 4 رو نمی دونه میره سراغ فیبو 3

برنامه فیبو 3 رو می دونه پس فیبو 4 رو محاسبه می کنه

برنامه باز میره سراغ 5. چون فیبو 5 رو نمی دونه میره سراغ فیبو 4

برنامه فیبو 4 رو می دونه پس فیبو 5 رو محاسبه می کنه و اون رو برمی گردونه.

دیدید پروسه چقدر طولانی بود؟ تصور کنید ورودی عددی مثل 100 باشه. در این صورت چند دقیقه یا چند ساعت طول میکشه تا پاسخ به دست بیاد.

پس ما باید از الگوریتمی سریع تر استفاده کنیم. من اینجا از الگوریتم پویااستفاده می کنم.

الگوریتم پویا یعنی به جای چند بار اومدن از آخر به اول (مثل کد بالا)، یک بار از اول به آخر بریم.

یعنی:

برنامه چون 2 رو میدونه 3 رو محاسبه می کنه

برنامه چون 3 رو میدونه 4 رو محاسبه می کنه

برنامه چون 4 رو میدونه 5 رو محاسبه می کنه

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

البته من فقط محتویات داخل تابع fibo رو می نویسم. یعنی باید کد اول رو بنویسید ولی به جای محتویات داخل تابع fibo، کد زیر رو ینویسید:

fibos = [0, 1]
if num <= len(fibos): return fibos[num-1]
  while len(fibos) != num:
    fibos.append(fibos[-1]+fibos[-2])
  return fibos[-1]

توضیح کد بالا:

خط 1: دو عضو اول الگو رو توی یه لیست ذخیره کردم.

خط 2: گفتم اگه تعداد اعضای لیست fibos کوچکتر یا مساوی ورودی باشه (یعنی ورودی 1 یا 2 باشه)، عضو ورودی منهای 1 ام fibos رو برگردون. منهای 1 برای اینه که الگو ها در ریاضی از n=1 شروع میشن ولی تو برنامه نویسی از 0

خط 3 و 4: گفتم تا زمانی که تعداد اعضای الگو برابر ورودی نشده، فیبوی 2 عضو آخر لیست رو با هم جمع کن و به لیست اضافه کن.

خط 5: گفتم عضو آخر لیست رو (که n مین عضو فیبوناچی هست) برگردون.

این کد هم کوتاه تر و هم سریع تر از کد اول هست.

مقایسه زمان یافتن پاسخ این 2 کد:

ورودی                                         الگوریتم اول                                 الگوریتم دوم

10                                               ناچیز                                            ناچیز

40                                              حدود 25 ثانیه                               ناچیز

100                                             نتونستم منتظر بمونم                     ناچیز

300000                                      نتونستم منتظر بمونم                     حدود 2.5 ثانیه

عبارت "ناچیز" یعنی کمتر از 10 صدم ثانیه

می بینید که سرعت این 2 قطعه کد قابل مقایسه نیست. سرعت کد دوم هزاران برابر کد اول هست.

برای مطالعه بیشتر دربارۀ برنامه نویسی پویا می تونین به اینجا سر بزنین.

ممنون از مطالعه این مقاله