======اعداد فیبوناچی و محاسبه سریع آن======
دنباله فیبوناچی از رابطه $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$$

====پیاده سازی====

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

<file c++ fibonacci.cpp>
int f(int n)
{
    if (n < 2)
        return 1;
    return f(n - 1) + f(n - 2);
}
</file>

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

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

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

<پاسخ>
خانه آخر باید توسط یک یک‌مینو و یا یک دو‌مینو پوشانده شود پس اگر $f(n)$ جواب مساله باشد آنگاه $f(n) = f(n - 1) + f(n - 2), f(0) = 1, f(1) = 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)$ محاسبه کرد.
<file c++ 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;
}
</file>