Написать функцию No_2Zero(N, K), которая вычисляет количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей. Лидирующие нули не допускаются. Для EJudge N⩽33.
print(No_2Zero(6, 3))
328
Подсказка: довольно легко вывести рекуррентное соотношение, которое в виде трёх функций, вызывающих друг друга, занимает 6 строк. Однако алгоритм из трёх функций неэффективен настолько, что не пройдёт тесты. лучше объединить их в одну, тогда она вообще в 4 строчки будет. Правда, в такой форме это будет всё ещё «неправильная» рекурсия, с глубиной вложенности N/2. Ну и пускай.
Спойлёр:
После того, как задача решена, ещё один спойлер: