الگوریتم فیبوناچی — ۰ تا ۱۰۰ دنباله فیبوناچی به زبان ساده

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

الگوریتم فیبوناچی چیست؟

الگوریتم فیبوناچی یک روش برای تولید دنباله‌ای از اعداد است که با دو عدد ابتدایی ۰ و ۱ شروع می‌شود. در این دنباله، هر عدد جدید از جمع دو عدد قبلی خودش ساخته می‌شود. این دنباله به صورت: ۰، ۱، ۱، ۲، ۳، ۵، ۸، ۱۳، … ادامه پیدا می‌کند. قانون اصلی آن بسیار ساده است و می‌گوید: هر عدد برابر است با جمع دو عدد قبل از خودش.

این الگوریتم را می‌توان به روش‌های مختلفی پیاده‌سازی کرد. روش بازگشتی (Recursive) مستقیماً از تعریف ریاضی استفاده می‌کند، اما به دلیل محاسبات تکراری برای اعداد بزرگ، کند است. روش تکراری (Iterative) با استفاده از یک حلقه ساده این مشکل را حل می‌کند و با حافظه و زمان کمتری محاسبات را انجام می‌دهد. همچنین، تکنیک برنامه‌ریزی پویا (Dynamic Programming) از ذخیره‌سازی نتایج قبلی استفاده می‌کند تا الگوریتم را بهینه‌تر کند.

نسبت طلایی

الگوریتم فیبوناچی به دلیل ویژگی‌های ساده اما جالبش، پایه‌ای برای درک مفاهیم پیشرفته‌تر در علوم مختلف است. یک ویژگی جالب دیگر این دنباله ارتباط آن با نسبت طلایی (Golden Ratio) است. نسبت طلایی با نماد ϕ (فای) نمایش داده می‌شود و وقتی هر عدد فیبوناچی را به عدد قبلی خودش تقسیم کنیم (مثلاً ۱۳ ÷ ۸ یا ۸ ÷ ۵)، هرچه جلوتر برویم، این نسبت به عدد ۱.۶۱۸ نزدیک‌تر می‌شود که همان نسبت طلایی است. این نسبت در طبیعت، هنر، معماری و طراحی دیده می‌شود، مثل مارپیچ صدف‌ها، الگوی دانه‌های گل آفتابگردان، و حتی در طراحی ساختمان‌ها و آثار هنری معروف.

در طبیعت نیز دنباله فیبوناچی به‌طور گسترده‌ای مشاهده می‌شود. تعداد گلبرگ‌های گل‌ها، شکل مارپیچ صدف‌ها، چیدمان برگ‌ها روی شاخه‌ها، و حتی ساختارهای کهکشانی اغلب از این دنباله پیروی می‌کنند. این ویژگی‌ها نشان‌دهنده اهمیت بنیادی این اعداد در توضیح الگوهای طبیعی و ریاضی است. فیبوناچی، اگرچه ساده به نظر می‌رسد، اما پیوندی عمیق میان ریاضیات، هنر، و طبیعت ایجاد می‌کند که آن را به یکی از جذاب‌ترین مفاهیم علمی تبدیل کرده است.

آموزش تبدیل مبنا با روش سریع برای اعداد اعشاری و صحیح

کلیک کنید

مثال واقعی از طبیعت

لئوناردو در کتاب خود سوالی جالب مطرح می‌کند: با فرض شرایط ایده‌آل، چقدر می‌توان از یک جفت خرگوش در یک سال جفت خرگوش تولید کرد؟ پاسخ این سوال ۱۴۴ جفت است که به کمک الگوریتم فیبوناچی به دست می‌آید. در این آزمایش ذهنی، فرض بر این است که دو خرگوش نوزاد در یک حیاط محصور قرار می‌گیرند و تا یک ماهگی قادر به تولید مثل نیستند. در ابتدا، تنها جفت اولیه باقی می‌ماند.

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

پس از ۱۲ ماه، تعداد جفت خرگوش‌ها به ۱۴۴ می‌رسد و این روند ادامه پیدا می‌کند. پس از دو سال، تعداد جفت‌ها به ۴۶,۳۶۸ جفت خواهد رسید. این مدل نشان می‌دهد که چگونه جمعیت خرگوش‌ها در شرایط ایده‌آل به سرعت افزایش می‌یابد، هرچند در دنیای واقعی عوامل مختلفی مانند منابع محدود و دشمنان طبیعی این رشد را متوقف می‌کنند.

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

همانطور که دانستیم دنباله فیبوناچی یک سری از اعداد است که در آن هر عدد (به جز دو عدد اول) برابر است با مجموع دو عدد قبلی‌اش. برای محاسبه اعداد دنباله فیبوناچی، ابتدا دو عدد ابتدایی را مشخص می‌کنیم: ۰ و ۱. سپس برای هر عدد بعدی، آن را از جمع دو عدد قبلی به دست می‌آوریم.

به عبارت دیگر، هر عدد در دنباله برابر با جمع دو عدد قبلی‌اش است. به طور مثال، پس از ۰ و ۱، عدد بعدی ۱ به دست می‌آید (چرا که ۰ + ۱ = 1). سپس ۱ و ۱ را جمع می‌کنیم که می‌شود ۲، بعد از آن ۱ و ۲ را جمع می‌کنیم که می‌شود ۳، و به همین ترتیب ادامه می‌دهیم.

این روند به همین صورت ادامه پیدا می‌کند و هر عدد جدید از جمع دو عدد قبلی خود به دست می‌آید. بنابراین، دنباله به شکل زیر ادامه پیدا می‌کند: ۰، ۱، ۱، ۲، ۳، ۵، ۸، ۱۳، ۲۱، ۳۴ و غیره. برای محاسبه اعداد بالاتر، تنها کافی است که دو عدد قبلی را جمع کرده و عدد جدید را به دنباله اضافه کنیم. این روش به‌راحتی قابل پیاده‌سازی است و به همین دلیل در الگوریتم‌های مختلف برای حل مسائل مختلف مورد استفاده قرار می‌گیرد.

دنباله فیبوناچی به زبان ساده

برای پیدا کردن اعداد فیبوناچی معمولاً از اعداد ۰ و ۱ شروع می‌کنیم که عدد اول و دوم دنباله خواهند بود. برای پیدا کردن عدد سوم باید دو عدد قبلی را جمع (یعنی ۰+۱) کنیم که پاسخ می‌شود ۱. برای پیدا کردن عدد چهارم نیز باید دو عدد قبلی را جمع (یعنی ۱+۱) کنیم که پاسخ می‌شود ۲. همینطور این روش ادامه می‌یابد.

به طور کلی و به زبان ساده روش محاسبه اعداد با الگوریتم فیبوناچی به صورت زیر خواهد بود:

• اولین عدد: ۰

چون این عدد اول دنباله است، همین‌طوری شروع می‌کنیم.

• دومین عدد: ۱

این هم مثل عدد اول، از قبل مشخص است.

• عدد سوم: ۱ = 0 + ۱

حالا دوتا عدد قبلی (۰ و ۱) را جمع می‌کنیم، پاسخ می‌شود ۱.

• عدد چهارم: ۲ = 1 + ۱

دو عدد قبلی (۱ و ۱) را جمع می‌کنیم، پاسخ می‌شود ۲.

• عدد پنجم: ۳ = 1 + ۲

حالا دو عدد قبلی (۱ و ۲) را جمع می‌کنیم، پاسخ می‌شود ۳.

• عدد ششم: ۵ = 2 + ۳

دو عدد قبلی (۲ و ۳) را جمع می‌کنیم، پاسخ می‌شود ۵.

• عدد هفتم: ۸ = 3 + ۵

حالا دو عدد قبلی (۳ و ۵) را جمع می‌کنیم، پاسخ می‌شود ۸.

• عدد هشتم: ۱۳ = 5 + ۸

در آخر، دو عدد قبلی (۵ و ۸) را جمع می‌کنیم، پاسخ می‌شود ۱۳. در اینجا این دنباله به دست آمد: ۰، ۱، ۱، ۲، ۳، ۵، ۸، ۱۳. اگر این روش را ادامه دهیم می‌توانیم به اعداد زیر برسیم:

۱۳ + ۸ = 21

۲۱ + ۱۳ = 34

۳۴ + ۲۱ = 55

۵۵ + ۳۴ = 89

۸۹ + ۵۵ = 144

۱۴۴ + ۸۹ = 233

۲۳۳ + ۱۴۴ = 377

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

یک فکت جالب درمورد الگوریتم فیبوناچی

دنباله فیبوناچی به شکلی پیش می‌رود که الگوی زوج و فرد در آن تکرار می‌شود: زوج، فرد، فرد، زوج، فرد، فرد، زوج، فرد، فرد و به همین ترتیب ادامه پیدا می‌کنند.

این الگو به دلیل قواعد جمع اعداد در دنباله فیبوناچی است. در این دنباله، هر عدد حاصل جمع دو عدد قبلی است و ترکیب زوج و فرد بودن این اعداد یک الگوی تکرارشونده ایجاد می‌کند.

علت این الگو در قواعد جمع اعداد نهفته است. وقتی دو عدد فرد با هم جمع شوند، حاصل همیشه زوج است؛ در مقابل، جمع یک عدد زوج و یک عدد فرد (به هر ترتیبی) همواره یک عدد فرد می‌دهد. ازآنجاکه دنباله فیبوناچی با یک عدد زوج (۰) و دو عدد فرد (۱، ۱) شروع می‌شود، این الگوی تکراری “زوج، فرد، فرد” در تمام طول دنباله حفظ می‌شود. این ویژگی ساده اما جالب یکی از جنبه‌های ریاضی جذاب دنباله فیبوناچی است که در بسیاری از زمینه‌ها از طبیعت تا هنر مشاهده می‌شود.

آموزش مجموعه برترین سوالات ریاضی هفتم

کلیک کنید

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

برای محاسبه دنباله فیبوناچی روش‌های مختلفی وجود دارد که هرکدام مزایا و معایب خاص خود را دارند. در اینجا سه روش ساده و رایج برای محاسبه این دنباله آورده شده است:

روش بازگشتی (Recursive)

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

برای n ≥ ۲ یا به عبارتی n هایی که بزرگتر از ۲ هستند:

F(n) = F(n−۱) + F(n−۲)

و همچنین

F(0) = 0 , F(1) = 1

یعنی:

• اولین عدد دنباله F(0) برابر با ۰ است.
• دومین عدد دنباله F(1) برابر با ۱ است.

از سومین عدد به بعد، هر عدد برابر با جمع دو عدد قبلی خود است. برای مثال:

F(2) = F(1) + F(0) = 1+0 = 1

F(3) = F(2) + F(1) = 1+1 = 2

F(4) = F(3) + F(2) = 2+1 = 3

و به همین ترتیب ادامه می‌یابد.

این روش ساده است و از نظر مفهومی کاملاً شبیه تعریف دنباله فیبوناچی است، اما به دلیل تکراری بودن محاسبات برای مقادیر بزرگ، کارایی آن پایین است. سورس کد الگوریتم فیبوناچی به روش بازگشتی به زبان پایتون در زیر آورده شده است.

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

روش تکراری (Iterative)

در این روش از الگوریتم فیبوناچی، از یک حلقه (loop) برای محاسبه مقدار nام استفاده می‌شود. این روش سریع‌تر از روش بازگشتی است، زیرا هر عدد فقط یک بار محاسبه می‌شود. به عبارتی  برای این کار، دو عدد اول (۰ و ۱) را به‌عنوان مقدمه در نظر می‌گیریم و سپس از یک حلقه استفاده می‌کنیم تا بقیه اعداد دنباله را محاسبه کنیم:

• شروع با ۰ و ۱
• در هر تکرار، دو عدد قبلی را جمع کرده و به عدد جدید برسیم
• حلقه ادامه پیدا می‌کند تا به عدد مورد نظر برسیم.

کد این روش به زبان پایتون به صورت زیر است:

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

روش برنامه‌نویسی پویا (Dynamic Programming)

در روش برنامه‌نویسی پویا، از حافظه برای ذخیره نتایج قبلی استفاده می‌شود تا از محاسبات تکراری جلوگیری کنیم. در واقع، وقتی یک عدد محاسبه می‌شود، آن را در یک آرایه ذخیره کرده و در محاسبات بعدی از آن استفاده می‌کنیم. این روش عملکرد بهتری نسبت به روش‌های قبلی دارد زیرا به‌جای محاسبه دوباره، نتایج قبلی را استفاده می‌کنیم و زمان اجرای الگوریتم کاهش می‌یابد.

کد این روش به زبان پایتون به صورت زیر است:

def fibonacci_dp(n):
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

کاربردهای الگوریتم فیبوناچی

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

علوم کامپیوتر

در علوم کامپیوتر از این الگوریتم برای حل مسائل مربوط به تقسیم و غلبه (Divide and Conquer) استفاده می‌شود، جایی که یک مسئله بزرگ به زیرمسئله‌های کوچک‌تر شکسته می‌شود. در بهینه‌سازی و محاسبات موازی نیز دنباله فیبوناچی به عنوان یک الگوی ساختاری در مدیریت منابع و زمان‌بندی کاربرد دارد.

زیست‌شناسی و پزشکی

در زیست‌شناسی و پزشکی، دنباله فیبوناچی برای مطالعه الگوهای رشد طبیعی و پیش‌بینی تغییرات جمعیتی استفاده می‌شود. به عنوان مثال، رشد جمعیت خرگوش‌ها که نمونه کلاسیک معرفی این دنباله توسط لئوناردو فیبوناچی بوده است، به درک رفتارهای جمعیتی در طبیعت کمک کرده است.

همچنین، کاربرد این دنباله در مدل‌سازی رشد سلولی، تحلیل ساختار DNA، و حتی چیدمان اندام‌های بدن انسان مشاهده شده است. به همین دلیل، الگوریتم فیبوناچی به عنوان یک مفهوم جهانی، فراتر از یک ایده ریاضی ساده عمل می‌کند و تأثیر عمیقی بر علم و زندگی بشر دارد.

مهندسی نرم افزار

در مهندسی نرم‌افزار، دنباله فیبوناچی برای تخمین‌ها و مدیریت پروژه‌ها استفاده می‌شود، به ویژه در روش اسکرام (Scrum) که یکی از متدولوژی‌های توسعه نرم‌افزار چابک است. اعداد فیبوناچی در تخمین اندازه وظایف و پیچیدگی کارها به تیم‌ها کمک می‌کنند تا به صورت منطقی و بر اساس تجربه، زمان لازم برای تکمیل وظایف را پیش‌بینی کنند.

هنر و معماری

دنباله فیبوناچی و نسبت طلایی، که از این دنباله به دست می‌آید، در هنر و معماری کاربردهای گسترده‌ای دارد. نسبت طلایی تقریباً برابر با ۱.۶۱۸ است و در طراحی‌های هنری و معماری به‌طور طبیعی برای ایجاد توازن، هارمونی و زیبایی استفاده می‌شود. این نسبت در بسیاری از آثار معروف هنر و معماری تاریخی به کار رفته است، از جمله در آثار معماران بزرگ همچون فیلیپ برونلوچتی در کلیسای سانتا ماریا دل فیوره در فلورانس یا در ساختارهایی همچون پیرامیدهای مصر و پارthenon در آتن. در هنر، این نسبت برای طراحی ترکیب‌بندی‌ها، نقاشی‌ها و مجسمه‌ها استفاده می‌شود تا چشم بیننده به‌طور ناخودآگاه جذب و راضی شود.

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

اقتصاد و مهندسی

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

نتیجه گیری

الگوریتم فیبوناچی یکی از مفاهیم اساسی در ریاضیات است که در بسیاری از حوزه‌ها کاربرد دارد. این دنباله از اعداد ابتدا با دو عدد ۰ و ۱ شروع می‌شود و هر عدد بعدی از جمع دو عدد قبلی به دست می‌آید. اعداد فیبوناچی معمولاً در اعداد صحیح و حتی در اعداد اعشاری از منظر مسائل مالی کاربرد دارند، زیرا می‌توانند در مدل‌سازی‌های اقتصادی و پیش‌بینی‌های مالی به کار روند.

جالب است که دنباله فیبوناچی تنها به اعداد مثبت محدود نمی‌شود، بلکه به اعداد منفی نیز گسترش می‌یابد و به نوعی دنباله‌ای از اعداد فیبوناچی منفی نیز وجود دارد. علاوه بر این، در دنباله فیبوناچی همیشه اولین عدد ۰ و دومین عدد ۱ است، که این دو عدد پایه‌گذار شروع این دنباله مهم در ریاضیات هستند.