Задача:
У исполнителя имеются три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 2
C. Найти целую часть от деления на 3
Первая команда уменьшает число на 1, вторая – уменьшает его на 2, третья – находит целую часть от деления числа на 3. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 16 результатом является число 6, при этом траектория вычислений содержит число 11?
Решение:
Построим дерево вариантов выполнения алгоритма (начинаем с ветки «-1», раскрывать остальные ветки нет необходимости):
Веточка «//3» обрывается, т.к. получается число меньше 5 («проскочили» число 6) и траектория вычисления не прошла число 11.
Развиваем ветку «-1». Ветки не проходящие через число 11 или проскакивающие число 6 обрываем (на рисунке крестик)
Проходим до конца ветку «-1», замечаем, что число «7» даёт одну «6». Ветки «-1» и «-2» из числа «8» дают две «6». Ветки из числа «9» дают – три «6», ветки «-1» и «-2» из числа «10» пять «6».
Используем найденные значения вариантов для соответствующих чисел, двигаясь вверх по дереву.
Подсчитываем общее число «шестёрок» - 64
Ответ: 64
Вариант решения задачи на Python:
Описываем функцию: def f(x,y):
x - исходное число, y - конечное число, если исходное число меньше конечного, функция возвращает 0:
if x<y:
return 0
Если исходное число и конечное число одинаковы, существует одна программа
if x==y:
return 1
Иначе (исходное число больше конечного)
else:
return f(x-1,y)+f(x-2,y)+f(x//3,y), функция возвращает число значений функции для шагов х-1, х-2, целочисленное деление х на 3
Сама программа:
print(f(16,11)*f(11,6))
выводит на экран произведение числа шагов от 16 до 11
и числа шагов от 11 до 6