Анализ хода исполнения алгоритма

В задании 13 исполнитель меняет число своими командами, а спрашивают, сколько разных программ ведут от одного числа к другому. Вот задача, которую мы будем решать всю тему:

«Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1; 2. Умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 20, и при этом траектория вычислений содержит число 6 и не содержит числа 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.»

Выписывать все программы долго — их много, и они длинные. Мы научимся считать их, не выписывая. Сначала разберём, что сказано в условии:

Тема состоит из семи подтем — у каждой своя страница. Идём по ним по порядку:

1. Команды, программы и дерево — ты сейчас здесь.
2. Таблица количества программ — тот же счёт без дерева для участка из 6 в 20.
3. Обязательные и запрещённые числа — обязательное 6, запрещённое 9 и ответ задачи.
4. Новые и условные команды — другие команды вместо «+1» и «×2».
5. Убывание и деление — команды, которые уменьшают число.
6. Группы программ и обратные вопросы — дополнительный урок для редких условий.
7. Длина и память программы — ещё один дополнительный урок.

Почти везде задачу можно решить и вручную, и программой — выбирай вкладку «Вручную» или «Python». На экзамене подойдёт любой способ, а второй пригодится для проверки.

Возьмём исходное число 3 и выполним две программы: 12 и 21.

Программа — последовательность команд, записанная их номерами. Команды выполняют слева направо, по одной. Программа 12: сначала команда 1 — 3 + 1 = 4, потом команда 2 — 4 · 2 = 8. Программа 21 — те же команды в другом порядке: 3 · 2 = 6, потом 6 + 1 = 7.

Траектория — числа, которые появились на экране после каждой команды: у программы 12 это 4 и 8, у программы 21 — 6 и 7. Исходное число 3 в траекторию не входит: его не получала ни одна команда.

Обрати внимание: считают программы, а не числа. Из 1 команда 1 даёт 1 + 1 = 2 и команда 2 даёт 1 · 2 = 2. Число одно, а программы две — 1 и 2. Поэтому из 1 в 4 ведут четыре программы: 111, 12, 21 и 22.

Сколько программ переводят 2 в 6 — первый участок задачи темы?

Дерево перебирает все программы: из каждого числа выходит по ветке на каждую команду. Строим его от 2:

1. Из 2 команда 1 даёт 3, команда 2 — 4: две ветки.
2. Из каждого нового числа снова пробуем обе команды.
3. Получили 6 — ветка закончилась успехом: это одна программа.
4. Получили больше 6 — ветку обрываем: команды только увеличивают число, к 6 уже не вернуться.

def f(x, y):    if x > y:        return 0    if x == y:        return 1    return f(x + 1, y) + f(x * 2, y)  print(f(2, 6))

def f(x, y):    if x > y:        return 0    if x == y:        return 1    return f(x + 1, y) + f(x * 2, y) print(f(3, 6))

В дереве число 4 встретилось дважды: слева — после 2 → 3 → 4, справа — сразу после 2 → 4. Нужно ли продолжать его два раза?

Из одинаковых чисел дерево растёт одинаково, поэтому число достаточно записать один раз и отметить, сколькими программами в него пришли. В 4 пришли две программы (11 и 2), и каждую можно продолжить одинаково: 4 → 5 → 6. Значит, через 4 в 6 ведут две программы.

Это количество обозначают K(n): сколько программ переводят старт в число n. Запишем числа от 2 до 6 в строку, а под каждым — K:

Такая таблица заменяет дерево, когда чисел много, — ей посвящена подтема 2.

• Программапоследовательность команд
• Разные программыразный порядок команд, даже при одном результате
• Траекториячисла после команд, без старта
• Деревоветка на команду, обрыв за целью
• Повторычисло один раз, под ним K(n)
• Pythonf(x + 1, y) + f(x * 2, y)