Задание 23

Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 2
B. Найди целую часть от деления на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 38 результатом является число 2 и при этом траектория вычислений содержит число 16?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.

Теория

Задание на анализ и выполнение алгоритма. Необходимо подсчитать количество различных траекторий (путей, или программ), которые приводят из исходного числа к конечному. Возможны дополнительные условия, что траектория содержит одно или несколько чисел и не содержит другое. Решается данная задача аналитически или с помощью компьютера, например в MSExcel или программированием с использованием рекурсивного алгоритма. Решение графическим построением дерева траекторий слишком трудоемкое и долгое.

Решение

Аналитический способ

Решение с помощью Excel. Выполним анализ команд (-2 и целая часть от деления на 2, обозначим для краткости //2) и построим таблицу в Excel с помощью автозаполнения, приведенную на рисунке ниже

Алгоритм простой. В строке 1 - числа, которые получаются при старте с 38 и выполнении команд -2 и //2. Так как первое число, которое получится из 38 целочисленным делением на 2 это 19 - выполняя команду минус 2 попасть во все нечетные числа от 37 до 21 мы не можем (для быстроты выполнения между 36 и 20 стоит многоточие). Число 16 - оранжевая ячейка - далее пути только из числа 16! Во второй строке количество способов попасть в каждое из чисел выше в первой строке. Для исходного числа 38 ставим 1, в 37 попасть не можем, в 36 можно попасть из 38 - способ (способы) записан в третьей строке под числом. Весь алгоритм заключается в суммировании способов тех чисел, из которых можно попасть в данное число и запись этой суммы под числом во второй строке. Например в число 18 можно с помощью наших команд попасть из 20 (20-2), 37 (37//2) и 36 (36//2). Суммируя B2+C2+E2 получаем 2. Доходим до числа 16 и продолжаем алгоритм, учитывая, что во все меньшие числа нельзя попасть минуя 16.

ВНИМАТЕЛЬНО доходим до числа 16, а далее продолжаем траекторию, учитывая числа не более 16. В 15, 13, 11, 9 попасть из 16 не можем и ставим там 0.  В 7 можно попасть из 15 (15//2) и из 9 (9-2), но там 0 и эти команды можно не учитывать. Результат 36.

Программа

1-й способ

Без рекурсии со списком - эмуляция алгоритма изложенного выше в Excel.

2-й способ

Использован рекурсивный алгоритм, который требует тестирования на основе аналитического способа!

Ответ

36 (Время не более 15 минут)