فیبوناچی در پایتون
دنباله فیبوناچی یک دنباله بسیار معروف از اعداد صحیح است. در این آموزش، شما بر یادگیری دنباله فیبوناچی در پایتون تمرکز خواهید کرد.
شروع کار با دنباله فیبوناچی
لئوناردو فیبوناچی ریاضیدان ایتالیایی بود که توانست به سرعت پاسخی به این سوال که امپراتور فردریک دوم از سوابیا پرسیده بود ارائه دهد: «در یک سال چند جفت خرگوش به‌دست می‌آیند، به استثنای موارد مرگ و میر، با این فرض که هر زوج زوج دیگری را به دنیا می‌آورند که هر ماه زوج می‌شوند و اینکه جوان‌ترین زوج‌ها می‌توانند در ماه دوم زندگی تولید مثل کنند؟»
پاسخ به ترتیب زیر بود:
رابطه فیبوناچی که با 0 شروع می شود ، این الگو پس از دو عدد اول، 0 و 1 شروع می شود، جایی که هر عدد در دنباله همیشه مجموع دو عدد قبل از خود است. ریاضیدانان هندی از قرن ششم درباره این دنباله می دانستند و فیبوناچی از آن برای محاسبه رشد جمعیت خرگوش استفاده کرد.
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
در اصطلاحات ریاضی، این رابطه را یک رابطه تکراری می نامند، به این معنی که هر جمله از دنباله (فراتر از 0 و 1) تابعی از عبارت های قبلی است. همچنین نسخه‌ای از دنباله وجود دارد که در آن دو عدد اول هر دو 1 هستند، مانند دنباله فیبوناچی که با 11 شروع می شود . برای اهداف این آموزش، از نسخه‌ای از دنباله استفاده خواهید کرد که با 0 شروع می‌شود.
بررسی بازگشت در دنباله فیبوناچی
ایجاد دنباله فیبوناچی یک مسئله بازگشتی کلاسیک است. بازگشت زمانی است که یک تابع به خود ارجاع می دهد تا مشکلی را که می خواهد حل کند را تجزیه کند. در هر فراخوانی تابع، مشکل کوچکتر می شود تا زمانی که به یک مورد اصلی برسد، پس از آن نتیجه را به هر تماس گیرنده میانی برمی گرداند تا زمانی که نتیجه نهایی را به تماس گیرنده اصلی برگرداند.
اگر می‌خواهید عدد F(5) فیبوناچی را محاسبه کنید، ابتدا باید پیشینیان آن، F(4) و F(3) را محاسبه کنید. و برای محاسبه F(4) و F(3)، باید پیشینیان آنها را محاسبه کنید.
ایجاد توالی بازگشتی فیبوناچی در پایتون
رایج‌ترین الگوریتم برای تولید دنباله فیبوناچی از شما می‌خواهد که یک تابع بازگشتی را کدنویسی کنید که تا زمانی که عدد فیبوناچی مورد نظر را محاسبه کند، هر چند بار که لازم است خود را فراخوانی کند.
def fibonacci_of(n):
if n in {0, 1}:
return n
return fibonacci_of(n – 1) + fibonacci_of(n – 2)
[fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
در داخل fibonacci_of()، ابتدا حروف پایه را بررسی می کنید. سپس مجموع مقادیر حاصل از فراخوانی تابع را با دو مقدار قبلی n برمی گردانید . با بزرگتر شدن n، محاسبه سنگین تر و سنگین تر می شود. در نتیجه زمان مورد نیاز برای حل مسئله به صورت تصاعدی افزایش می یابد زیرا تابع ، بسیاری از مسائل فرعی یکسان را بارها و بارها محاسبه می کند.
توجه: این تابع را در سیستم خانگی خود با عددی بزرگتر از 50 امتحان نکنید. بسته به سخت افزار خود، ممکن است مدت زیادی منتظر بمانید تا آن را به پایان برسانید.
برای محاسبه(15) F، fibonacci_of باید خود را پانزده بار فراخوانی کند. برای محاسبه F(n)، حداکثر عمق درخت فراخوانی n است و از آنجایی که هر فراخوانی تابع دو فراخوانی تابع اضافی ایجاد می کند، پیچیدگی زمانی این تابع بازگشتی O(2n) است.
بهینه سازی الگوریتم بازگشتی برای دنباله فیبوناچی در پایتون
حداقل دو تکنیک وجود دارد که می توانید برای کارآمدتر کردن الگوریتم برای تولید دنباله فیبوناچی استفاده کنید . به عبارت دیگر، برای اینکه محاسبه آن زمان کمتری بگیرد این تکنیک‌ها تضمین می‌کنند که شما بارها و بارها مقادیر یکسان را محاسبه نمی‌کنید.
به خاطر سپردن الگوریتم بازگشتی
همانطور که در کد بالا مشاهده کردید، تابع فیبوناچی چندین بار با ورودی یکسان خود را فراخوانی می کند. به جای تماس جدید هر بار، می توانید نتایج تماس های قبلی را در چیزی مانند حافظه پنهان ذخیره کنید. می توانید از لیست پایتون برای ذخیره نتایج محاسبات قبلی استفاده کنید. این تکنیک را به خاطر سپردن می نامند.
با به خاطر سپردن ، فقط باید یک بار پس از بازگشت از کیس پایه، درخت فراخوانی عمق n را به سمت بالا طی می کند، زیرا تمام مقادیر محاسبه شده قبلی از حافظه پنهان بازیابی می شوند. حتی برای موارد پایه، می‌توانید فراخوانی F(0) و F(1) را با بازیابی مستقیم مقادیر از حافظه پنهان در اندیس‌های 0 و 1 جایگزین کنید، بنابراین به جای پانزده بار، فقط شش بار تابع را فراخوانی می‌کنید!
در اینجا ترجمه احتمالی این بهینه سازی به کد پایتون آمده است:
cache = {0: 0, 1: 1}
def fibonacci_of(n):
if n in cache:
return cache[n]
cache[n] = fibonacci_of(n – 1) + fibonacci_of(n – 2)
return cache[n]
در این مثال، شما از دیکشنری پایتون برای ذخیره اعداد فیبوناچی محاسبه شده استفاده می کنید. ابتدا، حافظه پنهان حاوی مقادیر آغازین دنباله فیبوناچی، 0 و 1 است. در داخل تابع، ابتدا بررسی کنید که آیا عدد فیبوناچی برای مقدار ورودی فعلی n در حافظه پنهان است یا خیر. اگر چنین است، پس شماره را برمی گردانید.
اگر هیچ عدد فیبوناچی برای مقدار فعلی n وجود نداشته باشد، آنگاه آن را با فراخوانی ()fibonacci_of به صورت بازگشتی و به‌روزرسانی حافظه پنهان محاسبه می‌کنید. مرحله آخر بازگرداندن عدد فیبوناچی درخواستی است.
ایجاد دنباله فیبوناچی در پایتون
اکنون که اصول اولیه نحوه تولید دنباله فیبوناچی را می‌دانید، وقت آن است که عمیق‌تر بروید و راه‌های مختلف پیاده‌سازی الگوریتم را در پایتون را بیشتر بررسی کنید. در بخش بعدی، نحوه پیاده‌سازی الگوریتم مختلف برای تولید دنباله فیبوناچی با استفاده از برنامه‌نویسی شی‌گرا را بررسی خواهیم کرد.
استفاده از یک کلاس پایتون
مزیت استفاده از کلاس نسبت به تابع بازگشتی حافظه‌دار که قبلاً مشاهده کردید این است که یک کلاس حالت و رفتار (کپسوله‌سازی) را با هم در یک شی نگه می‌دارد. در مثال تابع، cache یک شی کاملا مجزا است، بنابراین کنترلی روی آن ندارید.
class Fibonacci:
def __init__(self):
self.cache = [0, 1]
def __call__(self, n):
if not (isinstance(n, int) and n >= 0):
raise ValueError(f’Positive integer number expected,got “{n}”‘)
if n < len(self.cache):
return self.cache[n]
else:
fib_number = self(n – 1) + self(n – 2)
self.cache.append(fib_number)
return self.cache[n]
نتیجه
دنباله فیبوناچی می تواند به شما در بهبود درک بازگشت و توابع بازگشتی در پایتون کمک کند. در این آموزش، شما یاد گرفتید که دنباله فیبوناچی چیست. شما همچنین در مورد برخی از الگوریتم های رایج برای تولید دنباله فیبوناچی در پایتون و نحوه ترجمه آنها به کد پایتون یاد گرفته اید. دنباله فیبوناچی می تواند یک سکوی پرشی عالی و نقطه ورود به دنیای توابع بازگشتی در پایتون باشد، که یک مهارت اساسی برای یک برنامه نویس است.
همچنین بخوانید : پیدا کردن اعداد اول با پایتون