Fibonacci Sətirləri#2524

Fibonacci Sətirləri (Həll təhlili)

Fibonacci sətirləri rekursiv olaraq təyin olunur:

F_{n} = F_{n - 2} + F_{n - 1}

F_n = F_{n-2} + F_{n-1}

Bu o deməkdir ki, $F_{n}$ F_n sözü ard-arda iki hissədən ibarətdir:

ilk $F_{n - 2}$ F_{n-2} simvol — $F_{n - 2}$ F_{n-2} sözüdür,
növbəti $F_{n - 1}$ F_{n-1} simvol — $F_{n - 1}$ F_{n-1} sözüdür.

Buna görə, $F_{n}$ F_n sözündə $k$ -cı simvolu tapmaq üçün bütün sözü yaratmağa ehtiyac yoxdur. Yalnız həmin simvolun hansı hissədə olduğunu müəyyən etmək kifayətdir.

$F_{n} (k)$ F_n(k) ilə $F_{n}$ F_n sözünündəki $k$ -cı simvolunu ifadə edək.

Belə ki:

əgər $k \leq ∣ F_{n - 2} ∣$ k ≤ |F_{n-2}|, axtarılan simvol birinci hissədədir:

F_{n} (k) = F_{n - 2} (k)

F_n(k) = F_{n-2}(k)

əks halda (əgər $k > ∣ F_{n - 2} ∣)$ k > |F_{n-2}|), simvol ikinci hissədədir:

F_{n} (k) = F_{n - 1} (k - ∣ F_{n - 2} ∣)

F_n(k) = F_{n-1}(k - |F_{n-2}|)

Bu halda, məsələ daha kiçik indeksli sözlərdə simvolun axtarılmasına çevrilir.

Misal

$F_{6}$ F_6 sözünü nəzərdən keçirək, hansı ki aşağıdakı əlaqələrə malikdir:

$F_{6} = F_{4} + F_{5}$ F_6 = F_4 + F_5,
$∣ F_{4} ∣ = 5, ∣ F_{5} ∣ = 8$ |F_4| = 5, |F_5| = 8

$F_{6} (4)$ F_6(4) hesablayın. $k = 4 \leq ∣ F_{4} ∣ = 5$ k = 4 \le |F_4| = 5, demək $F_{6} (4) = F_{4} (4)$ F_6(4) = F_4(4).

$F_{6} (7)$ F_6(7) hesablayın. $k = 7 > ∣ F_{4} ∣ = 5$ k = 7 > |F_4| = 5, demək $F_{6} (7) = F_{5} (7 - 5) = F_{5} (2)$ F_6(7) = F_5(7 - 5) = F_5(2).

Alqoritmin realizasiyası

$f ib$ arrayi Fibonacci sətirlərin uzunluqlarını saxlayır:

$f ib [i]$ $F_{i}$ F_i sözünün uzunluğunu saxlayır.

#define MAX 44
int fib[MAX] = {1, 1};

solve funksiyası $F_{n}$ F_n sözündə $k$ -cı simvolu tam olaraq sözü yaratmadan qaytarır.

char solve(int n, int k)
{

Sadə halları fərqli şəkildə emal edirik: $n = 0$ n = 0 və $n = 1$ n = 1.

  if (n == 0) return 'a';
  if (n == 1) return 'b';

Bildiyimiz kimi, $F_{n} = F_{n - 2} + F_{n - 1}$ F_n = F_{n - 2} + F_{n - 1}.

Əgər $k \leq F_{n - 2}$ k \le F_{n - 2}, o zaman $k$ -cı simvol $F_{n - 2}$ F_{n - 2} sözündədir.
Əgər $k > F_{n - 2}$ k > F_{n - 2}, o zaman $k$ -cı simvol $F_{n - 1}$ F_{n - 1} sözündədir. Lakin onun mövqeyi birinci hissənin uzunluğuna görə dəyişir, beləliklə $k - F_{n - 2}$ k - F_{n - 2} nömrəli simvolu axtarırıq.

  if (k <= fib[n-2]) return solve(n - 2, k);
  return solve(n - 1, k - fib[n-2]);
}

Programın əsas hissəsi. İlk $M A X$ Fibonacci ədədlərini hesablayırıq.

for (int i = 2; i < MAX; i++)
  fib[i] = fib[i-1] + fib[i-2];

Testlərin sayı $t es t s$ oxuyuruq.

scanf("%d",&tests);
while (tests--)
{

Hər test üçün cavabı hesablayıb çap edirik.

  scanf("%d %d",&n,&k);
  printf("%c\n",solve(n,k));
}