Binary password#7438

Binary password (Editorial)

A password (a string of length $n$ ) is considered secure if it does not contain two consecutive zeros. The number of such strings is equal to the Fibonacci number $f_{n}$ f_n, defined as follows:

$f_{1} = 2$ f_1 = 2 (the strings $0$ , $1$ ),

$f_{2} = 3$ f_2 = 3 (the strings $01$ , $10$ , $11$ ),

$f_{n} = f_{n - 1} + f_{n - 2}, n > 3$ f_n = f_{n-1} + f_{n-2}, n > 3

For example, the first Fibonacci numbers are:

The total number of binary strings of length $n$ is $2^{n}$ 2^n. Therefore, the expected number of randomly generated strings required to obtain a secure one is equal to

2^{n} / f_{n}

2^n / f_n

This fraction should be reduced by dividing the numerator and the denominator by their greatest common divisor.

Example

For $n = 1$ n = 1, the answer is $2^{1} / f_{1} = 2/2 = 1/1$ 2^1 / f_1 = 2 / 2 = 1 / 1.

For $n = 4$ n = 4, the answer is $2^{4} / f_{4} = 16/8 = 2/1$ 2^4 / f_4 = 16 / 8 = 2 / 1.

Algorithm implementation

Declare an array to store the Fibonacci numbers.

long long f[61];

The function gcd computes the greatest common divisor of two numbers.

long long gcd(long long a, long long b)
{
  return (!b) ? a : gcd(b, a % b);
}

The main part of the program. Read the input value $n$ .

scanf("%d", &n);

Compute the Fibonacci numbers.

f[0] = 1; f[1] = 2;
for (i = 2; i <= n; i++)
  f[i] = f[i - 1] + f[i - 2];

The answer is given as a fraction:

n u m / d e n = 2^{n} / f_{n}

num / den = 2^n / f_n

Reduce this fraction by dividing the numerator and the denominator by their greatest common divisor.

num = (1LL << n);
den = f[n];
d = gcd(num, den);

num /= d;
den /= d;

Print the answer.

printf("%lld/%lld\n", num, den);