دنباله اعداد فیبوناچی

الگوریتم‌های محاسبه بازگشتی و غیربازگشتی
جستجو:  

بسیاری از فرآیندهای طبیعی از جمله ترکیب ساختار بدن موجودات زنده نظم مشخصی دارند و از دنباله اعدادی تبعیت می‌کنند که امروزه با نام دنباله اعداد فیبوناچی (فیبوناتچی - 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} $ نیاز است.


تا کنون ۵۳ امتیاز ثبت شده
نوشته لایک نداشت؟
 
به اشتراک گذاری نوشته

algs.ir/spg1rcc

اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram


نام: *  

پست الکترونیک (محرمانه):

پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• شیما
۱ تیر ۱۳۹۵، ساعت ۱۲:۲۴

سلام آقا مسعود... میدونم ربطی به این بحث نداره ولی میشه یه توضیحی در مورد اعداد فوق اول بدید.. ومعادل ریاضیش رو در انگلیسی بفرمائید چی هست prime  عدد اول ...فوق اول چی میشه

۱ تیر ۱۳۹۵، ساعت ۱۷:۰۷
• مسعود اقدسی فام

فکر کنم منظورتون اعداد superprime یا higher-order prime هستن.

اگه دنباله‌ی اعداد اول رو بنویسید و عناصری از اونها رو انتخاب کنید که شماره‌ی محلشون عدد اول باشه، بهشون superprime گفته می‌شه. مثلا اولین عدد superprime عدد ۳ هست که در موقعیت ۲ (اولین عدد اول) از دنباله‌ی کل اعداد اول قرار داره.

• شیما
۱ تیر ۱۳۹۵، ساعت ۱۷:۴۸

بله منظورم همین بود  تشکر می کنم از شما12

• sara
۱۳ اسفند ۱۳۹۶، ساعت ۱۱:۲۷

040506060606060606

• A4FARAN3
۲۱ فروردین ۱۳۹۷، ساعت ۱۴:۴۱

دمت گرم

• aref
۲۶ مهر ۱۳۹۷، ساعت ۱۹:۵۸

مگه بهتر از اینم میشه...

کاربردی و درجه یک با توضیحات کامل

• 1234
۱ اردیبهشت ۱۳۹۸، ساعت ۱۷:۵۱

0102030405050708090911121314

• عباس
۲ آبان ۱۳۹۸، ساعت ۲۱:۰۱

0102030405060708091011121314

• آرمین بوسفیان
۱ دی ۱۳۹۸، ساعت ۲۱:۰۲

سلام اقا مسعود اگه این عداد فیبوناچی رو با همون فرمول که تو اول نوشتید ادامه دهیم و عدد۱۰۰۰رو بخواهیم پیدا کنیم چطور میشه؟؟؟؟؟؟؟؟؟؟؟

به این صورت(f999)+(f998)من فقط اینو میتونم بدست بیارم!؟و بخواهیم عدد رو پیدا کنیم بعد از این چکار کنیم؟اون عدد رو چژور بدیت بیاوریم؟؟

لطفا جواب بدید

پاسخی که بفهمم!

•  ئوئو
۵ دی ۱۳۹۸، ساعت ۱۰:۱۰

جمله ی عمومی دنباله ی فیبوناچی؟

•  ئوئو
۵ دی ۱۳۹۸، ساعت ۱۰:۱۰

جمله ی عمومی دنباله ی فیبوناچی؟

•  ئوئو
۵ دی ۱۳۹۸، ساعت ۱۰:۱۰

جمله ی عمومی دنباله ی فیبوناچی؟

• هایدی سویله
۱۹ مهر ۱۳۹۹، ساعت ۰۲:۳۳

دمت گرم

• گیسو
۱ آذر ۱۳۹۹، ساعت ۱۸:۰۳

سلام

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

• هامی
۱۷ خرداد ۱۴۰۱، ساعت ۱۵:۳۸

میشه پنجاه جمله اول دنباله فیبوناچی الگو ریتمشو بزارید

لطفااااا

• هامی
۱۷ خرداد ۱۴۰۱، ساعت ۱۵:۳۸

میشه پنجاه جمله اول دنباله فیبوناچی الگو ریتمشو بزارید

لطفااااا

• هامی
۱۷ خرداد ۱۴۰۱، ساعت ۱۵:۴۱

۱۱۲۳۵۸۱۳

اینارم داده تو سوال😔😕