بسیاری از فرآیندهای طبیعی از جمله ترکیب ساختار بدن
موجودات زنده نظم مشخصی دارند و از دنباله اعدادی تبعیت میکنند که امروزه با نام
دنباله اعداد فیبوناچی (فیبوناتچی - Fibonacci) شناخته میشود. مشهورترین خاصیت
این اعداد نسبت دو جمله متوالی آنها به ازای جملات بزرگ دنباله است که به عدد
طلایی مشهور است.
این دنباله از جمله دنبالههای عددی است که در طراحی
سوالات مسابقات برنامهنویسی نیز استفاده میشود و گاهی در حل سوالات کاربرد دارد.
از این رو آشنایی با روشهای مختلف تولید جملات آن حائز اهمیت است.
تعریف: دنباله اعداد فیبوناچی روی
اعداد حسابی به صورت زیر تعریف میشود:
\[ F_n= \left \{\begin{matrix} F_{n-1} + F_{n-2} &
& & \; n > 1\\ 1 & & & \; n = 1 \\ 0 & & & n
= 0 \end{matrix}\right. \]
همانگونه که از تعریف مشخص است، جملات این دنباله از جمع
دو جمله قبلی آن با شروع از دو مقدار صفر و یک به دست میآید:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
[برگرد بالا]
سادهترین راهکار برای محاسبه اعداد دنباله فیبوناچی
استفاده از تابع بازگشتی زیر است:
long long fibo_1(int n){
if(n < 2)
return
n;
return fibo_1(n - 1) + fibo_1(n - 2);
}
این تابع فراخوانی تابع با مقدار $n $ را به فراخوانی
بازگشتی با دو مقدار بسیار نزدیک به $n$ تبدیل میکند. بنابراین میتوان پیشبینی
کرد که زمان تولید خروجی نسبت به اندازه ورودی از مرتبه نمایی باشد. برای مثال
فراخوانیهای بازگشتی تابع برای محاسبه $F_7$ در شکل زیر آمده است:
به این ترتیب برای محاسبه $F_7$ تابع مذکور $41$ بار
فراخوانی میشود که در مقایسه با مقدار $n $ مقرون به صرفه نیست. دلیل این
فراخوانیهای زیاد تکرار در محاسبه جملات میانی است. به عنوان نمونه بر اساس شکل
فوق مقدار $F_2$ هشت بار به صورت تکراری محاسبه شده است.
[برگرد بالا]
برای رفع مشکل فراخوانیهای تکراری در محاسبات میتوان از
روش برنامهنویسی پویا و حرکت از جزء به کل استفاده کرد:
long long fibo_2(int n){
if(n < 2)
return
n;
int f1 = 0, f2
= 1, f3;
for(int i = 2 ; i <= n ; i++){
f3 = f1
+ f2;
f1 =
f2;
f2 =
f3;
}
return f3;
}
مرتبه اجرایی محاسبه جمله $n$-ام دنباله فیبوناچی
با این راهکار $ \Theta(n) $ است که در مقایسه با روش قبل (مرتبه نمایی) عملکرد
بسیار بهتری دارد. همچنین با توجه به کنار گذاشتن فراخوانیهای بازگشتی حافظه
کمتری مصرف میشود.
نکته: در صورتی که نیاز به در اختیار
داشتن تمام جملات دنباله در یک بازه مشخص باشد، این روش بهترین راهکار ممکن است و
کافیست مقدار f3 در هر تکرار کد فوق در یک مخزن جدا مانند آرایه ذخیره شود.
[برگرد بالا]
تعریف رابطه فیبوناچی خود به وضوح یک راهکار تقسیم و غلبه برای محاسبه جملات آن است. اما همانگونه
که بحث شد، استفاده از آن رابطه و فراخوانیهای بازگشتی مقرون به صرفه نیست.
یک تعریف بازگشتی دیگر دنباله فیبوناچی به صورت زیر
است:
\[ \begin{matrix} F_{2n-1} = F^2_n + F^2_{n-1} \\
F_{2n} = (2 F_{n-1} + F_n) F_n \end{matrix} \]
این رابطه محاسبه مقدار جمله $n$-ام دنباله را به
محاسبه دو جمله در حدود $ \frac{n}{2}$ تقسیم میکند. چنین رابطهای مرتبه
$ O(log\;n) $ را تداعی میکند. اما پیادهسازی بازگشتی این رابطه نیز فراخوانیهای
تکراری دارد. به شکل زیر توجه کنید:
این راهکار تعداد فراخوانیها برای محاسبه $F_7$ را از
41 فراخوانی حالت بازگشتی عادی به 11 فراخوانی کاهش میدهد. اما همچنان برخی
فراخوانیهای تکراری وجود دارد که مرتبه آن را بزرگتر از $ \Theta(n)$ (مرتبه
محاسبه به روش برنامهنویسی پویا) میکند. این فراخوانیهای تکراری زمانی که عدد
جمله بزرگتر میشود، تاثیر چشمگیری در زمان محاسبه دارند.
برای رفع این مشکل و بالا بردن کارایی الگوریتم میتوان
جملات تولید شده را در حافظه نگه داشت تا از محاسبه مجدد آن جلوگیری کرد. در چنین
حالتی اگرچه فضای مصرفی الگوریتم بالا میرود، اما زمان اجرای آن بهبود قابل توجهی
پیدا میکند. به عنوان مثال برای محاسبه جمله $ F_{13941207} $ بیش از بیست
میلیون فراخوانی تابع بدون ذخیره کردن مقادیر جملات کوچکتر صورت میگیرد (بسیار
بیشتر از عدد $13941207$) که با ذخیره کردن این مقادیر به کمتر از $130$ فراخوانی
کاهش میابد!
نکته: ممکن است این سوال پیش بیاید که
در روش فراخوانی بازگشتی با تعریف اصلی دنباله فیبوناچی نیز امکان ذخیره کردن
جملات دنباله برای پیشگیری از محاسبه مجدد آن وجود دارد. ویژگی مهم روش اخیر این
است که تنها بخشی از اعداد دنباله تولید و ذخیره میشوند. در حالی که برای محاسبه
با تعریف یا روش برنامهنویسی پویا باید تمامی جملات قبلی دنباله تولید و ذخیره
شوند. به عنوان مثال، برای محاسبه $F_{13941207}$ با راهکار اخیر تنها نیاز به
ذخیره کردن $64 $ جمله است که در مقایسه با تمامی جملات بسیار کمتر است.
[برگرد بالا]
دنباله فیبوناچی را میتوان به فرم ماتریسی زیر نشان
داد:
\[ \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\
F_{n-2} \end{pmatrix} \]
با بسط دادن سمت راست رابطه، برابری زیر حاصل میشود:
\[ \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} =
M^{n-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} = M^{n-1} \begin{pmatrix} 1 \\
0 \end{pmatrix}\; \; , \; \; M = \begin{pmatrix} 1 & 1 \\ 1 & 0
\end{pmatrix} \]
به عبارت دیگر، درایه سطر اول حاصلضرب توان $(n-1)$-ام
ماتریس $ M $ در ماتریس ستونی یک و صفر همان $ F_n $ است. بنابراین کافی است
عنصر $ {(M^{n-1})}_{11} $ (عنصر سطر اول و ستون اول) محاسبه شود
(چرا؟).
این رابطه محاسبه جملات دنباله فیبوناچی را به
محاسبه توان یک ماتریس بدل میکند. توان یک عدد یا یک ماتریس مربعی را میتوان با
استفاده از رابطه زیر حساب کرد که همواره از مرتبه $ O(log \; n)$ است
(چرا؟):
\[ A^n= \left \{ \begin{matrix} {(A^{\frac{n}{2}})}^2
& & & \; n \% 2 = 0 \\ {(A^{\frac{n - 1}{2}})}^2 \times A &
& & \; n \% 2 = 1 \end{matrix} \right. \]
مزیت بزرگ این روش نسبت به روش قبلی عدم نیاز به
ذخیرهسازی مقادیر جملات کوچکتر است و در مقابل هزینه سنگینتر محاسبه ضرب
اعداد را دارد که با توجه به کم بودن آنها (مرتبه لگاریتمی) قابل چشمپوشی است.
همینطور تعداد فراخوانیهای بازگشتی کمتری نسبت به روش قبلی دارد. به عنوان مثال،
با این روش تنها $24$ فراخوانی بازگشتی برای محاسبه توان $13941206$-ام ماتریس $
M $ و در نتیجه محاسبه $F_{13941207} $ نیاز است.
جمعبندی و نکات تکمیلی
در ادامه جمعبندی نوشتههای فوق به همراه برخی نکات تکمیلی و مفید آمده است.
[برگرد بالا]دنباله فیبوناچی مجموعهای از اعداد است که هر عدد از جمع دو عدد قبلی خود بهدست میآید. این دنباله با اعداد صفر و یک آغاز میشود و به صورت 0، 1، 1، 2، 3، 5، 8، 13، 21،... ادامه پیدا میکند.
[برگرد بالا]نسبت دو عدد متوالی در دنباله فیبوناچی با بزرگتر شدن اعداد به عددی نزدیک به 1.618 میل میکند که به آن عدد طلایی (Golden Ratio) میگویند. این نسبت در طبیعت، هنر و معماری کاربردهای فراوانی دارد.
[برگرد بالا]سادهترین روش استفاده از تابع بازگشتی است که هر جمله را با فراخوانی دوباره برای دو عدد قبلی محاسبه میکند. با وجود سادگی، این روش به دلیل تعداد زیاد فراخوانیها کارایی پایینی دارد.
[برگرد بالا]زیرا بسیاری از محاسبات در آن تکراری هستند. به عنوان مثال در محاسبه جملهی هفتم تابع بیش از چهل بار فراخوانی میشود که باعث افزایش زمان اجرا به صورت نمایی میگردد.
[برگرد بالا]در این روش، مقادیر قبلی در حافظه ذخیره میشوند تا از محاسبه مجدد جلوگیری شود. این روش زمان اجرا را به Θ(n) کاهش میدهد و بسیار سریعتر از روش بازگشتی است.
[برگرد بالا]در این روش، از روابط بازگشتی خاص برای محاسبه جملات با استفاده از اعداد کوچکتر (در حدود n/2) استفاده میشود. این روش نسبت به حالت بازگشتی ساده کاراتر است، اما هنوز شامل برخی محاسبات تکراری است.
[برگرد بالا]در این روش از ضرب توان ماتریس خاصی استفاده میشود تا مستقیماً جمله nام بهدست آید. این الگوریتم از مرتبه O(log n) است و یکی از سریعترین روشها برای محاسبه فیبوناچی محسوب میشود.
[برگرد بالا]بسته به نیاز، روش ماتریسی معمولا سریعترین گزینه است. اگر نیاز به تمام جملات تا n دارید، روش برنامهنویسی پویا مناسبتر است.
[برگرد بالا]روش بازگشتی ساده: O(2^n)
روش پویا (حلقهای): 𝑂(𝑛)
روش تقسیم و غلبه: تقریباً 𝑂(log 𝑛)
روش ماتریسی: 𝑂(log 𝑛)
[برگرد بالا]بله، با استفاده از فرمول بسته (Binet’s Formula) میتوان مقدار تقریبی جمله nام را با استفاده از توان عدد طلایی بهدست آورد، اما در مقادیر بزرگ ممکن است دقت عددی کاهش یابد.
[برگرد بالا]اعداد فیبوناچی در مسائل الگوریتمی، تحلیل بازگشتها، طراحی الگوریتمهای بازگشتی و سوالات مسابقات برنامهنویسی بسیار پرکاربرد هستند.
[برگرد بالا]بله، دنباله فیبوناچی در بسیاری از پدیدههای طبیعی مانند آرایش گلبرگها، دانههای آفتابگردان و ساختار صدفها مشاهده میشود که همگی با نسبت طلایی مرتبط هستند.