У исполнителя Вычислитель две команды... Составьте алгоритм получения из числа 4 числа 63, содержащий не более 5 команд.

8. (Верхнее задание) **Ответ: 22111** Решение: Нам нужно из числа 4 получить 63, используя не более 5 команд. Будем идти от обратного (от 63 к 4): 1. Число 63 не является квадратом натурального числа, поэтому последней командой было «вычти 1». $63 + 1 = 64$. 2. Число 64 является квадратом 8. Значит, могла быть команда «возведи в квадрат». Проверим: $8$ — тоже квадрат? Нет, но $8 + 1 = 9$ (квадрат). Попробуем другой путь. 3. Если мы получили 64, прибавим еще 1? $64 + 1 = 65$ (не квадрат). 4. Вернемся к 64. Оно равно $8^2$. Чтобы получить 8 из 4, нужно: $4^2 = 16$ (много), или $4+1+1+1+1=8$. Но у нас ограничение в 5 команд. 5. Попробуем прямой ход: - Команда 2: $4^2 = 16$ - Команда 2: $16^2 = 256$ (слишком много) - Команда 1: $16 - 1 = 15$ - Попробуем так: $4 \xrightarrow{2} 16 \xrightarrow{2} 256$ — не подходит. - Попробуем: $4 \xrightarrow{2} 16 \xrightarrow{1} 15 \xrightarrow{1} 14...$ — не подходит. - Попробуем: $4 \xrightarrow{1} 3 \xrightarrow{2} 9 \xrightarrow{1} 8 \xrightarrow{2} 64 \xrightarrow{1} 63$. Проверим номера команд: 1 (вычти 1), 2 (возведи в квадрат), 1 (вычти 1), 2 (возведи в квадрат), 1 (вычти 1). Итого 5 команд: **12121**. - Проверим еще вариант: $4 \xrightarrow{2} 16 \xrightarrow{1} 15 \xrightarrow{1} 14 \xrightarrow{1} 13 \xrightarrow{1} 12$ — мало. - Попробуем: $4 \xrightarrow{1} 3 \xrightarrow{1} 2 \xrightarrow{2} 4...$ — не подходит. - Попробуем: $4 \xrightarrow{2} 16 \xrightarrow{2} ...$ — много. - Самый эффективный путь к 63: это $64 - 1$. А 64 это $8^2$. А 8 это $3^2 - 1$ или $2 \cdot 4$. Путь: $4 \xrightarrow{1} 3 \xrightarrow{2} 9 \xrightarrow{1} 8 \xrightarrow{2} 64 \xrightarrow{1} 63$. Команды: **12121**. 8. (Нижнее задание) **Ответ: 11122** Решение: Нужно из 36 получить 6 за 5 команд. Идем прямым ходом: 1. $36 \xrightarrow{1} 18$ (раздели на 2) 2. $18 \xrightarrow{1} 9$ (раздели на 2) 3. $9 \xrightarrow{1} 4.5$ (не подходит, работаем с натуральными числами) Попробуем иначе: 1. $36 \xrightarrow{1} 18$ 2. $18 \xrightarrow{1} 9$ 3. $9 \xrightarrow{2} 10$ 4. $10 \xrightarrow{2} 11...$ — не подходит. Попробуем: 1. $36 \xrightarrow{1} 18$ 2. $18 \xrightarrow{1} 9$ 3. $9 \xrightarrow{1} 4.5$ — нет. Попробуем от конца (от 6 к 36): 1. $6 - 1 = 5$ 2. $5 - 1 = 4$ 3. $4 \cdot 2 = 8$ 4. $8 \cdot 2 = 16$ 5. $16 \cdot 2 = 32$ (близко, но не 36) Другой путь от 36: 1. $36 \xrightarrow{1} 18$ 2. $18 \xrightarrow{1} 9$ 3. $9 \xrightarrow{1} 4.5$ — нет. Попробуем сначала прибавлять: 1. $36 \xrightarrow{1} 18$ 2. $18 \xrightarrow{2} 19 \xrightarrow{2} 20 \xrightarrow{1} 10 \xrightarrow{1} 5$ — нет. Верный путь: 1. $36 \xrightarrow{1} 18$ 2. $18 \xrightarrow{1} 9$ 3. $9 \xrightarrow{1} 4.5$ — нет. Стоп, в условии «раздели на 2» и «прибавь 1». 1. $36 \xrightarrow{1} 18$ 2. $18 \xrightarrow{1} 9$ 3. $9 \xrightarrow{1} 4.5$ — не натуральное. Значит, на 3-м шаге была команда 2. 3. $9 \xrightarrow{2} 10$ 4. $10 \xrightarrow{2} 11$ 5. $11 \xrightarrow{2} 12$ — нет. Попробуем: 1. $36 \xrightarrow{2} 37$ 2. $37 \xrightarrow{2} 38$ 3. $38 \xrightarrow{1} 19$ 4. $19 \xrightarrow{2} 20$ 5. $20 \xrightarrow{1} 10$ — нет. Попробуем еще: 1. $36 \xrightarrow{1} 18$ 2. $18 \xrightarrow{2} 19$ 3. $19 \xrightarrow{2} 20$ 4. $20 \xrightarrow{1} 10$ 5. $10 \xrightarrow{1} 5$ — нет. Пробуем так: 1. $36 + 1 + 1 + 1 + 1 = 40 \xrightarrow{1} 20$ 2. $36 \xrightarrow{1} 18 \xrightarrow{2} 19 \xrightarrow{2} 20 \xrightarrow{2} 21 \xrightarrow{2} 22$ 3. $36 + 1 + 1 = 38 \xrightarrow{1} 19 + 1 = 20 \xrightarrow{1} 10$ Ищем 6: $36 \xrightarrow{1} 18 \xrightarrow{1} 9 \xrightarrow{2} 10 \xrightarrow{2} 11 \xrightarrow{1} 5.5$ — нет. $36 \xrightarrow{1} 18 \xrightarrow{2} 19 \xrightarrow{2} 20 \xrightarrow{1} 10 \xrightarrow{2} 11$ $36 \xrightarrow{1} 18 \xrightarrow{1} 9 \xrightarrow{1} ...$ (нельзя) $36 \xrightarrow{2} 37 \xrightarrow{2} 38 \xrightarrow{2} 39 \xrightarrow{2} 40 \xrightarrow{1} 20$ — нет. $36 \xrightarrow{1} 18 \xrightarrow{1} 9 \xrightarrow{2} 10 \xrightarrow{2} 11$ — нет. Попробуем получить 12, чтобы потом разделить: $36 \xrightarrow{1} 18 \xrightarrow{1} 9 \xrightarrow{2} 10 \xrightarrow{2} 11 \xrightarrow{2} 12 \xrightarrow{1} 6$ — это 6 команд. А если $36 \xrightarrow{1} 18 \xrightarrow{1} 9 \xrightarrow{2} 10 \xrightarrow{2} 11$ — 5 команд. Попробуем: $36 \xrightarrow{1} 18 \xrightarrow{2} 19 \xrightarrow{2} 20 \xrightarrow{1} 10$ Если $36 \xrightarrow{1} 18 \xrightarrow{1} 9 \xrightarrow{1} 4.5$ — нельзя. Значит $36 \to 18 \to 9$ — уже 2 команды. Если $9 \to 10 \to 11 \to 12 \to 6$ — это 6 команд. Попробуем так: $36 + 1 + 1 + 1 + 1 = 40 \to 20$ (не то) $36 \to 18 \to 9 + 1 + 1 + 1 = 12 \to 6$ Команды: 1 (раздели), 1 (раздели), 2 (прибавь), 2 (прибавь), 2 (прибавь), 1 (раздели) — 6 команд. Нужно 5 команд: 1. $36 \xrightarrow{1} 18$ 2. $18 \xrightarrow{2} 19$ 3. $19 \xrightarrow{2} 21$ — нет. 4. $36 \xrightarrow{2} 37 \xrightarrow{2} 38 \xrightarrow{2} 39 \xrightarrow{2} 40 \xrightarrow{1} 20$ О! $36 \xrightarrow{1} 18 \xrightarrow{1} 9 \xrightarrow{2} 10 \xrightarrow{2} 11 \xrightarrow{2} 12$ — это 11122. А 6? $36 \xrightarrow{1} 18 \xrightarrow{1} 9 \xrightarrow{2} 10 \xrightarrow{2} 11 \xrightarrow{2} 12$. Ой, 12. Проверим: $36 \xrightarrow{1} 18 \xrightarrow{1} 9 \xrightarrow{2} 10 \xrightarrow{1} 5 \xrightarrow{2} 6$. Команды: **11212**. Проверка: $36 : 2 = 18$; $18 : 2 = 9$; $9 + 1 = 10$; $10 : 2 = 5$; $5 + 1 = 6$. Ровно 5 команд!