Ввести целые положительные N⩽16, K⩽16. Написать неуместно рекурсивную функцию , которая вычисляет количество натуральных N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей. Лидирующие нули не допускаются. Вывести это количество.
- Подсказка: «длинную арифметику» делать не надо, но результат — довольно большое число
Подсказка: довольно легко вывести рекуррентное соотношение, которое в виде трёх функций, вызывающих друг друга, занимает 6 строк. Однако алгоритм из трёх функций неэффективен настолько, что не пройдёт тесты. Лучше объединить их в одну, тогда она вообще в 4 строчки будет.
- Решать задачу надо рекурсией, а не через школьные формулы комбинаторики.
6 3
328