Yenə də Fibonacçi ədədləri (Həll təhlili)

Теorema. Fibonacci ədədləri üçün aşağıdakı forma yerinə yetirilir:

S (n) = F (0) + F (1) + ... + F (n) = F (n + 2) - 1

S(n) = F(0) + F(1) + ... + F(n) = F(n + 2) - 1

İspat. İnduksiya ilə ispat gətirək.

İnduksiya bazası. $n = 0$ n = 0 olduğu zaman:

F (0) = F (2) - 1,

F(0) = F(2) - 1,

və ya $0 = 1 - 1$ 0 = 1 - 1, bu doğrudur.

İnduksiya addımı. Var sayaq ki:

S (n) = F (n + 2) - 1

S(n) = F(n + 2) - 1

O zaman:

S (n + 1) = F (0) + F (1) + ... + F (n) + F (n + 1) = (F (n + 2) - 1) + F (n + 1) = F (n + 3) - 1,

S(n + 1) = F(0) + F(1) + ... + F(n) + F(n + 1) = \\ (F(n + 2) - 1) + F(n + 1) = F(n + 3) - 1,

Bu da ispat ediləndir.

Belə ki istənilən cəmi

S = F (a) + F (a + 1) + ... + F (b)

S = F(a) + F(a + 1) + ... + F(b)

əldə etmək mümkündür

S = S (b) - S (a - 1)

S = S(b) - S(a - 1)

Binet formula ilə Fibonacci saylarının hesablanması

Fibonacci ədədləri üçün generasiya funksiyasını nəzərdən keçirək ( $F_{0} = 0, F_{1} = 1$ F_0 = 0, F_1 = 1):

G (x) = n = 0 \sum \infty F_{n} x^{n} = F_{0} + F_{1} x + n = 2 \sum \infty F_{n} x^{n} = F_{0} + F_{1} x + n = 2 \sum \infty (F_{n - 1} + F_{n - 2}) x^{n} = x + n = 2 \sum \infty F_{n - 1} x^{n} + n = 2 \sum \infty F_{n - 2} x^{n} = x + x n = 1 \sum \infty F_{n} x^{n} + x^{2} n = 0 \sum \infty F_{n} x^{n} = x + x G (x) + x^{2} G (x)

G(x) = \sum_{n = 0}^∞ F_n x^n = F_0 + F_1x + \sum_{n = 2}^∞ F_n x^n = \\ F_0 + F_1x + \sum_{n = 2}^∞ (F_{n - 1} + F_{n - 2}) x^n = \\ x + \sum_{n = 2}^∞ F_{n - 1} x^n + \sum_{n = 2}^∞ F_{n - 2} x^n = \\ x + x \sum_{n = 1}^∞ F_n x^n + x^2 \sum_{n = 0}^∞ F_n x^n = \\ x + xG(x) + x^2G(x)

Buradan:

G (x) (1 - x - x^{2}) = x, G (x) = \frac{x}{1 - x - x ^{2}}

G(x) (1 - x - x^2) = x, \\ G(x) = \frac{x}{1 - x - x^2}

Generasiya funksiyasını sadə fraksiyonlara ayıraq. Müqavimətlərin kökünü tapın:

1 - x - x^{2} = (1 - φ x) (1 - ψ x),

1 - x - x^2 = (1 - φx) (1 - ψx),

burada

φ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}

φ = \frac{1 + \sqrt{5}}{2}, ψ = \frac{1 - \sqrt{5}}{2}

İndi generasiya funksiyasını belə təqdim edək:

\frac{x}{1 - x - x ^{2}} = \frac{A}{1 - φ x} + \frac{B}{1 - ψ x}

\frac{x}{1 - x - x^2} = \frac{A}{1 - φx} + \frac{B}{1 - ψx}

Sistemi həll edərək:

A = \frac{1}{5}, B = - \frac{1}{5}

A = \frac{1}{\sqrt{5}}, B = -\frac{1}{\sqrt{5}}

Nəzərə alaraq ki

\frac{1}{1 - r x} = n = 0 \sum \infty r^{n} x^{n},

\frac{1}{1 - rx} = \sum_{n = 0}^∞ r^n x^n,

Generasiya funksiyasını belə yaza bilərik:

G (x) = \frac{1}{5} (\frac{1}{1 - φ x} + \frac{1}{1 - ψ x}) = \frac{1}{5} n = 0 \sum \infty (φ^{n} - ψ^{n}) x^{n}

G(x) = \frac{1}{\sqrt{5}} \left( \frac{1}{1 - φx} + \frac{1}{1 - ψx} \right) = \frac{1}{\sqrt{5}} \sum_{n = 0}^∞ (φ^n - ψ^n) x^n

Amma nəzərə alsaq ki

G (x) = n = 0 \sum \infty F_{n} x^{n}

G(x) = \sum_{n = 0}^∞ F_n x^n

$F_{n}$ F_n-nin x^n əmsallarını bərabərləşdirərək:

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5} = \frac{1}{5} ((\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}) = \frac{( 1 + 5 ) ^{n} - ( 1 - 5 ) ^{n}}{2 ^{n} 5}

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

Fibonacci ədədlərinin identiklik ilə hesablanması

Fibonacci ədədləri üçün aşağıdakı identiklik tanınır:

F_{n + m} = F_{m} \cdot F_{n + 1} + F_{m - 1} \cdot F_{n}

F_{n + m} = F_m \cdot F_{n+1} + F_{m - 1} \cdot F_n

Bununla xüsusi halları tam göstərmək mümkündür:

$m = n$ m = n olduğu zaman $F_{2 n} = F_{n} \cdot F_{n + 1} + F_{n - 1} \cdot F_{n}$ F_{2n} = F_n \cdot F_{n + 1} + F_{n - 1} \cdot F_n
$m = n + 1$ m = n + 1 olduğu zaman $F_{2 n + 1} = F_{n + 1} \cdot F_{n + 1} + F_{n} \cdot F_{n}$ F_{2n + 1} = F_{n + 1} \cdot F_{n + 1} + F_n \cdot F_n

Bu formulalar Fibonacci ədədlərini "böl və hökm sür" metoduyla hesablamağa, $F_{n}$ F_n hesabını təxminən iki qat kiçik indeks dəyərlərinə salmağa imkan verir.

Əsas halları ayrıca emal edərək:

F_{0} = 0, F_{1} = F_{2} = 1

F_0 = 0, F_1 = F_2 = 1

Bu yanaşma ilə rekursiyanın dərinliyi $l o g_{2} n$ log_2n-ə proporisonal olur və alqoritmin vaxt kompleksliyi $O (l o g_{2} n)$ O(log_2n) təşkil edir.

Nümunə

Binet formuluna görə bir neçə Fibonacci ədədi hesablayaq, böyük modlla $Z_{p} (5)$ Z_p (\sqrt{5}) geniş alanında işlə.

F_{2} = \frac{1}{5} (\frac{1 + 5}{2})^{2} - (\frac{1 - 5}{2})^{2} = \frac{( 1 + 5 ) ^{2} - ( 1 - 5 ) ^{2}}{2 ^{2} 5} = \frac{( 6 + 2 5 ) - ( 6 - 2 5 )}{2 ^{2} 5} = \frac{4 5}{4 5} = 1 F_{3} = \frac{1}{5} (\frac{1 + 5}{2})^{3} - (\frac{1 - 5}{2})^{3} = \frac{( 1 + 5 ) ^{3} - ( 1 - 5 ) ^{3}}{2 ^{3} 5} = \frac{( 16 + 8 5 ) - ( 16 - 8 5 )}{2 ^{3} 5} = \frac{16 5}{8 5} = 2 F_{4} = \frac{1}{5} (\frac{1 + 5}{2})^{4} - (\frac{1 - 5}{2})^{4} = \frac{( 6 + 2 5 ) ^{2} - ( 6 - 2 5 ) ^{2}}{2 ^{4} 5} = \frac{( 56 + 24 5 ) - ( 56 - 24 5 )}{2 ^{4} 5} = \frac{48 5}{16 5} = 3

F_2 = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^2 - \left( \frac{1 - \sqrt{5}}{2} \right)^2 \right) = \frac{(1 + \sqrt{5})^2 - (1 - \sqrt{5})^2}{2^2 \sqrt{5}} = \frac{(6 + 2\sqrt{5}) - (6 - 2\sqrt{5})}{2^2 \sqrt{5}} = \frac{4\sqrt{5}}{4\sqrt{5}} = 1 \\ F_3 = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^3 - \left( \frac{1 - \sqrt{5}}{2} \right)^3 \right) = \frac{(1 + \sqrt{5})^3 - (1 - \sqrt{5})^3}{2^3 \sqrt{5}} = \frac{(16 + 8\sqrt{5}) - (16 - 8\sqrt{5})}{2^3 \sqrt{5}} = \frac{16\sqrt{5}}{8\sqrt{5}} = 2 \\ F_4 = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^4 - \left( \frac{1 - \sqrt{5}}{2} \right)^4 \right) = \frac{(6 + 2\sqrt{5})^2 - (6 - 2\sqrt{5})^2}{2^4 \sqrt{5}} = \frac{(56 + 24\sqrt{5}) - (56 - 24\sqrt{5})}{2^4 \sqrt{5}} = \frac{48\sqrt{5}}{16\sqrt{5}} = 3

Formulları tətbiq edək:

$m = n$ m = n olduğu zaman $F_{2 n} = F_{n} \cdot F_{n + 1} + F_{n - 1} \cdot F_{n}$ F_{2n} = F_n \cdot F_{n + 1} + F_{n - 1} \cdot F_n
$m = n + 1$ m = n + 1 olduğu zaman $F_{2 n + 1} = F_{n + 1} \cdot F_{n + 1} + F_{n} \cdot F_{n}$ F_{2n + 1} = F_{n + 1} \cdot F_{n + 1} + F_n \cdot F_n

F_{6} = F_{3} \cdot F_{4} + F_{2} \cdot F_{3} = 2 \cdot 3 + 1 \cdot 2 = 6 + 2 = 8, F_{7} = F_{4}^{2} + F_{3}^{2} = 3^{2} + 2^{2} = 9 + 4 = 13

F_6 = F_3 \cdot F_4 + F_2 \cdot F_3 = 2 \cdot 3 + 1 \cdot 2 = 6 + 2 = 8, \\ F_7 = F_4^2 + F_3^2 = 3^2 + 2^2 = 9 + 4 = 13

Alqoritm realizasiyası

MOD məsaməsi ilə hesablama məhsulunu ləğv edin.

#define MOD 1000000007

Yaddaşda artıq hesablanmış Fibonacci ədədlərini saxlamaq üçün olan tip $ma p$ olan $f ib$ dəyişənini təyinn edin.

map<long long, long long> fib;

f funksiyası $n$ -ci Fibonacci ədədini MOD üzərindən hesablamaq üçün.

long long f(long long n)
{
  if (n == 0) return 0;
  if (n == 1) return 1;
  if (n == 2) return 1;

Əgər $n$ -ci Fibonacci ədəd daha öncə hesablanıbsa və $f ib$ -də saxlanıbsa, dərhal geri qaytarılır, yenidən hesablama olmadan.

  if (fib[n]) return fib[n];

Sonra $n$ ədədi istifadə edərək parçalama:

$n = 2 k + 1$ n = 2k + 1 — tək hallar: $F_{n} = F_{k}^{2} + F_{k + 1}^{2}$ F_n = F_k^2 + F_{k + 1}^2.
$n = 2 k$ n = 2k — cüt hallar: $F_{n} = F_{k} \cdot F_{k + 1} + F_{k - 1} \cdot F_{k}$ F_n = F_k \cdot F_{k + 1} + F_{k - 1} \cdot F_k.

  long long k = n / 2;

Nəticəni yadda saxlayın və geri qaytarın.

  if (n % 2 == 1) // n = 2*k + 1
    return fib[n] = (f(k) * f(k) + f(k + 1) * f(k + 1)) % MOD;
  else // n = 2*k
    return fib[n] = (f(k) * f(k + 1) + f(k - 1) * f(k)) % MOD;
}

Proqramın əsas hissəsi. Hər test üçün giriş məlumatlarını oxuyub cavabını çıxarır.

while (scanf("%lld %lld", &a, &b) == 2)
  printf("%lld\n", (f(b + 2) - f(a + 1) + MOD) % MOD);

Alqoritm realizasiyası – Binet formulu

MOD məsaməsi ilə hesablama məhsulunu ləğv edin.

#define MOD 1000000007

Struktur $N u m$ -u $x + y 5$ x + y \sqrt{5} formulu olan ədədin saxlanması üçün təyin edin.

struct Num
{
  long long x, y; // x + y*sqrt(c)
  Num(long long x_ = 0, long long y_ = 0) : x(x_), y(y_) {}
};

$Z_{p} (5)$ Z_p (\sqrt{5}) sahəsində vurmağı həyata keçirək. mult funksiyası $a$ və $b$ ədədlərinin hasilini geri qaytarır.

Num mult(Num& a, Num& b)
{
  Num res;
  res.x = (a.x * b.x + 5 * a.y % MOD * b.y) % MOD;
   res.y = (a.x * b.y + a.y * b.x) % MOD;
   return res;
}

C++

pow funksiyası $ba s e^{n}$ base^n olan $ba se$ sahəsində $Z_{p} (5)$ Z_p (\sqrt{5}) hasilini verir.

Num pow(Num base, long long n)
{
  Num res = { 1, 0 }; // sahənin birliyi
  while (n > 0)
  {
    if (n & 1)
      res = mult(res, base);
    base = mult(base, base);
    n >>= 1;
  }
  return res;
}

C++

modpow funksiyası $a^{k} m o d p$ a^k~mod~p dəyərini geri qaytarır.

long long pow(long long x, long long n)
{
  long long res = 1;
  x %= MOD;
  while (n > 0)
  {
    if (n & 1) res = res * x % MOD;
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}

C++

fib funksiyası $n$ -ci Fibonacci ədədini hesablamaq üçün.

long long fib(long long n)
{

φ və ψ üçün məhsulların başlanğıcını təyin edin $φ = 1 + 5$ φ = 1 + \sqrt{5} və $ψ = 1 - 5$ ψ = 1 - \sqrt{5}.

  Num phi(1, 1);
  Num psi(1, MOD - 1);

$A = φ^{n}$ A = φ^n və $B = ψ^{n}$ B = ψ^n sonu na hesablama.

  Num A = pow(phi, n);
  Num B = pow(psi, n);

Çünki:

F_{n} = \frac{1}{5} ((\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}) = \frac{( 1 + 5 ) ^{n} - ( 1 - 5 ) ^{n}}{2 ^{n} 5} = \frac{( A _{x} + A _{y} 5 ) - ( B _{x} + B _{y} 5 )}{2 ^{n} 5},

F_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right) = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}} = \frac{(A_x + A_y \sqrt{5}) - (B_x + B_y \sqrt{5})}{2^n \sqrt{5}},

Ayrı yazılış numeratorsunu $A$ , $B$ və denominatoru hesabla.

Qeyd edək ki, burada $A_{x} = B_{x}$ A_x = B_x (bu səbəbdən $A_{x} - B_{x} = 0$ A_x - B_x = 0) və $5$ \sqrt{5}-nin numeratorunda əmsal $A_{y} - B_{y}$ A_y - B_y-ə bərabərdir.

  long long numerator = (A.y - B.y + MOD) % MOD;

$2^{n}$ 2^n-i denominatoru içərisində hesablama.

  long long denom = pow(2, n);

Numerator və denominator $5$ \sqrt{5} mürəkkəbi saxlayır. Bu fraksiyanı salın və ən son nəticəni hesablamaq üçün

(A_{y} - B_{y}) \cdot (2^{n})^{- 1} = n u m er a t or \cdot d e n o m^{- 1}

(A_y - B_y) \cdot (2^n)^{-1} = numerator \cdot denom^{-1}

  long long denom_inv = pow(denom, MOD - 2);
  return numerator * denom_inv % MOD;
}

Proqramın əsas hissəsi. Hər test üçün giriş məlumatlarını oxuyub cavabını çıxarır.

while (scanf("%lld %lld", &a, &b) == 2)
  printf("%lld\n", (fib(b + 2) - fib(a + 1) + MOD) % MOD);