Question

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

Answer 1

21

Можно написать программу, которая это посчитает, либо можно нарисовать граф от тройки, типа:

3->4->5

| \->8

v

6->7->8

| \->14

v

12

Ну, и так далее.

Если лень ручками, то вот код:

Answer 2

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

Давайте представим программы в виде последовательности символов, где "1" соответствует команде "прибавь 1", а "2" соответствует команде "умножь на 2".

Начнем с числа 3 и постепенно применяем команды из программы:

1. Начальное число: 3

Теперь представим число 16 в виде степени двойки, так как последовательность умножения на 2 будет превращать число в степени двойки:

16 = 2^4

Теперь рассмотрим все возможные комбинации команд, которые преобразуют число 3 в число 16:

a) Программа с 4 командами "умножь на 2" (2222): 3 * 2^4 = 48 (не подходит, т.к. нужно получить 16).

b) Программа с 1 командой "прибавь 1" и 3 командами "умножь на 2" (1222): (3 + 1) * 2^3 = 32 (не подходит, т.к. нужно получить 16).

c) Программа с 2 командами "прибавь 1" и 2 командами "умножь на 2" (1122): (3 + 1 + 1) * 2^2 = 16 (подходит!).

Таким образом, существует только одна программа, которая преобразует число 3 в число 16, используя только команды "прибавь 1" и "умножь на 2": 1122.