برنامه نویسی پویا با مثال (یافتن n امین عدد فیبوناچی) - قسمت 2

به نام خدا

سلام خدمت دوستان عزیز امیگویی

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

اول یه نگاهی به کد نهایی قسمت قبل بندازیم:

num = int(input("Enter n: ")) 
fibos = [0, 1] 
def fibo(num):
    if num <= len(fibos): return fibos[num-1]
    while len(fibos) != num:
        fibos.append(fibos[-1]+fibos[-2])
    return fibos[-1] print(fibo(num))

توضیح کد هم که تو قسمت قبل موجوده و می تونین ببینین.

حالا می خوایم کاری کنیم که خوانایی و سرعت کد افزایش پیدا کنه. برای این کار if رو از اول تابع حذف می کنیم و تو حلقه while تغییراتی می دیم (فقط محتویات داخل تابع رو می نویسم):

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

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

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

خط 3: لیست fibos رو برگردون

این کد کوتاه تره و خوانایی بیشتری داره. در ضمن به دلیل نبودن if، سرعتش هم بیشتره.

مثال:

کاربر عدد 10 رو وارد می کنه. فرآیند محاسبه به این شکل هست:

1- چون تعداد اعضای fibos دو هست و کوچک تر از 10 (ورودی) هست، دو عضو آخر fibos رو جمع می کنه و به fibos، append می کنه.

2- باز بررسی می کنه و می بینه تعداد اعضای fibos، سه هست و باز هم کمتر از 10 هست. پس دوباره دو عضو آخر fibos رو با هم جمع می کنه و به این لیست append می کنه.

.

.

.

10- بررسی می کنه و می بینه تعداد اعضای لیست fibos، یازده هست و کوچکتر یا مساوی 10 نیست. حلقه while تموم میشه و تابع، لیست fibos رو بر می گردونه.

نکته: ما تو قسمت قبل، عضو آخر fibos رو بر می گردوندیم ولی فکر کردم شاید بهتر باشه کل لیست رو بر گردونیم ولی فقط عضو آخر رو چاپ کنیم. اینطوری کار های بیشتری میشه با این برنامه انجام داد.

بهبود بیشتر (اختیاری):

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

مکانیزم این روش اینطوریه که کاربر مثلا عدد 100000 رو به عنوان ورودی میده. برنامه تا 100000 محاسبه می کنه و عضو آخر رو نمایش می ده. حالا کاربر عدد 150000 رو وارد می کنه. این بار برنامه دیگه تا 100000 رو محاسبه نمی کنه و از 100000 تا 150000 رو محاسبه می کنه. اینطوری سرعت به شکل قابل توجهی بالا می ره ولی کمی حافظه بیشتری مصرف می شه. بریم سراغ کد (تابع fibo تغییر نمی کنه):

while True:
    num = int(input("==> "))
    fibos = fibo(num)
    print(fibos[-1])
توضیح کد بالا:

خط 1: تا ابد (اگه این رو نذارین و برنامه متوقف بشه، بار دیگه که برنامه رو اجرا می کنین، بازم همه چیز از اول اتفاق می افته.)

خط 2: دریافت ورودی به صورت int

خط 3: fibos رو برابر لیست خروجی تابع fibo قرار می دیم

خط 4: عضو آخر fibos رو چاپ می کنیم

تو این قطعه کد، همواره fibos آپدیت میشه و به همین دلیل لازم نیست هر بار از اول محاسبه انجام بشه.

امیدوارم این مقاله براتون کاربردی بوده باشه :)