Двійковий пароль#7438

Двійковий пароль (Розбір)

Пароль (рядок довжини $n$ ) вважається надійним, якщо в ньому не зустрічаються два послідовних нуля. Кількість таких рядків дорівнює числу Фібоначчі $f_{n}$ f_n, що визначається наступним чином:

$f_{1} = 2$ f_1 = 2 (рядки $0$ , $1$ ),

$f_{2} = 3$ f_2 = 3 (рядки $01$ , $10$ , $11$ ),

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

Наприклад, перші числа послідовності Фібоначчі мають вигляд:

Загальна кількість бінарних рядків довжини $n$ дорівнює $2^{n}$ 2^n. Таким чином, очікуване число випадково згенерованих рядків до знаходження надійного дорівнює

2^{n} / f_{n}

2^n / f_n

Зазначену дробу слід скоротити, розділивши чисельник і знаменник на їхній найбільший спільний дільник.

Приклад

Для $n = 1$ n = 1 відповідь дорівнює $2^{1} / f_{1} = 2/2 = 1/1$ 2^1 / f_1 = 2 / 2 = 1 / 1.

Для $n = 4$ n = 4 відповідь дорівнює $2^{4} / f_{4} = 16/8 = 2/1$ 2^4 / f_4 = 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];

Відповідь дорівнює дробу

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

num / den = 2^n / f_n

Скорочуємо цю дробу, розділивши чисельник і знаменник на їхній найбільший спільний дільник.

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

num /= d;
den /= d;

Виводимо відповідь.

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