У исполнителя Тритон две команды которым присвоены номера 1.Прибавь 1 2.Прибавь 3 Первая...

Question

У исполнителя Тритон две команды которым присвоены номера
1.Прибавь 1
2.Прибавь 3
Первая из них увеличивает на 1 число на экране , вторая увеличивает это число на 3
Программа для Тритона-это последовательность команд
Сколько существует программ,которые число 22 преобразуют в число 35

Comments

88, решается по идее динамического программирования

---

как?

Answer 1

Задача сводится к использованию n1 раз команды "Прибавь 1" и использованию n2 раз команды "Прибавь 3", где n1 и n2 целые числа 0,1,2,...
По условию задачи составляем уравнение 22+n1*1+n2*3=35
n1+3*n2=13 -> n1=13-3*n2
Поскольку n1≥0, n2≤4 и составляем список решений:
n2=4, n1=13-3*4=1
n2=3, n1=13-3*3=4
n2=2, n1=13-3*2=7
n2=1, n1=13-3*1=10
n2=0, n1=13-3*0=13
Итого возможно 5 программ.

Comments

Замечание: Внутри первых четырех программ возможны несущественные вариации, когда команды "Прибавь 1" и "Прибавь 3" переставляются местами, но я не считаю эти вариации различными. Т.е. 1+3+3+3+3, 3+1+3+3+3, 3+3+1+3+3, 3+3+3+1+3 и 3+3+3+3+1 - одна и та же программа.