Задание 23

Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
B. Возвести в квадрат
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 20 и при этом траектория вычислений не содержит число 11?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория состоит из чисел 16, 32, 33.

Теория

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

Решение

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

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

Алгоритм простой. В строке 1 - числа, которые получаются при старте с 2 и выполнении команд +1, *2 и **2.  Строка 2 таблицы содержит количество способов попасть в ячейку с числом выше. Стартуем с 2 - ставим 1 способ. Далее для всех нечетных чисел просто - в них можно попасть только из предыдущего (на 1 меньше) числа, прибавив к нему 1. Исключение число 9 - в него можно попасть 8+1, а также 3**2 - суммируем способы соответственно чисел 3 и 8 (7+1) и получаем 8. В число 4 можно попасть тремя способами (3+1, 2*2, 2**2) - три раза суммируем способы числа 2. Рекомендация снизу писать все способы для каждого числа, чтобы не ошибиться. Число 11 - оранжевая ячейка - ее минуем!
Весь алгоритм заключается в суммировании количества способов тех чисел, из которых можно попасть в данное число и запись этой суммы под числом во второй строке. Например в число 6 можно с помощью наших команд попасть из 15 (15+1), 8 (8*2) и 4 (4**2). Суммируя C2+G2+N2 получаем 18. Для числа 20 результат будет 37.

Программа

1-й способ

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

n = []
for k in range (0,21):
    n.append(0)
n[2] = 1
print(n)#исходный список нулей
for k in range(3,21):
    if k%2==1:
        if k!=11:
            n[k]=n[k-1]
    else:
        n[k]=n[k-1]+n[k//2]
    if k**0.5%1 == 0:
        n[k]=n[k]+n[int(k**0.5)]
print(n)#итоговый список 
print(n[20])

2-й способ

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

def F(k):
    res = 0
    if k==2: res=1
    elif k<2 or k==11: res=0
    else:
        if k**0.5%1 != 0:
            if k%2==1:
                res=F(k-1)
            else:
                res=F(k-1)+F(k//2)
        else:
            if k%2==1:
                res=F(k-1)+F(int(k**0.5))
            else:
                res=F(k-1)+F(k//2)+F(int(k**0.5))
    return res
for k in range(2,21):
    print(k,'-',F(k))

Ответ

37 (Время не более 10 минут)