LecturesCMC/PythonIntro2020/Homework_Without2Zeros

Написать функцию No_2Zero(N, K), которая вычисляет количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей. Лидирующие нули не допускаются. Для EJudge N⩽33.

print(No_2Zero(6, 3))

328

• Подсказка: довольно легко вывести рекуррентное соотношение, которое в виде трёх функций, вызывающих друг друга, занимает 6 строк. Однако алгоритм из трёх функций неэффективен настолько, что не пройдёт тесты. лучше объединить их в одну, тогда она вообще в 4 строчки будет. Правда, в такой форме это будет всё ещё «неправильная» рекурсия, с глубиной вложенности N/2. Ну и пускай.

• Спойлёр: Количество искомых N-значных последовательностей — это сумма из количества N-значных последовательностей с 0 в конце и количества N-значных последовательностей без 0 в конце. Количество N-значных последовательностей с 0 в конце совпадает с количеством N-1-значных последовательностей без 0 в конце (чтобы не получилось два), а количество N-значных последовательностей без 0 в конце — с количеством любых N-1-значных последовательностей для каждой цифры, кроме 0, т. е. умноженным на K-1.

• После того, как задача решена, ещё один спойлер: Есть мнение, что на самом деле это вообще комбинаторная задача с полиномиальной сложностью, не?

CategoryHomework