2524. Строки Фибоначчи

В математике часто используются так называемые рекуррентные соотношения. Обычно с их помощью задают числовые последовательности, однако они также могут применяться для определения последовательностей строк.

Одним из примеров строк, определяемых рекуррентными соотношениями, являются фибоначчиевы строки. Они задаются следующим образом:

F₀ = a,

F₁ = b,

F_i = F_{i - 2} + F_{i - 1}, i > 1

Первые семь фибоначчиевых строк имеют следующий вид:

a,

b,

ab,

bab,

abbab,

bababbab,

abbabbababbab

Дима посещает кружок олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о фибоначчиевых строках и быстро заметил, что при увеличении индекса i длина строки F_i растёт очень быстро. Поэтому хранение всей строки целиком требует слишком много памяти. В связи с этим Дима решил ограничиться задачей поиска отдельных символов.

Напишите программу, которая определяет k-й символ строки F_n.

Вход. В первой строке задано число тестов t (1 ≤ t ≤ 100). В каждой из следующих t строк  заданы два целых числа n и k (0 ≤ n ≤ 45, 1 ≤ k ≤ |F_n|), где |F_n| – длина строки F_n. Позиции символов в строке нумеруются с единицы.

Выход. Выведите t строк. В каждой строке должен быть выведен ровно один символ – ответ на соответствующий тест.

Пример входа	Пример выхода
4 0 1 1 1 3 2 7 7	a b a a

РЕШЕНИЕ

рекурсия, строки

Анализ алгоритма

Фибоначчиевы строки определяются рекуррентно:

F_n = F_n–2 + F_n–1

Это означает, что строка F_n состоит из двух подряд идущих частей:

· первых F_n–2 символов – это строка F_n–2,

· следующих F_n–1 символов – это строка F_n–1.

Следовательно, чтобы найти k-й символ строки F_n, не нужно строить всю строку. Достаточно определить, в какой из двух частей он находится.

Обозначим через F_n(k) k-ый символ строки F_n.

Тогда:

· если k ≤ |F_n–2|, то искомый символ находится в первой части:

F_n(k) = F_n-2(k)

· иначе (если k > |F_n–2|), символ лежит во второй части:

F_n(k) = F_n-1(k – |F_n–2|)

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

Пример

Рассмотрим строку F₆, для которой имеют место соотношения:

· F₆ = F₄ + F₅,

· |F₄| = 5, |F₅| = 8

Вычислим F₆(4). Поскольку k = 4 ≤ |F₄| = 5, то F₆(4) = F₄(4).

Вычислим F₆(7). Поскольку k = 7 > |F₄| = 5, то F₆(7) = F₅(7 – 5) = F₅(2).

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

В массиве fib хранятся длины фибоначчиевых строк:

· fib[i] содержит длину строки F_i.

#define MAX 44

int fib[MAX] = {1, 1};

Функция solve возвращает k-й символ строки F_n, не строя саму строку целиком.

char solve(int n, int k)

{

Отдельно обрабатываем базовые случаи n = 0 и n = 1.

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

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

Известно, что F_n = F_{n - 2} + F_{n - 1}.

· Если k ≤ F_{n - 2}, то k-ый символ лежит в строке F_{n - 2}.

· Если k > F_{n - 2}, то k-ый символ лежит в строке F_{n - 1}. Однако его позиция смещается на длину первой части, поэтому ищем символ с номером k – F_{n - 2}.

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

return solve(n - 1, k - fib[n-2]);

}

Основная часть программы. Вычисляем первые MAX чисел Фибоначчи.

for (i = 2; i < MAX; i++)

fib[i] = fib[i-1] + fib[i-2];

Читаем количество тестов tests.

scanf("%d",&tests);

while (tests--)

{

Вычисляем и выводим ответ для каждого теста.

scanf("%d %d",&n,&k);

printf("%c\n",solve(n,k));

}