اعداد فیبوناچی
محاسبه جمله n ام از سری اعداد فیبوناچی
using System;
namespace Fibonacci
class Program
try
static void Main(string[] args)
int n = Convert.ToInt32(Console.ReadLine());
if (n < 1) < Console.WriteLine(“Input Number is less than 1”); >
else
Console.WriteLine(Fib(n));
>
catch (Exception exception)
Console.WriteLine(“Erorr:t”+exception.Message);
>
>
public static int Fib(int n)
if (n return اعداد فیبوناچی n;
>
else
return Fib(n – 1) + Fib(n – 2);
>
اعداد فیبوناچی
>
>
>
ارسال یک پاسخ
شما برای افزودن نظر جدید یا باید وارد شوید یا اینکه ثبت نام کنید. ورود ثبت نام
سری اعداد فیبوناچی
چنان‌که در ویکی‌پدیا آمده، فیبوناچی نام ریاضیدان ایتالیایی است که در مسابقات سال 1225 برای حل مساله مطرح شده راه‌حلی ارائه داد که جواب آن سری فیبوناچی شد و به احترام او این اعداد فیبوناچی سری اعداد را سری فیبوناچی نامگذاری کردند. این سری به دنباله‌ای از اعداد گفته می‌شود که به ازای هر x عضو اعداد صحیح مثبت بزرگ‌تر از ? داشته باشیم:
و به ازای x=0,1 داریم: F(x)=x.
جمله عمومی سری فیبوناچی به‌صورت زیر است:
حال ما قصد داریم همین اعداد را با برنامه‌نویسی محاسبه کنیم. اولین سوال ما به‌دست آوردن یک عنصر مشخص از اعداد فیبوناچی است، مثلا عنصر xام از این سری از اعداد را به‌دست بیاورید.
برای این کار باید در یک حلقه اعداد را با دو عدد قبلی جمع کنیم، مثلا اگر عنصر 10 ام سری فیبوناچی را از ما خواستند در یک حلقه از 1 تا 10 اعداد را با دو عدد پیشین جمع میکنیم.
فقط دقت داشته باشید که دو عدد اول 0 و 1 هستند. فرض میکنیم عدد اول a و عدد دوم b باشد و fib عدد مورد نظر ما باشد. در هر بار اجرا شدن حلقه فوق داریم:
این‌طوری می‌دانیم که در هر مرحله عدد فیبوناچی مورد نظر ما چیست. پس کد را به‌صورت زیر می‌نویسیم:
long Fibonacci(int no)
for (int i = 1; i « no; i++)
بسیار خب این روش ترتیبی برای به‌دست آوردن اعداد فیبوناچی است، می‌توانیم به‌صورت بازگشتی نیز اعداد فیبوناچی را محاسبه کنیم.
در روش بازگشتی در هر مرحله تابع به دو بخش تقسیم می‌شود و برای هر دو بخش دوباره تابع اعداد فیبوناچی فراخوانی می‌شود. در مرحله اول تابع به ازای ( Fibonacci (no–1 و ( Fibonacci (no–2 دوبار اجرا می‌شود و همین‌طور در مرحله بعدی این دو تابع از حل 4 تابع دیگر به‌دست می‌آید و همین‌طور اگر حساب کنیم می‌بینیم که در محاسبه عدد nام سری فیبوناچی باید 2 به توان n + 1 بار تابع اجرا شود. از آنجا که در توابع بازگشتی از Stack پشته استفاده می‌شود و فضای پشته محدود است با زیاد شدن no دچار خطایStack Overflow خواهیم شد!
پس در محاسبه اعداد بزرگ بهتر است از روش بازگشتی استفاده نکنیم.
کد روش بازگشتی به‌صورت زیر است:
long FibonacciRecursive(int no)
if ((no == 1) || (no == 2))
return FibonacciRecursive(no - 1) + FibonacciRecursive(no - 2);
در هر دو روش ممکن است عدد فیبوناچی حاصل بقدری بزرگ باشد که در متغیر‌های معمول زبان‌های برنامه‌نویسی جای نگیرد، آن وقت تکلیف چیست؟
برای حل این مشکل باید عدد حاصل را یک آرایه تعریف کرده و فرض کنید هر رقم از آرایه یک رقم از عدد است. برای اطلاعات بیشتر در مورد پیاده‌سازی جمع برای اعداد بزرگ به مقاله‌های قبلی که پیرامون این موضوع هستند مراجعه کنید.
آیا راه‌حل دیگری برای به‌دست آوردن عدد فیبوناچی وجود دارد؟ بله! با استفاده از عدد طلایی Phi.
برای محاسبه عدد فیبوناچی با استفاده از عدد طلایی کافیست جای اعداد فیبوناچی n در فرمول زیر شماره عدد فیبوناچی مورد نظر را قرار دهید.
fn = math.pow(Phi, n) / math.sqrt( 5)
عدد فی برابر است با: (25/1+ 1) / 2 = 1.6180339
double Phi = (Math.Sqrt(5) + 1) / 2;
double fibonachi = Math.Pow(Phi, 40) / Math.Sqrt(5);
بسیار خب ما توانستیم برای محاسبه عدد فیبوناچی از سه روش استفاده کنیم، هر کدام از روش‌های ذکر شده ویژ‌گی‌های خود را دارند.
مزیت روش آخر نسبت به روش‌های دیگر این است که دیگر حلقه‌ای اجرا نمی‌شود و بیشتر از توابع کتابخانه‌ای هر زبان استفاده شده است (توابع Math.Pow تابع توان و Math.Sqrt تابع جذر).
یکی دیگر از مسائلی که در مورد اعداد فیبوناچی مطرح می‌شود این است که عکس مراحل بالا را انجام دهیم، یعنی یک عدد به ما بدهند و تشخیص بدهیم که آیا این عدد جزئی از سری فیبوناچی است یا نه؟ یا به اصطلاح این عدد فیبوناچی است یا خیر؟
سری فیبوناچی در سی شارپ (Fibonacci)
در این آموزش تیم کدگیت را با توضیح سری فیبوناچی در سی شارپ همراهی کنید. پیش نیاز این آموزش شامل موارد زیر است:
سری فیبوناچی
در ریاضیات سری فیبوناچی به دنباله‌ای از اعداد گفته می‌شود که بصورت زیر تعریف می‌شود:
غیر از دو عدد اول اعداد بعدی از جمع دو عدد قبلی خود بدست می‌آید. اولین اعداد این سری عبارت‌اند از:
۰٬ ۱٬ ۱٬ ۲٬ ۳٬ ۵٬ ۸٬ ۱۳٬ ۲۱٬ ۳۴٬ ۵۵٬ ۸۹٬ ۱۴۴٬ ۲۳۳٬ ۳۷۷٬ ۶۱۰٬ ۹۸۷٬ ۱۵۹۷٬ ۲۵۸۴٬ ۴۱۸۱٬ ۶۷۶۵٬ ۱۰۹۴۶٬ ۱۷۷۱۱
این اعداد به نام لئوناردو فیبوناچی ریاضیدان ایتالیایی نام گذاری شده‌است.
سری فیبوناچی در سی شارپ
برای پیاده سازی سری فیبوناچی از دو روش بازگشتی و غیر بازگشتی استفاده میکنیم.
سری فیبوناچی در سی شارپ با روش بازگشتی
برای پیاده سازی سری فیبوناجی به صورت بازگشتی ما ورودی خود را یک متغییر int قرار میدهیم که نشان دهنده مرحله ای است که درون آن هستیم. مثلا اگر مقدار ورودی 6 بود یعنی ما عدد 6 در دنباله فیبونانچی را میخواهیم محاسبه کنیم.کد الگوریتم به صورت زیر است:اعداد فیبوناچی
کد بالا شامل دو متد است:
- Fib: متد محاسبه عدد n امین عدد فیبونانچی
- Main: کد تست برنامه فیبونانچی
سری فیبوناچی با روش غیر بازگشتی
در روش غیر بازگشتی ما دو متغیر تعریف میکنیم برای نگهداری دو مرحله قبل از دنباله و از آن برای محاسبه عدد بعدی دنباله فیبوناچی استفاده میکنیم. کد غیر بازگشتی فیبوناچی به صورت زیر است:
