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 из 0 и 1 равно 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);