Задача 98718

Тема:    [ Динамическое программирование: классические задачи ]

Сложность: 2+ Классы: Название задачи: K-ичные числа.

Условие

Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей.
Ограничения: 2 <= K <= 10, N + K <= 18.
Формат входных данных
Числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Формат выходных данных
Искомое число в десятичной записи.

Решение

Эта задача почти не отличается от задачи "Взрывоопасность", если число представить как стопку, а нули - как контейнеры типа A. Очевидно, что все числа разбиваются на три класса. Остается только прописать переходы при добавлении одной цифры. Лучше (привычнее) сделать это в десятичной системе счисления, а затем заменить девятки (количество ненулевых цифр) на K - 1, а десятки - на K. В результате основной цикл будет выглядеть так:

for i := 2 to N do
  begin
   OTZ := TZ; OZ := Z; ONZ := NZ;
   TZ := OTZ * K + Z; {TZ - два нуля}
   Z := ONZ; {Z - один ноль}
   NZ := OZ * (K - 1) + ONZ * (K - 1) {NZ - в конце не ноль}
  end;

Источники и прецеденты использования

веб-сайт
предмет	информатика
Название	Дидактические материалы по математике и информатике
URL	http://comp-science.narod.ru
занятие
Номер	2
Название	Динамическое программирование
Автор	Е.В.Брызгалов
задача
Номер	5