Динамическое программирование. Информатика

Пусть n - количество команд в программе. Тогда мы можем составить следующую систему уравнений:

3 x 3^(n-1) = 18

n + 1 = количество комбинаций команд в программе, где одна комбинация - это либо "Прибавь 1", либо "Умножь на 3".

Первое уравнение следует из того, что первая команда программы может быть только "Умножь на 3", а каждая следующая команда может быть любой из двух возможных.

Решая систему уравнений, находим:

n = 3

Это означает, что существует только одна программа, которая начинается с "Умножь на 3", а затем два раза применяет команду "Прибавь 1", чтобы получить результат 18:

Умножь на 3 -> Прибавь 1 -> Прибавь 1 = 18

Сперва посмотрим, сколько раз мы можем умножать.

 3 ∙ 3 = 9 < 18, а 3 ∙ 3 ∙ 3 = 27 > 18 

Отсюда следует, что умножить на 3 мы можем максимум один раз.

Поэтому осталось разобраться с прибавлением единички.

Крайние варианты:

 1) 18 : 3 = 6 = 3 + 1 + 1 + 1  => 3 раза прибавить и 1 раз умножить.

   (3 + 1 + 1 + 1) ∙ 3 = 18

2) 3 ∙ 3 = 9; 9 + 1 ∙ 9 = 18 => 1 раз умножить и 9 раз прибавить.

   3 ∙ 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 18 

Промежуточных вариантов остаётся 2: прибавить единицу 1 или 2 раза, умножить на 3 и "догнаться" единичками.

 3) (3 + 1) ∙ 3 + 1 + 1 + 1 + 1 + 1 + 1 = 18

4) (3 + 1 + 1) ∙ 3 + 1 + 1 + 1 = 18 

И есть вариант не умножать на 3.

 5) 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 18 

Всё, других вариантов нет, только 5 возможных программ.