7438. Бинарный пароль

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

Чтобы получить новый пароль, Жомарт генерирует случайную двоичную строку длины n. Если строка не является надёжной, он генерирует новую строку и повторяет процесс до тех пор, пока не получит надёжный пароль.

Найдите ожидаемое количество случайно сгенерированных паролей, которое потребуется Жомарту, прежде чем он найдёт надёжный.

Вход. Одно целое число n (1 ≤ n ≤ 60).

Выход. Выведите ожидаемое значение в виде дроби p / q, где p и q – взаимно простые натуральные числа.

Пример входа 1	Пример выхода 1
1	1/1
Пример входа 2	Пример выхода 2
4	2/1

РЕШЕНИЕ

математика

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

Пароль (строка длины n) считается надёжным, если в нём не встречаются два последовательных нуля. Количество таких строк равно числу Фибоначчи f_n, определяемому следующим образом:

f₁ = 2 (строки 0, 1),

f₂ = 3 (строки 01, 10, 11),

f_n = f_n-1 + f_n-2, n > 3

Например, первые числа последовательности Фибоначчи имеют вид:

Общее количество бинарных строк длины n равно 2ⁿ. Таким образом, ожидаемое число случайно сгенерированных строк до нахождения надёжной равно

2ⁿ / f_n

Указанную дробь следует сократить, разделив числитель и знаменатель на их наибольший общий делитель.

Пример

Для n = 1 ответ равен 2¹ / f₁ = 2 / 2 = 1 / 1.

Для n = 4 ответ равен 2⁴ / f₄ = 16 / 8 = 2 / 1.

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

Объявим массив для хранения чисел Фибоначчи.

long long f[61];

Функция gcd вычисляет наибольший общий делитель двух чисел.

long long gcd(long long a, long long b)

{

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

}

Основная часть программы. Читаем входное значение n.

scanf("%d", &n);

Вычисляем числа Фибоначчи.

f[0] = 1; f[1] = 2;

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

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

Ответ равен дроби

num / den = 2ⁿ / f_n

Сокращаем эту дробь, разделив числитель и знаменатель на их наибольший общий делитель.

num = (1LL << n);

den = f[n];

d = gcd(num, den);

num /= d;

den /= d;

Выводим ответ.

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