برنامه ای برای اعداد فیبوناچی با مثال

دنباله فیبوناچی بدون شک یکی از معروف ترین دنباله های ریاضی تمام دوران است. ریاضیدانان و دانشمندان قرن هاست که از این دنباله در ریاضیات و علوم استفاده می کنند و نام آن را به نام ریاضیدان مشهور ایتالیایی قرون وسطی، فیبوناچی، می گذارند.

دنباله فیبوناچی مجموعه ای از اعداد است که هر عدد بعدی مجموع دو عدد قبلی است که از 0 و 1 شروع می شود. این دنباله اغلب با Fn نشان داده می شود و به این صورت است:، 8، 13، 21، 34، 55، 89، 144، 233 و غیره.

اما مسئله مهم چیست؟چرا باید به دنباله فیبوناچی اهمیت دهیم؟خوب، معلوم می شود که این دنباله فقط یک سری اعداد دلخواه نیست.

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

زبان های برنامه نویسی مانند پایتون دارای توابع داخلی برای تولید دنباله فیبوناچی هستند. اگر به درک الگوریتم های پشت این توابع علاقه دارید، به دنبال آن باشید، زیرا این مقاله 7 الگوریتم اصلی و روش مورد استفاده برای تولید اعداد فیبوناچی را توضیح می دهد.

روش های مختلف ایجاد برنامه برای اعداد فیبوناچی

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

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

بازگشت

بازگشت روشی برای حل یک مسئله است که در آن راه حل به راه حل های نمونه های کوچکتر همان مسئله بستگی دارد. در زمینه دنباله فیبوناچی، راه حل بازگشتی با شکستن مسئله یافتن عدد فیبوناچی n به دو مسئله کوچکتر کار می کند: پیدا کردن (n-1)امین عدد فیبوناچی و یافتن (n-2)امین عدد فیبوناچی.

این فرآیند به صورت بازگشتی ادامه می یابد تا زمانی که به حالت پایه برسد، جایی که n 0 یا 1 است. پس از برآورده شدن، تابع به سادگی n را برمی گرداند. برای همه مقادیر دیگر n، تابع به صورت بازگشتی خود را فراخوانی می کند و n-1 و n-2 را به عنوان آرگومان/پارامتر ارسال می کند.

مثال زیر یک برنامه پایتون ساده را نشان می دهد که برای تولید اعداد فیبوناچی ، بازگشت را اجرا می کند:

اگر n n) ، همانطور که عملکرد خود را برای هر مقدار n دو برابر می کند.

این با بزرگتر شدن N به سرعت ناکارآمد می شود و این روش را برای مقادیر بزرگتر n غیر عملی می کند. پیچیدگی فضا o (n) است که خطی است ، زیرا حداکثر عمق درخت بازگشتی n است.

تکرار

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

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

ما می توانیم یک برنامه ساده را با استفاده از تکرار برای ایجاد شماره های فیبوناچی به روش زیر پیاده سازی کنیم:

برای من در محدوده (2 ، n+1):

FIB = FIB1 + FIB2

fib1 ، fib2 = fib2 ، fib

در اینجا ، ما از یک حلقه برای محاسبه شماره فیبوناچی N-Th در زمان خطی استفاده می کنیم. ما با شروع دو عدد اول در دنباله (0 و 1) و محاسبه شماره بعدی به عنوان مبلغ دو قبلی ، این کار را می کنیم.

ما دو شماره قبلی را در متغیرها پیگیری می کنیم و آنها را در هر تکرار به روز می کنیم. بعد از تکرار N ، شماره N-Th را برمی گردانیم.

پیچیدگی زمانی محلول تکراری o (n) است که خطی است. این امر به این دلیل است که برای حلقه N-1 بار برای محاسبه شماره فیبوناچی نهم اجرا می شود. از آنجا که این تابع فقط از تعداد ثابت متغیرها برای محاسبه شماره فیبریاچی نهم استفاده می کند ، پیچیدگی فضایی آن O (1) است که ثابت است.

یادبود

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

در زمینه دنباله فیبوناچی ، راه حل MEMOISINATION با ذخیره راه حل های زیر برنامه ها و بازگرداندن نتیجه ذخیره شده ، در صورت وجود کار می کند.

به این ترتیب ، این برنامه فقط یک بار راه حل برای هر یک از زیرگروه ها را محاسبه می کند و در صورت لزوم از آن استفاده می کند.

در اینجا نمونه ای از اجرای Memoization:

def fibonacci (n ، memo =<>):