Fibonacci strings#2524

Fibonacci strings (Editorial)

Fibonacci strings are defined recursively:

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

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

This means that the string $F_{n}$ F_n consists of two consecutive parts:

the first $F_{n - 2}$ F_{n-2} characters form the string $F_{n - 2}$ F_{n-2},
the next $F_{n - 1}$ F_{n-1} characters form the string $F_{n - 1}$ F_{n-1}.

Therefore, to find the $k$ -th character of the string $F_{n}$ F_n, it is not necessary to construct the entire string. It is enough to determine in which of the two parts it lies.

Let $F_{n} (k)$ F_n(k) denote the $k$ -th character of the string $F_{n}$ F_n.

Then:

if $k \leq ∣ F_{n - 2} ∣$ k ≤ |F_{n-2}|, the required character lies in the first part:

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

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

otherwise (if $k > ∣ F_{n - 2} ∣)$ k > |F_{n-2}|), the character lies in the second part:

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

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

Thus, the problem reduces to finding a character in strings with smaller indices.

Example

Consider the string $F_{6}$ F_6, for which the following relations hold:

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

Let us compute $F_{6} (4)$ F_6(4). Since $k = 4 \leq ∣ F_{4} ∣ = 5$ k = 4 \le |F_4| = 5, we have $F_{6} (4) = F_{4} (4)$ F_6(4) = F_4(4).

Let us compute $F_{6} (7)$ F_6(7). Since $k = 7 > ∣ F_{4} ∣ = 5$ k = 7 > |F_4| = 5, we have $F_{6} (7) = F_{5} (7 - 5) = F_{5} (2)$ F_6(7) = F_5(7 - 5) = F_5(2).

Algorithm implementation

The array $f ib$ stores the lengths of the Fibonacci strings:

$f ib [i]$ contains the length of the string $F_{i}$ F_i.

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

The function solve returns the $k$ -th character of the string $F_{n}$ F_n without constructing the string itself in full.

char solve(int n, int k)
{

The base cases $n = 0$ n = 0 and $n = 1$ n = 1 are handled separately.

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

It is known that $F_{n} = F_{n - 2} + F_{n - 1}$ F_n = F_{n - 2} + F_{n - 1}.

If $k \leq F_{n - 2}$ k \le F_{n - 2}, then the $k$ -th character lies in the string $F_{n - 2}$ F_{n - 2}.
If $k > F_{n - 2}$ k > F_{n - 2}, then the $k$ -th character lies in the string $F_{n - 1}$ F_{n - 1}. However, its position is shifted by the length of the first part, so we look for the character with index $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]);
}

The main part of the program. Compute the first $M A X$ Fibonacci numbers.

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

Read the number of test cases $t es t s$ .

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

Compute and print the answer for each test case.

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