توجه! قبل از مطالعه‌ی این مطلب، جهت آشنایی و دریافت جزئیات بیشتر معرفی دنباله فیبوناچی را ببینید.

روش‌های مختلفی برای یافتن جمله‌ی nاُم دنباله‌ی فیبوناچی وجود دارد. در این مطلب سعی می‌کنم به چندین روش مسئله‌ی یافتن جمله‌ی nاُم دنباله‌ی فیبوناچی را حل کنم.

1#include <iostream>
2using namespace std;
3void Move(int n, char srcPeg, char trgPeg, char tmpPeg) {
4  if (n == 1)
5    cout << "Move disk #1 from peg "
6      << srcPeg << " to " << trgPeg << endl;
7  else {
8    Move(n - 1, srcPeg, tmpPeg, trgPeg);
9    cout << "Move disk #" << n << " from peg "
10      << srcPeg << " to " << trgPeg << endl;
11    Move(n - 1, tmpPeg, trgPeg, srcPeg);
12  }
13}
14void main() {
15  int n;
16  cin >> n;
17  Move(n, 'A', 'C', 'B');
18}

تابع Move() در خط 17 از داخل تابع main() برای جابه‌جایی n مهره فراخوانی شده است. آرگومان‌های ارسالی به تابع به‌ترتیب عبارتند از تعداد مهره‌ها (اندازه‌ی مسئله)، برچسب میله‌ی مبداء (در اینجا A)، برچسب میله‌ی مقصد (C) و برچسب میله‌ی کمکی (B). این تابع بصورت بازگشتی طراحی شده و همان‌طور که ملاحظه می‌کنید برای هر تعداد مهره مانند n، دو بار در خطوط 8 و 11 با اندازه‌ی کوچکتر (n-1) بازفراخوانی می‌شود. ضمن این‌که مابین دو فراخوانی بازگشتی، نسبت به جابجایی مهره‌ی بزرگتر نیز اقدام می‌کند. بنابراین می‌توان گفت که زمان جابجایی n مهره عبارتست از مجموع زمان‌های دو بار جابجایی n-1 مهره به اضافه‌ی یک:

T(n) = 2 × T(n - 1) + 1

رابطه‌ی بازگشتی بالا را حل می‌کنیم. با تغییر n به n-1 داریم:

T(n - 1) = 2 × T(n - 2) + 1

با جایگذاری رابطه‌ی اخیر در رابطه‌ی قبلی داریم:

T(n) = 2 × [2 × T(n - 2) + 1] + 1 = 4 × T(n - 2) + 3

به همین ترتیب با تغییر n به n-2 داریم:

T(n - 2) = 4 × T(n - 4) + 3

با جایگذاری رابطه‌ی اخیر در رابطه‌ی قبلی داریم:

T(n) = 4 × [4 × T(n - 4) + 3] + 3 = 16 × T(n - 4) + 15

با ادامه‌ی این روند به الگوی زیر خواهیم رسید:

T(n) = 2ⁱ × T(n - i) + 2ⁱ - 1

با توجه به این‌که T(1) = 1، لذا با قرار دادن n - i = 1 ⇔ i = n - 1 خواهیم داشت:

T(n) = 2^n-1 × T(1) + 2^n-1 - 1 = 2^n-1 + 2^n-1 - 1
T(n) = 2 × 2^n-1 - 1 = 2ⁿ - 1

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

برای آشنایی با نماد O (اُ بزرگ) و دریافت جزئیات بیشتر در مورد مرتبه‌ی زمانی، مطلب مربوط به تحلیل کارایی و محاسبه‌ی پیچیدگی زمانی الگوریتم‌ها را ببینید.