Количество программ исполнителя

Теория

У исполнителя есть конечный набор команд, каждая из которых меняет число: например «+1» прибавляет единицу, а «×2» удваивает. Программа — это последовательность команд, а вопрос задачи звучит так: сколько разных программ переводит стартовое число в заданное конечное? Порядок команд важен: программы «+1, ×2» и «×2, +1» из числа 1 дают 3 и 4 соответственно, поэтому считаются разными.

Перебирать все программы нельзя — их слишком много, поэтому задачу решают динамическим программированием по возрастающим числам. Обозначим \(W(x)\) число программ, ведущих в число \(x\). Тогда \(W(x) = W(x-1) + W(x-2) + W(x/2)\): в \(x\) можно попасть из \(x-1\) командой «+1», из \(x-2\) командой «+2» и из \(x/2\) командой «×2» (последнее слагаемое берётся только для чётного \(x\)). Начало счёта — \(W(1) = 1\): пустая программа из нуля команд уже находится в стартовом числе.

Числа больше конечного не рассматриваются вовсе: команды только увеличивают значение, вернуться назад исполнитель не может. Отдельный случай — запретные промежуточные числа: если программа попала в такое число, дальше она не продолжается, поэтому счётчик \(W(x)\) для него обнуляется. Стартовое и конечное число запрещать бессмысленно — они разрешены всегда.

Важно: \(W(start) = 1\) — пустая программа; если стартовое и конечное число совпадают, ответ равен единице, а не нулю.

Пример с решением

1. Условие. Команды «+1» и «×2», стартовое число 1, конечное 5. Сколько программ ведёт из 1 в 5?
2. Начало счёта. \(W(1) = 1\) — пустая программа.
3. Число 2. В него ведут «+1» из 1 и «×2» из 1: \(W(2) = W(1) + W(1) = 2\).
4. Число 3. Только «+1» из 2 (число нечётное, команда «×2» в него не ведёт): \(W(3) = W(2) = 2\).
5. Число 4. «+1» из 3 и «×2» из 2: \(W(4) = W(3) + W(2) = 2 + 2 = 4\).
6. Число 5. «+1» из 4: \(W(5) = W(4) = 4\).
7. Ответ. Четыре программы: +1+1+1+1, ×2+1+1+1, +1×2+1, ×2×2+1. Калькулятор в режиме «Команды +1 и ×2» покажет ту же таблицу значений \(W\).
8. Проверка запрета. Если запретить промежуточное число 3, то \(W(3) = 0\), и для чисел 1…6 останется всего две программы: они обе идут через 2 и 4.

Главное

• Программа — последовательность команд; разный порядок — разные программы.
• Динамика по возрастанию: \(W(x)\) складывается из значений \(x-1\), \(x-2\) и \(x/2\).
• Значения больше конечного не рассматриваются: команды только увеличивают число.
• Запретные промежуточные числа обнуляют счётчик, стартовое и конечное — разрешены всегда.