برنامه سری فیبوناچی در ج

سری Fibonacci با گرفتن مبلغ دو شماره قبلی در این سری بدست می آید ، با توجه به اینکه اصطلاحات اول و دوم به ترتیب 0 و 1 هستند. سری Fibonacci توسط f (n) = f (n-1) + f (n-2) f (n) = f (n-1) + f (n-2) f (n) = f (n) نشان داده شده است.- 1) + F (n - 2). سری 0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34. به عنوان سری Fibonacci شناخته می شود.

محدوده

• در این مقاله ، ما خواهیم فهمید که سری Fibonacci چیست و چگونه سری Fibonacci شکل می گیرد.
• ما برنامه هایی را برای یافتن سری فیبوناچی در C با استفاده از بازگشت و بدون بازگشت جستجو خواهیم کرد.
• ما در مورد پیچیدگی زمان و فضایی هر برنامه برای یافتن سری Fibonacci در C بحث خواهیم کرد.

سری فیبوناچی چیست؟

سری Fibonacci را می توان با استفاده از معادله ریاضی f (n) = f (n-1) + f (n-2) f (n) = f (n-1) + f (n-2) f (n) توصیف کرد.= f (n - 1) + f (n - 2) ، با شرط f (1) = 0 و f (2) = 1. مجموع دو عدد قبلی در دنباله تعداد بعدی دنباله است.

بگذارید ببینیم که دنباله چگونه شکل می گیرد:

رقم اول: 0 رقم دوم: 1 رقم سوم: رقم اول + رقم دوم: (0+1) = 1 رقم چهارم: رقم دوم + رقم سوم: (1+1) = 2 رقم پنجم: رقم چهارم + رقم سوم: (2+1) = 3 رقم ششم: رقم پنجم + رقم چهارم: (3+2) = 5و غیره 

سری فیبوناچی در ج

اکنون می دانیم که سری Fibonacci چیست و دنباله چگونه شکل می گیرد. بگذارید یک برنامه C را برای یافتن سری Fibonacci اجرا کنیم. سری Fibonacci در C می تواند با استفاده از بازگشت یا بدون استفاده از بازگشت اجرا شود. بگذارید به روشهای مختلف اجرای سری فیبوناچی در C نگاه کنیم.

1. سری فیبوناچی در C با استفاده از بازگشت

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

در اینجا کد برای یافتن سری Fibonacci در C با استفاده از یک عملکرد بازگشتی است.

کد:

#عبارتند از در نظر گرفتن فیبر(در نظر گرفتن n)  if (n == 1) برگشت 0; // رقم اول در این سری 0 است دیگر if (n == 2) برگشت 1; // رقم دوم در این سری 1 است دیگر برگشت (فیبر (n - 1) + فیبر (n - 2)); // جمع دو شماره قبلی در این سریال شماره بعدی را در این سریال نشان می دهد> در نظر گرفتن اصلی()  در نظر گرفتن n = 5; در نظر گرفتن i; چاپی("سری فیبوناچی:  n" است); برای (من = 1؛من<= n; i++) چاپی("٪ D"، فیبر (i)) ؛>> 

خروجی:

سری Fibonacci: 0 1 1 2 3 

توضیح:

در کد فوق ، ما تابعی به نام FIB () ایجاد کردیم که دارای یک عدد صحیح به عنوان پارامتر و نوع داده بازگشت است. در عملکرد اصلی ، ما از یک حلقه از 1 تا n و در هر تکرار ، به نام FIB () استفاده می کنیم. در عملکرد فیبر () ، اگر پارامتر منتقل شده 0 یا 1 باشد ، ما همان مقدار را برمی گردانیم. در غیر این صورت ، ما مجموع تماس های بازگشتی را با مقادیر پارامتر یک و دو کمتر از پارامتر فعلی خود ، که FIB (I-1)+FIB (I-2) است ، برمی گردانیم.

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

پیچیدگی زمان و فضا روش بازگشتی

• پیچیدگی زمان کد فوق t (2^n) ، یعنی نمایی است.
• پیچیدگی فضایی کد فوق O (n) برای یک سری بازگشتی است.

توجه داشته باشید

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

2. سری فیبوناچی در C بدون بازگشت

ما در مورد نحوه اجرای سری فیبوناچی با استفاده از بازگشت بحث کردیم. سری Fibonacci در C بدون استفاده از بازگشت نیز قابل اجرا است. بگذارید روشهای مختلف اجرای سری فیبوناچی را بدون استفاده از بازگشتی بررسی کنیم.

با استفاده از برنامه نویسی پویا

در برنامه نویسی پویا ، ما تمام مقادیر قبلاً محاسبه شده از اعداد فیبوناچی را در یک آرایه ذخیره خواهیم کرد. ما می دانیم که آرایه دارای صفر است. بنابراین اعداد فیبوناچی در شاخص آرایه N-1 ذخیره می شوند. به عنوان مثال ، شماره 2 فیبوناچی در شاخص 1 آرایه ذخیره می شود.

رمز

#عبارتند از در نظر گرفتن فیبر(در نظر گرفتن n)  در نظر گرفتن arr [5]; در نظر گرفتن i; arr [0] = 0; // دوره اول صفر است arr [1] = 1; // دوره دوم یکی است برای (من = 2؛من<= n; i++) arr [i] = arr [i - 1] + arr [i - 2]; // محاسبه مجموع دو شماره فیبوناچی قبلی> برای (من = 0؛من1؛I ++)چاپی("٪ D"، arr [i]) ؛>> در نظر گرفتن اصلی()  در نظر گرفتن n = 5; چاپی("سری فیبوناچی:  n" است);فیبر (N) ؛برگشت 0;> 

خروجی

سری Fibonacci: 0 1 1 2 3 

توضیح در کد فوق ، در عملکرد اصلی () ، ما عملکرد FIB () را با N به عنوان یک پارامتر نامیدیم. مقدار n به 5 آغاز می شود.

در عملکرد فیبر () ، ما آرایه ای از اندازه N را ایجاد می کنیم ، در مورد ما ، آرایه ای از اندازه 5 برای نگه داشتن شماره های فیبوناچی. عنصر اول و دوم در آرایه به ترتیب به 0 و 1 آغاز می شود. بعداً برای یافتن عناصر دیگر آرایه یعنی اعداد فیبوناچی با استفاده از فرمول arr [i] = arr [i-1] + arr [i-2] استفاده کردیم. بعداً همه عناصر موجود در آرایه را چاپ خواهیم کرد.

پیچیدگی زمانی و پیچیدگی فضا برنامه نویسی پویا

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

روش بهینه سازی شده فضا

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

کد:

#عبارتند از در نظر گرفتن اصلی()  در نظر گرفتن a = 0; // مقدار اولیه A روی 0 تنظیم شده است در نظر گرفتن b = 1; // مقدار اولیه B روی 1 تنظیم شده است در نظر گرفتن من ، نتیجه ؛ در نظر گرفتن n = 5; چاپی("سری فیبوناچی:  n" است); برای (من = 0؛منچاپی("٪ D"، آ)؛ نتیجه = a + b ؛ // جمع دو شماره قبلی محاسبه می شود a = b; b = result;>> 

خروجی

سری Fibonacci: 0 1 1 2 3 

توضیح

اکنون که کد را دیده ایم ، اجازه دهید سعی کنیم کد را درک کنیم

• در خط 12 ، مقدار A+B را در نتیجه متغیر ذخیره می کنیم.
• در خط 13 ، مقدار B را در a ذخیره می کنیم.
• در خط 14 ، مقدار نتیجه را در b ذخیره می کنیم.
• از آنجا که کدها در داخل حلقه برای حلقه هستند ، مراحل فوق دوباره تکرار می شود تا حلقه به پایان برسد.

اگر خطوط فوق را تجزیه و تحلیل کنیم ، می توانیم آن را درک کنیم

• در ابتدا ، مقادیر A و B به ترتیب 0 و 1 بود.
• بعداً ، جمع A و B را در نتیجه ذخیره کردیم. اکنون مقدار نتیجه 1 است.
• در مرحله بعدی ، ما مقدار B را به A اختصاص می دهیم ، و اکنون یک اراده 1 دارد.
• سپس ، ما مقدار نتیجه را به B اختصاص خواهیم داد ، و اکنون B مقدار 1 را خواهد داشت.
• با ادامه حلقه. در تکرار بعدی ، مقدار نتیجه برابر با 2 خواهد بود (زیرا نتیجه = a+b). و حلقه تا زمان برآورده شدن شرایط ادامه می یابد.

پیچیدگی زمانی و پیچیدگی فضا روش بهینه سازی شده فضا

• پیچیدگی زمانی سری فیبوناچی t (n) ، یعنی خطی است. ما باید مبلغ دو اصطلاح را پیدا کنیم و بسته به ارزش n ، آن زمان تکرار می شود.
• پیچیدگی فضایی سری Fibonacci با استفاده از برنامه نویسی پویا O (1) است.

نتیجه

• با گرفتن مبلغ دو اصطلاح فیبوناچی قبلی ، شماره فیبوناچی را می توان پیدا کرد. رقم اول و دوم این سری به ترتیب به 0 و 1 ثابت است.
• سری 0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34. به عنوان سری Fibonacci شناخته می شود.
• برنامه C برای سری Fibonacci را می توان با استفاده از روش بازگشت با پیچیدگی زمانی T (2^N) و پیچیدگی فضایی T (n) یافت.
• روش برنامه نویسی پویا برای یافتن سری فیبوناچی در C دارای پیچیدگی فضایی O (n) و پیچیدگی زمان t (n) است.
• روش بهینه سازی شده فضا برای سری Fibonacci در C دارای پیچیدگی فضایی O (1) و پیچیدگی زمان t (n) است.