پرش به محتویات

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

دنباله فیبوناچی به صورت زیر تعریف می‌شود:

$$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$$

عناصر اول این دنباله (OEIS A000045) عبارتند از:

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

ویژگی‌ها

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

  • اتحاد کاسینی:
$$F_{n-1} F_{n+1} - F_n^2 = (-1)^n$$

این را می‌توان با استقرا اثبات کرد. یک اثبات یک خطی توسط Knuth از طریق محاسبه دترمینان شکل ماتریسی ۲x۲ زیر به دست می‌آید.

  • قانون «جمع»:
$$F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$$
  • با اعمال اتحاد قبلی برای حالت $k = n$، به دست می‌آوریم:
$$F_{2n} = F_n (F_{n+1} + F_{n-1})$$

  • از این طریق می‌توانیم با استقرا اثبات کنیم که برای هر عدد صحیح مثبت $k$، $F_{nk}$ مضربی از $F_n$ است.

  • عکس این قضیه نیز درست است: اگر $F_m$ مضربی از $F_n$ باشد، آنگاه $m$ مضربی از $n$ است.

  • اتحاد ب.م.م:

$$GCD(F_m, F_n) = F_{GCD(m, n)}$$
  • اعداد فیبوناچی بدترین ورودی‌های ممکن برای الگوریتم اقلیدس هستند (قضیه لامه را در الگوریتم اقلیدس ببینید).

کدگذاری فیبوناچی

ما می‌توانیم از این دنباله برای کدگذاری اعداد صحیح مثبت به کلمات کد باینری استفاده کنیم. طبق قضیه زکندورف، هر عدد طبیعی $n$ را می‌توان به طور منحصر به فرد به صورت مجموعی از اعداد فیبوناچی نمایش داد:

$$N = F_{k_1} + F_{k_2} + \ldots + F_{k_r}$$

به طوری که $k_1 \ge k_2 + 2,\ k_2 \ge k_3 + 2,\ \ldots,\ k_r \ge 2$ باشد (یعنی: در این نمایش نمی‌توان از دو عدد فیبوناچی متوالی استفاده کرد).

نتیجه می‌شود که هر عددی را می‌توان به طور منحصر به فرد در کدگذاری فیبوناچی، کد کرد. و می‌توانیم این نمایش را با کدهای باینری $d_0 d_1 d_2 \dots d_s 1$ توصیف کنیم، که در آن $d_i$ برابر با $1$ است اگر $F_{i+2}$ در نمایش استفاده شده باشد. به انتهای کلمه کد یک $1$ اضافه می‌شود تا پایان آن را مشخص کند. توجه داشته باشید که این تنها جایی است که دو بیت ۱ متوالی ظاهر می‌شوند.

$$\begin{eqnarray} 1 &=& 1 &=& F_2 &=& (11)_F \\ 2 &=& 2 &=& F_3 &=& (011)_F \\ 6 &=& 5 + 1 &=& F_5 + F_2 &=& (10011)_F \\ 8 &=& 8 &=& F_6 &=& (000011)_F \\ 9 &=& 8 + 1 &=& F_6 + F_2 &=& (100011)_F \\ 19 &=& 13 + 5 + 1 &=& F_7 + F_5 + F_2 &=& (1001011)_F \end{eqnarray}$$

کدگذاری یک عدد صحیح $n$ را می‌توان با یک الگوریتم حریصانه ساده انجام داد:

  1. اعداد فیبوناچی را از بزرگترین به کوچکترین پیمایش کنید تا عددی را بیابید که کوچکتر یا مساوی $n$ باشد.

  2. فرض کنید این عدد $F_i$ است. $F_i$ را از $n$ کم کنید و در موقعیت $i-2$ از کلمه کد یک $1$ قرار دهید (اندیس‌گذاری از ۰ از چپ‌ترین بیت به راست‌ترین بیت).

  3. این کار را تا زمانی که باقیمانده‌ای وجود نداشته باشد تکرار کنید.

  4. یک $1$ نهایی به کلمه کد اضافه کنید تا پایان آن را مشخص کند.

برای کدگشایی یک کلمه کد، ابتدا $1$ نهایی را حذف کنید. سپس، اگر بیت $i$-ام (اندیس‌گذاری از ۰ از چپ‌ترین بیت به راست‌ترین بیت) برابر ۱ بود، $F_{i+2}$ را به عدد اضافه کنید.

فرمول‌هایی برای عدد فیبوناچی $n$-ام

عبارت فرم بسته

فرمول زیر به «فرمول بینه» معروف است، هرچند که پیش از او توسط مواور نیز شناخته شده بود:

$$F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

اثبات این فرمول با استقرا آسان است، اما می‌توان آن را با کمک مفهوم توابع مولد یا با حل یک معادله تابعی نیز به دست آورد.

می‌توان بلافاصله متوجه شد که قدر مطلق جمله دوم همیشه کمتر از $1$ است و همچنین به سرعت (به صورت نمایی) کاهش می‌یابد. از این رو، مقدار جمله اول به تنهایی «تقریباً» برابر با $F_n$ است. این را می‌توان به طور دقیق به صورت زیر نوشت:

$$F_n = \left[\frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n}{\sqrt{5}}\right]$$

که در آن براکت‌ها نشان‌دهنده گرد کردن به نزدیک‌ترین عدد صحیح هستند.

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

محاسبه فیبوناچی در زمان خطی

عدد فیبوناچی $n$-ام را می‌توان به راحتی در زمان $O(n)$ با محاسبه یک به یک اعداد تا $n$ پیدا کرد. با این حال، راه‌های سریع‌تری نیز وجود دارد که در ادامه خواهیم دید.

با استفاده از فرمول $F_n = F_{n-1} + F_{n-2}$ و شروع از مقادیر پایه $F_0$ و $F_1$ می‌توانیم اعداد را به صورت تکراری محاسبه کنیم.

```cpp file=fibonacci_linear int fib(int n) { int a = 0; int b = 1; for (int i = 0; i < n; i++) { int tmp = a + b; a = b; b = tmp; } return a; } 

با این روش، به یک راه حل خطی با زمان $O(n)$ می‌رسیم.

### فرم ماتریسی

برای رفتن از $(F_n, F_{n-1})$ به $(F_{n+1}, F_n)$، می‌توانیم رابطه بازگشتی خطی را به صورت ضرب ماتریس ۲x۲ بیان کنیم:

$$
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
F_n \\
F_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
F_n + F_{n-1}  \\
F_{n}
\end{pmatrix}
=
\begin{pmatrix}
F_{n+1}  \\
F_{n}
\end{pmatrix}
$$

این به ما امکان می‌دهد که تکرار رابطه بازگشتی را به عنوان ضرب ماتریس مکرر در نظر بگیریم که ویژگی‌های خوبی دارد. به طور خاص،

$$
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^n
\begin{pmatrix}
F_1 \\
F_0
\end{pmatrix}
=
\begin{pmatrix}
F_{n+1}  \\
F_{n}
\end{pmatrix}
$$

که در آن $F_1 = 1, F_0 = 0$ است.
در واقع، از آنجایی که

$$
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
= \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}
$$

می‌توانیم از ماتریس به طور مستقیم استفاده کنیم:

$$
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n
= \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}
$$

بنابراین، برای یافتن $F_n$ در زمان $O(\log n)$، باید ماتریس را به توان n برسانیم. (به [توان‌رسانی دودویی](binary-exp.md) مراجعه کنید).

```cpp file=fibonacci_matrix
struct matrix {
    long long mat[2][2];
    matrix friend operator *(const matrix &a, const matrix &b){
        matrix c;
        for (int i = 0; i < 2; i++) {
          for (int j = 0; j < 2; j++) {
              c.mat[i][j] = 0;
              for (int k = 0; k < 2; k++) {
                  c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
              }
          }
        }
        return c;
    }
};

matrix matpow(matrix base, long long n) {
    matrix ans{ {
      {1, 0},
      {0, 1}
    } };
    while (n) {
        if(n&1)
            ans = ans*base;
        base = base*base;
        n >>= 1;
    }
    return ans;
}

long long fib(int n) {
    matrix base{ {
      {1, 1},
      {1, 0}
    } };
    return matpow(base, n).mat[0][1];
}

روش دو برابر کردن سریع

با بسط دادن عبارت ماتریسی بالا برای $n = 2\cdot k$

$$ \begin{pmatrix} F_{2k+1} & F_{2k}\\ F_{2k} & F_{2k-1} \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{2k} = \begin{pmatrix} F_{k+1} & F_{k}\\ F_{k} & F_{k-1} \end{pmatrix} ^2 $$

می‌توانیم این معادلات ساده‌تر را پیدا کنیم:

$$ \begin{align} F_{2k+1} &= F_{k+1}^2 + F_{k}^2 \\ F_{2k} &= F_k(F_{k+1}+F_{k-1}) = F_k (2F_{k+1} - F_{k})\\ \end{align}.$$

بنابراین با استفاده از دو معادله بالا، اعداد فیبوناچی را می‌توان به راحتی با کد زیر محاسبه کرد:

```cpp file=fibonacci_doubling pair fib (int n) { if (n == 0) return {0, 1};

auto p = fib(n >> 1);
int c = p.first * (2 * p.second - p.first);
int d = p.first * p.first + p.second * p.second;
if (n & 1)
    return {d, c + d};
else
    return {c, d};

} ```

کد بالا $F_n$ و $F_{n+1}$ را به صورت یک زوج برمی‌گرداند.

تناوب به پیمانه p

دنباله فیبوناچی را به پیمانه $p$ در نظر بگیرید. ثابت خواهیم کرد که این دنباله متناوب است.

این را با برهان خلف ثابت می‌کنیم. $p^2 + 1$ زوج اول از اعداد فیبوناچی را به پیمانه $p$ در نظر بگیرید:

$$(F_0,\ F_1),\ (F_1,\ F_2),\ \ldots,\ (F_{p^2},\ F_{p^2 + 1})$$

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

اکنون دو زوج از باقیمانده‌های یکسان را با کوچکترین اندیس‌ها در دنباله انتخاب می‌کنیم. فرض کنید این زوج‌ها $(F_a,\ F_{a + 1})$ و $(F_b,\ F_{b + 1})$ باشند. ثابت خواهیم کرد که $a = 0$ است. اگر این نادرست بود، دو زوج قبلی $(F_{a-1},\ F_a)$ و $(F_{b-1},\ F_b)$ وجود داشتند که طبق ویژگی اعداد فیبوناچی، آنها نیز باید برابر باشند. با این حال، این با این واقعیت که ما زوج‌هایی با کوچکترین اندیس‌ها را انتخاب کرده‌ایم در تناقض است و اثبات ما را مبنی بر عدم وجود پیش‌دوره (یعنی اعداد از $F_0$ به بعد متناوب هستند) کامل می‌کند.

مسائل تمرینی