Question

У исполнителя вычислить две команды, которым присвоены номера: 1. прибавь 1, 2. прибавь 4, 3. умножить на 3. Первая из них увеличивает число на экрана на 1, вторая – на 4, третья – увеличивает его в 3 раза. Программа для Вычислителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 16?

Answer 1

Есть несколько алгоритмов решения такой задачи.

Прямой перебор - попытка перебрать всевозможные последовательности этих команд и посмотреть, какие из них, примененные к 1 сделают из нее 16 - но это долгий способ, оценка сложности сверху без короткой схемы - это 3^15 таких последовательностей (сколько всего команд) ^ (максимально возможное число команд в подходящей программе, это 15 прибавлений по единичке).

Можно развить подход "от противного", который лежит в основе идей динаимического программирования: обозначив n(x) - какое количество различных программ преобразую число 1 в x, получаем формулу для исходного n(16) = n(15) + n(12) = (n(14) + n(11) + n(5)) + (n(11) + n(8) + n(4)) = ...

Будем считать, что n(1) = 1

Тогда вот функция на питоне для подсчёта искомого числа. Вызов n(16) вернёт результат 136

def n(x):

   if x < 1: return 0

   elif x == 1: return 1

   else: return n(x - 1) + n(x - 4) + (0 if x % 3 != 0 else n(x // 3))

У такого подхода есть несомненное преимущество: его не только проще написать, но и сложность его O(n)

Answer 2

Для того чтобы число 1 преобразовать в число 16 с использованием этих трех команд, можно перебрать все возможные последовательности команд и определить, сколько программ приведут к желаемому результату.

Давайте рассмотрим все возможные комбинации команд:

1. Первая команда: прибавить 1

   • Число станет равным 2
   • Для достижения числа 16, оставшимися операциями мы должны умножить число на 8 (16 / 2).

2. Первая команда: прибавить 4

   • Число станет равным 5
   • Для достижения числа 16, оставшимися операциями мы должны умножить число на 3.2 (16 / 5).

3. Первая команда: умножить на 3

   • Число станет равным 3
   • Для достижения числа 16, оставшимися операциями мы должны умножить число на 5.33 (16 / 3).

Таким образом, нет способа получить точно 16, начиная с числа 1 и используя только эти три команды.