برنامه محاسبه nامین عدد فیبوناچی – به زبان ساده

در این مطلب، روش‌های گوناگون نوشتن برنامه محاسبه nامین عدد فیبوناچی مورد بررسی قرار گرفته و سپس، پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است. اعداد فیبوناچی، اعدادی هستند که در توالی اعداد صحیح زیر قرار داشته باشند.

۰, ۱, ۱, ۲, ۳, ۵, ۸, ۱۳, ۲۱, ۳۴, ۵۵, ۸۹, ۱۴۴, ...

به بیان ریاضی، توالی F_n از اعداد فیبوناچی با استفاده از رابطه بازگشتی زیر، تعریف شده است.

F_n = F_n-1 + F_n-2

در رابطه بالا، مقدار دانه برای F₀ = 0 و برای F₁ = 1 است.

F₀ = 0 and F₁ = 1

فرض می‌شود عدد n داده شده است. هدف، نوشتن برنامه‌ای است که n‌اُمین عدد فیبوناچی را چاپ کند. مثال‌های زیر در این راستا قابل توجه هستند.

Input: n = ۲

Output: ۱



Input: n = ۱

Output: ۳۴

در ادامه، تابع (int fib(int n نوشته می‌شود که مقدار F_n را باز می‌گرداند. برای مثال، اگر n = 0 باشد، ()fib باید ۰ و اگر n = 1 باشد، تابع ()fib باید مقدار ۱ را بازگرداند. برای n > 1، باید مقدار F_n-1 + F_n-2 بازگردانده شود.

For n = 9

Output: ۳۴

در ادامه، روش‌های گوناگون محاسبه nامین عدد فیبوناچی ارائه شده است.

روش اول محاسبه nامین عدد فیبوناچی

یک راهکار ساده برای محاسبه nامین عدد فیبوناچی، پیاده‌سازی مستقیم رابطه ریاضی بازگشتی است که پیش‌تر ارائه شد.

برنامه بازگشتی محاسبه nامین عدد فیبوناچی در ++C

برنامه بازگشتی محاسبه nامین عدد فیبوناچی در C

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

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

برنامه بازگشتی محاسبه nامین عدد فیبوناچی در #C

برنامه بازگشتی محاسبه nامین عدد فیبوناچی در PHP

خروجی

خروجی قطعه کدهای بالا برای n = 9 به صورت زیر است.

34

پیچیدگی زمانی این این روش، (T(n) = T(n-1) + T(n-2 است. می‌توان مشاهده کرد که این پیاده‌سازی کارهای تکرار شونده زیادی را انجام می دهد (درخت بازگشتی که در ادامه آمده، قابل مشاهده است). بنابراین، پیاده‌سازی ارائه شده در بالا، برای محاسبه nامین عدد فیبوناچی، نامناسب است.

fib(5) 
/ \
fib(4) fib(3) 
/ \ / \ 
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)

فضای اضافی (Extra Space) مورد استفاده در روش بالا، اگر فراخوانی تابع برابر با سایز پشته در نظر گرفته شود، برابر با (O(n و در غیر این صورت برابر با (O(۱ است.

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

در روش دوم محاسبه nامین عدد فیبوناچی، از روش بازگشتی، همراه با برنامه‌نویسی پویا (Dynamic Programming) استفاده شده است. در این روش، می‌توان از کار تکرار شونده‌ای که در راهکار بالا انجام می‌شود اجتناب کرد؛ این کار به وسیله ذخیره‌سازی اعداد فیبوناچی که تاکنون محاسبه شده‌اند انجام می‌شود.

برنامه محاسبه nامین عدد فیبوناچی در C

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

برنامه محاسبه nامین عدد فیبوناچی در پایتون

برنامه محاسبه nامین عدد فیبوناچی در #C

برنامه محاسبه nامین عدد فیبوناچی در PHP

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

این روش، نسبت به روش‌های ارائه شده در بالا، بهینه‌تر است. در اینجا، می‌توان فضای استفاده شده در روش ۲ را با ذخیره‌سازی دو عدد پیشین بهینه کرد. زیرا این دو مورد، تنها اعدادی هستند که برای محاسبه عدد فیبوناچی بعدی در سری مورد نیاز هستند.

برنامه محاسبه nامین عدد فیبوناچی در ++C/C

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

برنامه محاسبه nامین عدد فیبوناچی در پایتون

برنامه محاسبه nامین عدد فیبوناچی در #C

برنامه محاسبه nامین عدد فیبوناچی در PHP

خروجی

خروجی قطعه کدهای بالا برای n = 9 به صورت زیر است.

34

پیچیدگی زمانی این الگوریتم از درجه (O(n و فضای اضافی آن از (O(1 است.

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

در اینجا، از به توان رساندن ماتریس {{1,1},{1,0}} برای محاسبه nامین عدد فیبوناچی استفاده شده است. پیچیدگی زمانی این راهکار از درجه (O(n است؛ دلیل این امر آن است که اگر n بار ماتریس {{M = {{1,1},{1,0 در خودش ضرب شود، (به بیان دیگر، توان (M, n) محاسبه شود) n+1اُمین عدد فیبوناچی به عنوان عنصری در سطر و ستون (0, 0) در ماتریس نتیجه به دست می‌آید. ارائه ماتریس، عبارت بسته زیر را برای اعداد فیبوناچی به دست می‌دهد.

$$\begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix} ^ n = \begin{bmatrix}F_{n+1} & F_{n} \\F_{n} & F_{n-1} \end{bmatrix}$$

برنامه محاسبه nامین عدد فیبوناچی در C

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

برنامه محاسبه nامین عدد فیبوناچی در پایتون ۳

برنامه محاسبه nامین عدد فیبوناچی در #C

برنامه محاسبه nامین عدد فیبوناچی در PHP

پیچیدگی زمانی این روش، از درجه (O(n و فضای اضافی آن از درجه (O(1 است.

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

این روش، بهینه شده روش پیشین است. در واقع، روش چهارم را می‌توان به نوعی بهینه کرد که با پیچیدگی زمانی (O(Logn کار کند. می‌توان از ضرب بازگشتی برای محاسبه (power(M, n در روش پیشین، استفاده کرد.

برنامه محاسبه nامین عدد فیبوناچی در C

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

برنامه محاسبه nامین عدد فیبوناچی در پایتون ۳

برنامه محاسبه nامین عدد فیبوناچی در #C

پیچیدگی زمانی این روش، از درجه (O(Logn است. اگر اندازه پشته فراخوانی تابع در نظر گرفته شود، فضای اضافی این روش از درجه (O(Logn و در غیر این صورت، از (O(1 است.

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

در زیر، یک فرمول بازگشتی جالب توجه برای پیدا کردن nامین عدد فیبوناچی در زمان (O(Log n ارائه شده است.

اگر n زوج است، k = n/2:

F(n) = [2*F(k-1) + F(k)]*F(k)

اگر n فرد است، k = (n + 1)/2:

F(n) = F(k)*F(k) + F(k-1)*F(k-1)

این رابطه را می‌توان از معادله ماتریس بالا به دست آورد.

$$\begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix} ^ n = \begin{bmatrix}F_{n+1} & F_{n} \\F_{n} & F_{n-1} \end{bmatrix}$$

با دترمینان گرفتن از دو طرف معادله، داریم:

$$(-1)^n = F_{n+1}F_{n-1} – F_{n}^2$$

همچنین، با توجه به اینکه رابطه $$A^nA^m = A^n+m$$ برای هر ماتریس مربعی A برقرار است، ماتریس‌های همانی زیر را می‌توان به دست آورد (این موارد، از دو ضریب مختلف ضرب داخلی ماتریس‌ها به دست آمده‌اند).

$$F_{m} F_{n} + F_{m - 1} F_{n - 1} = F_{m + n - 1}$$

با قرار دادن n = n+1 رابطه زیر به دست می آید:

$$F_{m}F_{n+1} + F_{m - 1}F_{n} = F_{m + n}$$

با قرار دادن m = n روابط زیر حاصل می‌شوند:

$$F_{2n-1} = F_{n}^2 + F_{n-1} ^ 2$$

$$F_{2n} = (F_{n - 1} + F_{n+1})F_{n} = (2F_{n-1}+F_{n})F_{n}$$

برای اثبات این رابطه، باید اقدامات زیر را انجام داد:

• اگر n زوج است، می‌توان $$k = \frac{n}{2}$$ را قرار داد.
• اگر n فرد است، می‌توان $$k = \frac{n + 1}{2}$$ را قرار داد.

در ادامه، پیاده‌سازی روش بالا انجام شده است.

برنامه محاسبه nامین عدد فیبوناچی در ++C

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

برنامه محاسبه nامین عدد فیبوناچی در پایتون

برنامه محاسبه nامین عدد فیبوناچی در #C

برنامه محاسبه nامین عدد فیبوناچی در PHP

خروجی

خروجی قطعه کدهای بالا برای n = 9 به صورت زیر است.

34

پیچیدگی زمانی این روش، از درجه (O(Log n است، زیرا در هر فراخوانی بازگشتی، مساله به نیمی تقسیم (شکسته) می‌شود.

روش هفتم محاسبه nامین عدد فیبوناچی

در این روش، فرمول به طور مستقیم برای nامین عبارت سری فیبوناچی پیاده‌سازی می‌شود.

$$F_{n} = \frac{\{[\frac{\sqrt{5}+1}{2}]^{n}\}}{\sqrt{5}}$$

برنامه محاسبه nامین عدد فیبوناچی در ++C

برنامه محاسبه nامین عدد فیبوناچی در C

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

برنامه محاسبه nامین عدد فیبوناچی در #C

برنامه محاسبه nامین عدد فیبوناچی در PHP

خروجی

خروجی قطعه کد بالا، برای n = 9 به صورت زیر است.

34

پیچیدگی زمانی این روش از درجه (O(1 و پیچیدگی فضایی آن نیز از درجه (O(1 است.