Фибоначчийн тоо¶

Фибоначчийн дараалал дараах байдлаар тодорхойлогдоно:

$$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$$

Үүнийг индукцээр батлаж болно. Кнутын нэг мөрийн баталгаа нь доорх 2x2 матриц хэлбэрийн тодорхойлогчийг авахаас гарна.

"Нэмэх" дүрэм:

$$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$ хоёртын кодоор тодорхойлж болно, энд илэрхийлэлд $F_{i+2}$ ашиглагдсан бол $d_i$ нь $1$ байна. Код үгийн төгсгөлийг заахын тулд кодын араас $1$ нэмнэ. Энэ бол дараалсан хоёр 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$-г кодчлохыг энгийн greedy algorithm-аар хийж болно:

Фибоначчийн тоонуудыг хамгийн томоос хамгийн бага руу давтаж, $n$-ээс бага буюу тэнцүү тоог олтол үргэлжлүүл.
Энэ тоо нь $F_i$ байсан гэж үзье. $n$-ээс $F_i$-г хасаад код үгийн $i-2$ байрлалд $1$ тавь (зүүнээс баруун тийш битийг 0-ээс эхлэн дугаарлана).
Үлдэгдэл байхгүй болтол давт.
Код үгийн төгсгөлийг заахын тулд эцэст нь $1$ нэм.

Код үгийг тайлахын тулд эхлээд эцсийн $1$-г хас. Дараа нь $i$ дугаар бит тавигдсан бол (зүүнээс баруун тийш битийг 0-ээс эхлэн дугаарлана) тоон дээр $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$ дугаар Фибоначчийн тоог $n$ хүртэл тоонуудыг нэг нэгээр нь тооцоолох замаар $O(n)$-д амархан олж болно. Гэвч доор үзэх шиг илүү хурдан аргууд бас байдаг.

Бид $F_n = F_{n-1} + F_{n-2}$ томьёог ашиглахын тулд давталтын аргаас эхэлж болно, тиймээс эдгээр утгыг массивт урьдчилан тооцоолно. $F_0$ ба $F_1$-ийн суурь тохиолдлыг харгалзан үзнэ.

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;
}

Ингэснээр бид дараалал дахь $n$-ээс өмнөх бүх утгыг хадгалсан шугаман шийд, $O(n)$ хугацаа авна.

Матриц хэлбэр¶

$(F_n, F_{n-1})$-ээс $(F_{n+1}, F_n)$ рүү шилжихийн тулд шугаман рекуррент хамаарлыг 2x2 матрицын үржүүлэлт хэлбэрээр илэрхийлж болно:

$$ \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 зэрэгт дэвшүүлэх ёстой. (Хоёртын зэрэгт дэвшүүлэлт-ийг үзнэ үү)

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}.$$

Тиймээс дээрх хоёр тэгшитгэлийг ашиглан Фибоначчийн тоог дараах кодоор амархан тооцоолж болно:

pair<int, int> 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};
}

The above code returns $F_n$ and $F_{n+1}$ as a pair.

p модулиар үечлэл¶

Фибоначчийн дарааллыг $p$ модулиар авч үзье. Бид энэ дараалал үечилсэн болохыг батлана.

Үүнийг эсрэгээс нь баталъя. $p$ модулиар авсан Фибоначчийн тооны эхний $p^2 + 1$ хосыг авч үзье:

$$(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$-ээс эхлэн үечилсэн) гэдгийг батална.