İkili parol#7438

İkili parol (Həll təhlili)

Şifrə (uzunluğu $n$ olan bir sətir) etibarlı sayılır, əgər orada iki ardıcıl sıfır tapılmırsa. Belə sətirlərin sayı Fibonacci ədədləri $f_{n}$ f_n ilə təyin olunur, belə ki:

$f_{1} = 2$ f_1 = 2 (sətirlər $0$ , $1$ ),

$f_{2} = 3$ f_2 = 3 (sətirlər $01$ , $10$ , $11$ ),

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

Məsələn, Fibonacci ardıcıllığının ilk ədədləri belə görünür:

Uzunluğu $n$ olan ikili sətirlərin ümumi sayı $2^{n}$ 2^n-ə bərabərdir. Beləliklə, təsadüfi yaradılan sətirlərin etibarlı sətir tapılması üçün gözlənilən sayı belədir:

2^{n} / f_{n}

2^n / f_n

Bu ifadəni təsəvvür etmək üçün payı və məxrəci onların ən böyük ortaq böləninə bölmək lazımdır.

Nümunə

$n = 1$ n = 1 üçün cavab $2^{1} / f_{1} = 2/2 = 1/1$ 2^1 / f_1 = 2 / 2 = 1 / 1 bərabərdir.

$n = 4$ n = 4 üçün cavab $2^{4} / f_{4} = 16/8 = 2/1$ 2^4 / f_4 = 16 / 8 = 2 / 1 bərabərdir.

Alqoritmin realizasiyası

Fibonacci ədədlərini saxlamaq üçün massiv elan edək.

long long f[61];

gcd funksiyası iki ədədin ən böyük ortaq bölənini hesablayır.

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

Proqramın əsas hissəsi. Giriş dəyəri $n$ -i oxuyuruq.

scanf("%d", &n);

Fibonacci ədədlərini hesablamaq.

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

Cavab olan ifadə belədir:

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

num / den = 2^n / f_n

Bu ifadəni qısaltmaq üçün payı və məxrəci onların ən böyük ortaq böləninə bölək.

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

num /= d;
den /= d;

Cavabı ekrana çıxarırıq.

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