7. У исполнителя Удвоитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 2. Первая из них увеличивает число на экране на 1, вторая удваивает его. Например, 2122 – это программа, которая преобразует число 1 в число 12. Запишите порядок команд в программе преобразования числа 8 в число 83, содержащей не более 7 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.

Дано:

• Начальное число: 8
• Конечное число: 83
• Команды: 1 (прибавить 1), 2 (умножить на 2)
• Максимальное количество команд: 7

Решение:

Чтобы получить число 83 из числа 8, будем двигаться от конца к началу, используя обратные команды (вычитание 1 и деление на 2). Если число нечетное, мы можем только вычесть 1. Если число четное, мы можем либо вычесть 1, либо разделить на 2. Мы стремимся к меньшему количеству команд, поэтому будем выбирать деление на 2, когда это возможно.

1. Начинаем с 83. Число нечетное, значит, последняя команда была 1 (прибавить 1). Обратная команда: вычесть 1.
2. 83 - 1 = 82. Число четное. Попробуем применить обратную команду к умножению на 2 (то есть разделить на 2).
3. 82 / 2 = 41. Число нечетное. Значит, предпоследняя команда была 1.
4. 41 - 1 = 40. Число четное. Применим обратную команду деления на 2.
5. 40 / 2 = 20. Число четное. Применим обратную команду деления на 2.
6. 20 / 2 = 10. Число четное. Применим обратную команду деления на 2.
7. 10 / 2 = 5. Число нечетное. Значит, перед этим была команда 1.
8. 5 - 1 = 4. Число четное. Применим обратную команду деления на 2.
9. 4 / 2 = 2. Число четное. Применим обратную команду деления на 2.
10. 2 / 2 = 1.

Полученная последовательность обратных команд: 1, 2, 2, 2, 1, 2, 2, 2, 2. Это 9 команд, что больше 7. Попробуем другой путь, когда число четное.

Снова начнем с 83.

1. 83 - 1 = 82 (команда 1)
2. 82 / 2 = 41 (команда 2)
3. 41 - 1 = 40 (команда 1)
4. 40 / 2 = 20 (команда 2)
5. 20 - 1 = 19 (команда 1)
6. 19 - 1 = 18 (команда 1)
7. 18 / 2 = 9 (команда 2)
8. 9 - 1 = 8 (команда 1)

Эта последовательность тоже длиннее 7 команд. Давайте попробуем другой подход: работать с прямыми командами и стремиться к 83, не превышая 7 команд.

Начинаем с 8. Нам нужно увеличить число. Удвоение дает больший прирост.

1. 8 * 2 = 16 (команда 2)
2. 16 * 2 = 32 (команда 2)
3. 32 * 2 = 64 (команда 2)
4. 64 + 1 = 65 (команда 1)
5. 65 + 1 = 66 (команда 1)
6. 66 + 1 = 67 (команда 1)
7. 67 + 1 = 68 (команда 1)

Эта последовательность также не ведет к 83 и превышает 7 команд. Попробуем другой путь.

Идем от 8 к 83. Цель - получить число, близкое к 83, которое можно получить умножением на 2. Ближайшее к 83, которое делится на 2, это 82.

Чтобы получить 82, нужно было иметь 41 (82 / 2). Чтобы получить 41, нужно было иметь 40 (41 - 1). Чтобы получить 40, нужно было иметь 20 (40 / 2). Чтобы получить 20, нужно было иметь 10 (20 / 2). Чтобы получить 10, нужно было иметь 5 (10 / 2). Но 5 из 8 не получается за малое число команд.

Попробуем другой вариант:

1. 8 * 2 = 16 (2)
2. 16 + 1 = 17 (1)
3. 17 * 2 = 34 (2)
4. 34 * 2 = 68 (2)
5. 68 + 1 = 69 (1)
6. 69 + 1 = 70 (1)
7. 70 + 1 = 71 (1)

Это 7 команд, но результат 71, а не 83.

Попробуем такой путь:

1. 8 + 1 = 9 (1)
2. 9 * 2 = 18 (2)
3. 18 * 2 = 36 (2)
4. 36 + 1 = 37 (1)
5. 37 * 2 = 74 (2)
6. 74 + 1 = 75 (1)
7. 75 + 1 = 76 (1)

Снова 7 команд, но результат 76.

Рассмотрим путь, где мы приближаемся к 83.

8 -> (x2) 16 -> (x2) 32 -> (x2) 64. Теперь нам нужно получить 83 из 64. Разница 83 - 64 = 19. Чтобы получить 19, нам нужно 7 раз прибавить 1. Это уже 3 + 7 = 10 команд.

Попробуем такой путь:

1. 8 * 2 = 16 (2)
2. 16 * 2 = 32 (2)
3. 32 * 2 = 64 (2)
4. 64 + 1 = 65 (1)
5. 65 + 1 = 66 (1)
6. 66 + 1 = 67 (1)
7. 67 + 1 = 68 (1)

Семь команд, результат 68.

Попробуем другой путь:

1. 8 * 2 = 16 (2)
2. 16 + 1 = 17 (1)
3. 17 * 2 = 34 (2)
4. 34 + 1 = 35 (1)
5. 35 * 2 = 70 (2)
6. 70 + 1 = 71 (1)
7. 71 + 1 = 72 (1)

Снова 7 команд, результат 72.

Давайте попробуем такой вариант, работая в обратную сторону и ища самый короткий путь:

1. 83. Нечетное, значит, последняя команда была +1. Обратная: 83 - 1 = 82 (команда 1).
2. 82. Четное. Можно разделить на 2. Обратная: 82 / 2 = 41 (команда 2).
3. 41. Нечетное. Обратная: 41 - 1 = 40 (команда 1).
4. 40. Четное. Обратная: 40 / 2 = 20 (команда 2).
5. 20. Четное. Обратная: 20 / 2 = 10 (команда 2).
6. 10. Четное. Обратная: 10 / 2 = 5 (команда 2).
7. 5. Нечетное. Обратная: 5 - 1 = 4 (команда 1).

Получилось 7 команд: 1, 2, 1, 2, 2, 2, 1. Проверим:

8 + 1 = 9 (1)

9 * 2 = 18 (2)

18 + 1 = 19 (1)

19 * 2 = 38 (2)

38 * 2 = 76 (2)

76 * 2 = 152 (2)

152 + 1 = 153 (1) - неверно.

Еще раз попробуем обратный ход:

1. 83. Нечетное. Обратная команда: -1. Получаем 82. Команда: 1.
2. 82. Четное. Можно: -1 (81) или /2 (41). Выбираем /2. Обратная команда: /2. Получаем 41. Команда: 2.
3. 41. Нечетное. Обратная команда: -1. Получаем 40. Команда: 1.
4. 40. Четное. Можно: -1 (39) или /2 (20). Выбираем /2. Обратная команда: /2. Получаем 20. Команда: 2.
5. 20. Четное. Можно: -1 (19) или /2 (10). Выбираем /2. Обратная команда: /2. Получаем 10. Команда: 2.
6. 10. Четное. Можно: -1 (9) или /2 (5). Выбираем /2. Обратная команда: /2. Получаем 5. Команда: 2.
7. 5. Нечетное. Обратная команда: -1. Получаем 4. Команда: 1.
8. 4. Четное. Можно: -1 (3) или /2 (2). Нам нужно получить 8. Если мы получим 2, то потом надо будет 2*2*2 = 8 (3 команды). Если мы получим 3, то надо будет 3+1+1+1+1+1 = 8 (5 команд). Выбираем /2. Обратная команда: /2. Получаем 2. Команда: 2.
9. 2. Четное. Можно: -1 (1) или /2 (1). Если мы получим 1, то чтобы получить 8, нам нужно 1*2*2*2 = 8 (3 команды). Если мы получим 1, то надо будет 1+1+1+1+1+1+1 = 8 (7 команд). Выбираем /2. Обратная команда: /2. Получаем 1. Команда: 2.
10. 1. Четное. Нет, 1 нечетное. Обратная команда: -1. Получаем 0. Команда: 1.

Эта последовательность очень длинная.

Попробуем идти от 8 к 83, оптимизируя:

8 -> 16 (2) -> 32 (2) -> 64 (2). Теперь нам нужно получить 83. У нас 3 команды, осталось 4.

Из 64 нужно получить 83. Разница 19. 19 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 (19 раз +1). Не подходит.

Попробуем так:

1. 8 + 1 = 9 (1)
2. 9 * 2 = 18 (2)
3. 18 + 1 = 19 (1)
4. 19 * 2 = 38 (2)
5. 38 + 1 = 39 (1)
6. 39 * 2 = 78 (2)
7. 78 + 1 = 79 (1)

7 команд, результат 79.

Попробуем такой вариант:

1. 8 + 1 = 9 (1)
2. 9 + 1 = 10 (1)
3. 10 * 2 = 20 (2)
4. 20 * 2 = 40 (2)
5. 40 + 1 = 41 (1)
6. 41 * 2 = 82 (2)
7. 82 + 1 = 83 (1)

Количество команд: 1, 1, 2, 2, 1, 2, 1. Это 7 команд.

Проверим:

8 + 1 = 9 (1)

9 + 1 = 10 (1)

10 * 2 = 20 (2)

20 * 2 = 40 (2)

40 + 1 = 41 (1)

41 * 2 = 82 (2)

82 + 1 = 83 (1)

Это 7 команд, и результат 83.

Ответ: 1122121