Сколько всего паролей будет?

Question

[HrustHr]

Есть сочетания букв "aa", "a", "b" и "bb".

Сколько всего вариантов паролей будет, если сгенерировать из сочетаний , пароли длинной 10 букв и длинной 72 букв ?

Большое спасибо

Comments

[Wataru]

Какая-то странная задачка. Какой ответ будет для 3 букв? "bbb" считается 1раз, или 3 (b+bb, b+b+b, bb+b)?

Answer 1

[Wataru]

Если пароли считаются уникальные, как строки, то ответ - 2^n: любую строку из "a" и "b" можно как-то составить.

Если пароли считаются уникальные, как последовательность "aa", "a", "b" и "bb" (так, для трех букв отдельно подсчитаются a+aa, aa+a и a+a+a), то ответ можно найти по рекуррентной формуле F(N) = 2(F(N-1)+F(N-2)), F(1) = 2, F(2) = 6.

Формла выводится так: В конце может быть один символ. Тут 2 варианта - это "a" или "b", тогда получается F(N-1) последовательностей длины N-1. Если же в конце идет "aa" или "bb", то таких последовательностей ровно F(N-2). Просуммировав все получится 2(F(N-1)+F(N-2))

Это что-то вроде чисел фиббоначи. Можно еще вывести формулу:

F(N) = (1+sqrt(3))^(N+1)-(1-sqrt(3))^(N+1) / (2sqrt(3))

Если пишите программу, то лучше считать F() итеративно. Только учтите, там будут очень большие числа - в 64-битный тип не поместится.

Answer 2

[mayton2019]

72 в десятой степени будет 3 743 906 242 624 487 424

Вот такое число. В физических величинах это будет ... эээ 3 квинтиллиона с хвостиком.