Рядки Фібоначчі#2524

Рядки Фібоначчі (Розбір)

Фібоначчієві рядки визначаються рекурентно:

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

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

Це означає, що рядок $F_{n}$ F_n складається з двох частин:

перші $F_{n - 2}$ F_{n-2} символи — це рядок $F_{n - 2}$ F_{n-2},
наступні $F_{n - 1}$ F_{n-1} символи — це рядок $F_{n - 1}$ F_{n-1}.

Отже, щоб знайти $k$ -й символ рядка $F_{n}$ F_n, не потрібно будувати весь рядок. Достатньо визначити, в якій з двох частин він знаходиться.

Позначимо через $F_{n} (k)$ F_n(k) $k$ -ий символ рядка $F_{n}$ F_n.

Тоді:

якщо $k \leq ∣ F_{n - 2} ∣$ k ≤ |F_{n-2}|, то шуканий символ знаходиться в першій частині:

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

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

інакше (якщо $k > ∣ F_{n - 2} ∣)$ k > |F_{n-2}|), символ лежить у другій частині:

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

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

Таким чином, задача зводиться до пошуку символа в рядках з меншими індексами.

Приклад

Розглянемо рядок $F_{6}$ F_6, для якого мають місце співвідношення:

$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). Оскільки $k = 4 \leq ∣ F_{4} ∣ = 5$ k = 4 \le |F_4| = 5, то $F_{6} (4) = F_{4} (4)$ F_6(4) = F_4(4).

Обчислимо $F_{6} (7)$ F_6(7). Оскільки $k = 7 > ∣ F_{4} ∣ = 5$ k = 7 > |F_4| = 5, то $F_{6} (7) = F_{5} (7 - 5) = F_{5} (2)$ F_6(7) = F_5(7 - 5) = F_5(2).

Реалізація алгоритму

У масиві $f ib$ зберігаються довжини фібоначчієвих рядків:

$f ib [i]$ містить довжину рядка $F_{i}$ F_i.

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

Функція solve повертає $k$ -й символ рядка $F_{n}$ F_n, не будучи сам рядок цілком.

char solve(int n, int k)
{

Окремо оброблюємо базові випадки $n = 0$ n = 0 і $n = 1$ n = 1.

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

Відомо, що $F_{n} = F_{n - 2} + F_{n - 1}$ F_n = F_{n - 2} + F_{n - 1}.

Якщо $k \leq F_{n - 2}$ k \le F_{n - 2}, то $k$ -й символ лежить у рядку $F_{n - 2}$ F_{n - 2}.
Якщо $k > F_{n - 2}$ k > F_{n - 2}, то $k$ -й символ лежить у рядку $F_{n - 1}$ F_{n - 1}. Однак його позиція зміщена на довжину першої частини, тому шукаємо символ з номером $k - F_{n - 2}$ k - F_{n - 2}.

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

Основна частина програми. Обчислюємо перші $M A X$ числа Фібоначчі.

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

Читаємо кількість тестів $t es t s$ .

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

Обчислюємо і виводимо відповідь для кожного тесту.

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