دنباله فیبوناچی از رابطه $f(n) = f(n - 1) + f(n - 2), f(0) = 1, f(1) = 1$ به دست می‌آید. عدد‌های اول این دنباله به شکل زیر است.

$$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89$$

ساده ترین روش پیاده‌سازی روش محاسبه مستقیم است.

fibonacci.cpp

int f(int n)
{
    if (n < 2)
        return 1;
    return f(n - 1) + f(n - 2);
}

این روش, روش سریعی نیست. در واقع می‌توان نشان داد زمان اجرای کد بالا $O(f(n))$ است. برای اینکه در کد بالا $f(i)$ یک بار محاسبه شود می‌توان از روش برنامه‌نویسی پویا استفاده کرد تا به زمان اجرای $O(n)$ رسید.

ابتدا سعی کنید مساله زیر را حل کنید.

مساله: به چند روش می‌توان خانه‌های یک جدول $1 \times n$ را با دومینو و یک‌مینو (مربع $1 \times 1$) پوشاند؟

در واقع مساله بالا معادل همان دنباله فیبوناچی است. حال رابطه دیگری برای این مساله به دست می‌آوریم. فرض کنید بخواهیم $f(2n)$ را به دست آوریم. اگر جدول را به دو جدول $1 \times n$ تقسیم کنیم. یک حالت این است که این دو تکه کاملا مستقل از هم باشند و حالت دیگر این است که یک دومینو یک خانه از هر کدام از این دو تکه را پوشانده باشد که در آن صورت دو جدول $1 \times (n - 1)$ مستقل به دست می‌آید. بنابراین می‌توان نتیجه گرفت که

$$f(2n) = f(n) \times f(n) + f(n - 1) \times f(n - 1)$$ همچنین با استدلالی مشابه می‌توان نشان داد $$f(2n + 1) = f(n + 1) \times f(n) + f(n) \times f(n - 1) = f(n) \times (f(n + 1) + f(n - 1)) = f(n) \times (f(n) + 2f(n - 1))$$ بنابراین در محاسبه فیبوناچی از روی $f(n - 1)$ و $f(n)$ می‌توان $f(2n)$ و $f(2n + 1)$ را به دست آورد. پس در با توجه به فرمول‌های بالا می‌توان $f(n)$ را با زمان اجرای $O(log n)$ محاسبه کرد.

fibonacci.cpp

pair<int, int> f_helper(int n) // Returns pair of f(n) and f(n + 1)
{
    if (n == 0)
        return make_pair(1, 1);
    if (n & 1)
    {
        pair<int, int> res = f_helper(n - 1);
        swap(res.first, res.second);
        res.second += res.first;
        return res;
    }
    pair<int, int> ans, res = f_helper(n / 2 - 1);
    ans.first = res.second * res.second + res.first * res.first;
    ans.second = res.second * (res.second + 2 * res.first);
    return ans;
}
int f(int n)
{
    return f_helper(n).first;
}