بررسی انواع روش‌های محاسبه سری فیبوناچی

در بسیاری از مصاحبه‌هایی که برای موقعیت شغلی توسعه­‌‍‌دهنده‌ی نرم­افزار انجام می‌گیرد، این سوال پرسیده می‌شود که الگوریتم سری فیبوناچی را بنویسید ‌یا الگوریتم محاسبه‌ی  nامین جمله از سری فیبوناچی را بنویسید. هم ‌چنین این مسئله، جزو مسائلی است که دانشجویان رشته کامپیوتر در درس طراحی الگوریتم و ساختمان داده خواهند خواند و جزو سوالات امتحانی آن­ها هم خواهد بود. در این مقاله قصد داریم، با مسأله سری فیبوناچی آشنا شده و انواع روش‌های محاسبه‌ی سری فیبوناچی را بررسی کنیم.

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

سری یا دنباله فیبوناچی‌ یکسری از اعداد می‌باشد که در هر مرحله، عدد بعدی با جمع کردن دو عدد قبل از آن به دست می‌آید. سری فیبوناچی با اعداد 0 و 1 شروع می‌شود. عدد سوم با جمع کردن دو عدد قبلی که 0 و 1 باشند، به دست می‌آید پس عدد سوم 1 خواهد شد و به همین روال اعداد دیگر سری فیبوناچی محاسبه می‌شود. مثلا عدد چهارم از جمع دو عدد قبل از خودش ‌یعنی اعداد دوم و سوم ( 1 و 1 ) محاسبه می‌شود، پس عدد چهارم 2 می‌شود. در زیر تعدادی از جمله‌های سری فیبوناچی را می‌بینید. که همان طور که گفته شد، هر عدد از جمع دو عدد قبل از خودش محاسبه شده است. 

0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , . . . 

فرمول ریاضی محاسبه‌ی سری فیبوناچی به صورت زیر است. 

F ( n ) = F ( n-1 ) + F ( n-2 )

• F ( n ) جمله‌ی n ام است که می‌خواهیم محاسبه کنیم 
• F ( n - 1 ) جمله‌ی قبلی جمله‌ی n ام
• F ( n - 2 ) دو جمله‌ی قبلی جمله‌ی n ام

این سری توسط فردی به نام فیبوناچی ، که حدود 800 سال پیش در ایتالیا زندگی می‌کرده است، کشف شده است. هم‌چنین لازم به ذکر است که مثال‌های این نوشتار با استفاده از زبان ‌برنامه‌نویسی #C نوشته شده است. سعی کرده ایم مثال‌ها را به گونه‌ای عمومی ‌بنویسیم تا بتوانید به راحتی به زبان‌های دیگر تبدیل کنید و با زبان‌های ‌برنامه‌نویسی دیگر باز نویسی کنید.

محاسبه و چاپ سری فیبوناچی تا n امین جمله با روش حلقه تکرار

یکی از ساده‌ترین روش‌های محاسبه‌ی دنباله فیبوناچی، استفاده از حلقه تکرار است. در این روش با استفاده از‌ یک حلقه تکرار، سری فیبوناچی را تا جمله n ام آن محاسبه و چاپ می‌کنیم. همان­طور که گفته شد، جمله اول و دوم را به ترتیب 0 و 1 در نظر می‌گیریم. در بسیاری از مقاله‌ها و کتاب‌ها می‌بینید که جملات به جای شروع شدن از ‌یک، از صفر شروع شده است ‌یعنی جملات صفر و ‌یک، به ترتیب برابر با صفر و ‌یک خواهند بود که تفاوتی هم ‌در نحوه‌ی محاسبه نخواهد داشت. 

در متد محاسبه n امین سری فیوناچی به روش تکراری ‌یعنی FibonacciSeries، دو متغیر به نام‌های  firstNumberو  secondNumberتعریف می‌کنیم و مقادیر 0 و 1 را به آن‌ها نسبت می‌دهیم. سپس بررسی می‌کنیم اگر سری 0‌ یا 1 درخواست شده بود همان اعداد را بر‌می‌گردانیم. بعد از آن، از ‌یک حلقه for استفاده می‌کنیم. حلقه از جمله سوم شروع می‌شود (چون جمله‌ یک و دو را پیدا کرده‌ایم) و تا جمله‌ای که می‌خواهیم محاسبه کنیم (جمله‌ی n ام) ادامه خواهد داشت. درون حلقه بر اساس فرمول محاسبه،‌ یعنی جمع دو جمله قبلی، جمله‌ی بعد را حساب می‌کنیم و در متغیر result نگه می‌داریم. در آخر نیز دو جمله‌ای که بر اساس آن جمله‌ی بعدی محاسبه می‌شود (متغیر‌های firstNumber و secondNumber) را بروزرسانی می‌کنیم تا در گام بعدی حلقه از آن‌ها استفاده کنیم. در زیر قطعه کد نوشته شده برای محاسبه و چاپ سری فیبوناچی تا n امین جمله را با روش حلقه‌ی تکرار مشاهده می‌کنید.

using System;
namespace FibonacciSeries
{
    class Program
    {
        static int FibonacciSeries(int n)
        {
            int firstNumber = 0, secondNumber = 1, result = 0;

            if (n == 0) return 0; // To return the first Fibonacci number   
            if (n == 1) return 1; // To return the second Fibonacci number   


            for (int i = 2; i <= n; i++)
            {
                result = firstnumber + secondnumber;
                firstnumber = secondnumber;
                secondnumber = result;
            }

            return result;
        }

        static void Main(string[] args)
        {
            Console.Write(" Enter the length of the Fibonacci Series: ");
            int length = Convert.ToInt32(Console.ReadLine());

            for (int i = 0 ; i < length ; i++)
            {
                Console.Write(" {0} ", FibonacciSeries(i));
            }
            Console.ReadKey();
        }
    }
}

برای نمونه با فراخوانی متد FibonacciSeries با ورودی 13، خروجی به صورت زیر خواهد بود. 

FibonacciSeries(13) 
0 1 1 2 3 5 8 13 21 34 55 89 144

محاسبه و چاپ سری فیبوناچی تا n امین جمله با روش تابع برگشتی

در این روش محاسبه، از تابع بازگشتی استفاده می‌کنیم. تابع بازگشتی (Recursive) تابعی است که به صورت مداوم، خود را فراخوانی می‌کند. این فراخوانی‌ها باید در جایی پایان‌ یابد. در غیر این صورت با خطای پر شدن حافظه‌ی stack‌ یا خطای مشهور stack over flow مواجه خواهیم شد.

مسئله‌ی سری فیبوناچی ذاتا مسئله‌ای است که می‌توان آن را به مسائل کوچک‌تری تقسیم کرد و آن مسائل کوچک‌تر را حل کرد.

همان‌طور که گفته شد، فرمول ریاضی مسئله فیبوناچی به صورت زیر است. 

F ( n ) = F ( n - 1 ) + F ( n - 2 )

برای حل f ( n ) باید F ( n-1 ) و F ( n-2 ) را حل کنیم و به همین صورت ادامه دهیم تا مسئله حل شود. تابع بازگشتی هم‌دقیقا به این صورت است که تابع با ورودی بزرگ را به ورودی کوچک‌تر تقسیم می‌کنیم و با جمع کردن آن‌ها تابع اصلی حل خواهد شد.

در مثال زیرو در متد Fibonacci_Recursive ، ابتدا چک می‌کنیم که آیا به آخر محاسبات رسیده‌ایم‌یا نه. منظور از آخر محاسبات جایی است که مسئله از آن کوچک‌تر نخواهد شد. همان‌طور که گفته شد توابع برگشتی باید در جایی خاتمه ‌یابند. در مثال ما اگر مقدار ورودی 0 ‌یا 1 باشد همان مقدار برگشت داده می‌شود و برای آن‌ها تابع فراخوانی نمی‌شود. اگر مقادیر ورودی 0 یا 1 نباشند، تابع برای مقادیر n – 1 و n – 2 دو بار فراخوانی خواهد شد. این فراخوانی‌ها آن قدر ادامه می‌یابد که مسئله حل شده و با جمع کردن مقادیر به دست آمده، جمله n ام سری فیبوناچی به دست خواهد آمد. در زیر قطعه کد نوشته شده برای محاسبه و چاپ سری فیبوناچی تا n امین جمله را با روش تابع برگشتی مشاهده می‌کنید.

using System;
namespace FibonacciSeries
{
    class Program
    {
        public static int Fibonacci_Recursive(int n)
        {
            if (n == 0) return 0; // To return the first Fibonacci number   
            if (n == 1) return 1; // To return the second Fibonacci number   
            return Fibonacci_Recursive(n - 1) + Fibonacci_Recursive(n - 2);
        }
        public static void Main(string[] args)
        {
            Console.Write(" Enter the length of the Fibonacci Series: ");
            int length = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < length; i++)
            {
                Console.Write(" {0} ", Fibonacci_Recursive(i));
            }
            Console.ReadKey();
        }
    {
{

در زیر نمونه‌ای دیگر از روش بازگشتی را مشاهده می‌کنید. 

using System;
namespace FibonacciSeries
{
    class Program
    {
        public static void FibonacciRecursive(int firstNumber, int secondNumber, int counter, int length)
        {
            if (counter <= length)
            {
                Console.Write (" {0} ", firstNumber);
                FibonacciRecursive(secondNumber, firstNumber + secondNumber, counter + 1, length);
            }
        }

        public static void Main(string[] args)
        {
            Console.Write(" Enter the length of the Fibonacci Series: ");
            int length = Convert.ToInt32 (Console.ReadLine());
            FibonacciRecursive (0, 1, 1, length);
            Console.ReadKey();
        }
    {
{

محاسبه و چاپ n امین جمله سری فیبوناچی با روش تابع برگشتی

در این بخش می‌خواهیم به جای چاپ همه‌ی اعداد سری تا‌یک جمله خاص، تنها جمله‌ی n ام سری فیبوناچی را محاسبه کنیم. برای محاسبه‌ی آن از روش تابع بازگشتی استفاده می‌کنیم. در ابتدای کار گام بازگشت (جایی که باید تابع بازگشتی از آن جا خاتمه‌یابد) را تعیین می‌کنیم. به دلیل این که فیبوناچی جملات 0 و 1 خودشان می‌شوند، پس اگر در ورودی اعداد 0‌یا 1 وارد شد، همان عدد را بر می‌گردانیم و در غیر این صورت، فیبوناچی n – 1 و n – 2 را محاسبه می‌کنیم و با هم‌جمع می‌بندیم. این کار را تا زمانی انجام می‌دهیم تا به جملات 0 و 1 برسیم. در زیر قطعه کد نوشته شده برای محاسبه‌ی n امین جمله را مشاهده می‌کنید.

using System;
namespace FibonacciSeries
{
    class Program
    {
        public static int NthFibonacciNumber(int n)
        {
            if ((n == 0) || (n == 1))
            {
                return n;
            }
            else
            {
                return (NthFibonacciNumber(n - 1) + NthFibonacciNumber(n - 2));
            }
        }

        public static void Main(string[] args)
        {
            Console.Write(" Enter the nth number of the Fibonacci Series: ");
            int number = Convert.ToInt32(Console.ReadLine());
            number = number - 1;
            // We have to decrement the length because the series starts with 0 

           Console.Write(NthFibonacciNumber(number));
            Console.ReadKey();
        }
	}
}

تنها نکته‌ای که باید به آن توجه کنید این است که چون در این مثال شماره اولین جمله سری فیبوناچی را 0 در نظر گرفته ایم، از ورودی کاربر‌یک عدد کم می‌کنیم.

number = number - 1;

در این مقاله سعی کردیم با مسئله‌ی سری فیبوناچی آشنا شده و انواع روش‌های محاسبه‌ی آن را‌ یاد بگیریم. امیدوارم در فهم ‌این مسئله‌ی نه چندان سخت به شما کمک کرده باشد.