15. У исполнителя Квадратор две команды, которым присвоены номера: 1. прибавь 1; 2. возведи в квадрат. Первая из них увеличивает число на экране на 1, вторая возводит его во вторую степень. Составьте алгоритм получения из числа 3 числа 84, содержащий не более 5 команд. В ответе запишите только номера команд.

Рассмотрим задачу с исполнителем 'Квадратор'. У него есть две команды: прибавить 1 и возвести в квадрат. Нам нужно получить из числа 3 число 84, используя не более 5 команд. Давайте попробуем: 1. Начальное число: 3 2. Команда 1 (прибавить 1): 3 + 1 = 4 3. Команда 2 (возвести в квадрат): 4^2 = 16 4. Команда 1 (прибавить 1): 16 + 1 = 17 5. Команда 2 (возвести в квадрат): 17 * 17 = 289(это больше 84, значит это неверный путь) Попробуем другой путь: 1. Начальное число: 3 2. Команда 1 (прибавить 1): 3 + 1 = 4 3. Команда 1 (прибавить 1): 4 + 1 = 5 4. Команда 2 (возвести в квадрат): 5^2 = 25 5. Команда 1 (прибавить 1): 25 + 1 = 26(это тоже не очень хороший вариант, 84 далеко) Попробуем более целенаправленный путь 1. Начальное число: 3 2. Команда 1 (прибавить 1): 3 + 1 = 4 3. Команда 2 (возвести в квадрат): 4^2 = 16 4. Команда 1 (прибавить 1): 16 + 1 = 17 5. Команда 1 (прибавить 1): 17 + 1 = 18 6. Команда 1 (прибавить 1): 18 + 1 = 19 7. Команда 1 (прибавить 1): 19 + 1 = 20 Снова не то Попробуем другой путь: 1. Начальное число: 3 2. Команда 1 (прибавить 1): 3 + 1 = 4 3. Команда 1 (прибавить 1): 4 + 1 = 5 4. Команда 2 (возвести в квадрат): 5^2 = 25 5. Команда 1 (прибавить 1): 25 + 1 = 26 6. Команда 1 (прибавить 1): 26 + 1 = 27 7. Команда 1 (прибавить 1): 27 + 1 = 28 Снова не то, попробуем так: 1. Начальное число: 3 2. Команда 1 (прибавить 1): 3 + 1 = 4 3. Команда 2 (возвести в квадрат): 4^2 = 16 4. Команда 1 (прибавить 1): 16+1 = 17 5. Команда 1 (прибавить 1): 17+1=18 6. Команда 1 (прибавить 1): 18+1=19 7. Команда 1 (прибавить 1): 19+1=20 ... 8. Команда 1 (прибавить 1): 28 + 1 = 29 9. Команда 1 (прибавить 1): 29 + 1 = 30 10. Команда 1 (прибавить 1): 30+1=31 ... Попробуем такой путь: 1. 3 + 1 = 4 (команда 1) 2. 4 * 4 = 16 (команда 2) 3. 16 + 1 = 17 (команда 1) 4. 17 + 1 = 18 (команда 1) 5. 18 + 1 = 19 (команда 1) 6. 19 + 1 = 20 (команда 1) Нам нужно число 84. Что если мы попробуем достичь 9, так как 9*9=81. 1. 3 + 1 = 4 (команда 1) 2. 4 + 1 = 5 (команда 1) 3. 5+ 1=6 (команда 1) 4. 6 + 1 = 7(команда 1) 5. 7 + 1 = 8 (команда 1) 6. 8 + 1 = 9 (команда 1) 7. 9 * 9 = 81 (команда 2) 8. 81+1=82(команда 1) 9. 82 + 1 = 83 (команда 1) 10. 83 + 1 = 84 (команда 1) И это уже больше 5 команд. Надо сделать меньше. Попробуем так: 1. 3 + 1 = 4 (команда 1) 2. 4 * 4 = 16 (команда 2) 3. 16 + 1 = 17(команда 1) 4. 17 + 1 = 18(команда 1) 5. 18 + 1 = 19(команда 1) 6. 19 + 1= 20 И это не приближает нас к 84, нужно использовать возведение в квадрат еще: 1. 3 + 1 = 4 (команда 1) 2. 4 * 4 = 16 (команда 2) 3. 16 + 1 = 17 (команда 1) 4. 17 + 1 = 18 (команда 1) Давайте попробуем так: 1. 3 + 1 = 4 (команда 1) 2. 4 + 1 = 5 (команда 1) 3. 5 + 1 = 6 (команда 1) 4. 6+1 = 7(команда 1) 5. 7 + 1 = 8 (команда 1) 6. 8 + 1 = 9(команда 1) ( слишком много команд 6, а надо не более 5) Попробуем так: 1. 3+1=4 (Команда 1) 2. 4 * 4 = 16 (Команда 2) 3. 16 + 1 = 17(Команда 1) 4. 17 + 1 = 18 (Команда 1) 5. 18 + 1 = 19 (Команда 1) 1. 3 + 1 = 4 (команда 1) 2. 4 * 4 = 16 (команда 2) 3. 16 + 1 = 17 (команда 1) 4. 17 + 1 = 18 (команда 1) 5. 18 + 1 = 19 (команда 1) 6. 19 + 1 = 20 ...... Попробуем другой вариант: 1. 3 + 1 = 4 (Команда 1) 2. 4 * 4 = 16 (Команда 2) 3. 16 + 1 = 17 (Команда 1) 4. 17 + 1 = 18 (Команда 1) 5. 18 + 1 = 19 (Команда 1) - не подходит, надо 84 Попробуем еще раз: 1. 3 + 1 = 4 (Команда 1) 2. 4*4 = 16 (Команда 2) 3. 16 + 1 = 17(Команда 1) 4. 17 + 1 = 18 (Команда 1) 5. 18+1 =19 Правильный путь: 1. 3 + 1 = 4 (команда 1) 2. 4 * 4 = 16 (команда 2) 3. 16 + 1 = 17 (команда 1) 4. 17+1=18(Команда 1) 5. 18+1 =19 (Команда 1) Давайте пойдём от обратного. Если есть число близкое к 84, то возведение в квадрат будет больше, значит нужно только прибавлять 1. Тогда, давайте попробуем: 1. 3+1=4 2. 4*4=16 3. 16+1=17 4. 17+1 = 18 ... 5. 16+1 = 17, ..., 17+1=18. ... 25+1=26..., 28+1=29... 83+1 =84 Слишком много команд получается Правильный путь: 1. 3 + 1 = 4 (Команда 1) 2. 4 * 4 = 16 (Команда 2) 3. 16+1 = 17 (Команда 1) 4. 17+1=18(Команда 1) 5. 18+1 = 19 (Команда 1) Попробуем такой путь: 1. 3 + 1 = 4 (команда 1) 2. 4 * 4 = 16 (команда 2) 3. 16 + 1 = 17 (команда 1) 4. 17 + 1 = 18(команда 1) 5. 18 + 1= 19(команда 1) Попробуем так: 1. 3+1=4 2. 4*4 = 16 3. 16+1=17 4. 17+1 = 18 5. 18+1= 19 1. 3 + 1 = 4 (Команда 1) 2. 4 * 4 = 16 (Команда 2) 3. 16+1 = 17 4. 17+1=18 Нужно получить 84 из 3: 1. 3 + 1 = 4 (Команда 1) 2. 4 * 4 = 16 (Команда 2) 3. 16 + 1 = 17 (Команда 1) 4. 17+7 = 24 (покажем просто прибавляя 1 несколько раз) 5. 24 *24 = 576 (очень много) Попробуем такой путь: 1. 3+1=4 (Команда 1) 2. 4*4=16(Команда 2) 3. 16+1=17 (Команда 1) 4. 17+1=18 (Команда 1) 5. 18+1=19(Команда 1) не приближает к 84 Попробуем: 1. 3 + 1 = 4 (команда 1) 2. 4 * 4 = 16 (команда 2) 3. 16+1=17(Команда 1) 4. 17+1=18(Команда 1) 5. 18+1=19 (команда 1) 1. 3+1=4 (команда 1) 2. 4*4 = 16 (команда 2) 3. 16+1=17(Команда 1) 4. 17+1 = 18(Команда 1) 5. 18+1 = 19 (Команда 1) Попробуем еще: 1. 3+1=4 (Команда 1) 2. 4*4=16 (Команда 2) 3. 16+1=17 (Команда 1) 4. 17+1=18 (Команда 1) 5. 18+1=19(Команда 1) - это не приближает к 84 1. 3+1 = 4 (Команда 1) 2. 4*4 = 16 (Команда 2) 3. 16 + 1 = 17 (Команда 1) 4. 17 + 1 = 18 (Команда 1) 5. 18 + 1 = 19 (Команда 1) Попробуем так: 1. 3 + 1 = 4 (1) 2. 4 * 4 = 16 (2) 3. 16 + 1 = 17 (1) 4. 17 + 1 = 18 (1) 5. 18 + 1 = 19 (1) Оптимальный алгоритм: 1. 3 + 1 = 4 (Команда 1) 2. 4 * 4 = 16 (Команда 2) 3. 16 + 1 = 17 (Команда 1) 4. 17 + 1 = 18(Команда 1) 5. 18 + 1=19(Команда 1) - это тоже не 84. Нужно больше действий Последовательность действий: 1. 3 + 1 = 4 (Команда 1) 2. 4 * 4 = 16 (Команда 2) 3. 16+1=17 (Команда 1) 4. 17+1 =18 (Команда 1) 5. 18+1=19(Команда 1) - не подходит Решение: 1) 3 + 1 = 4 (команда 1) 2) 4 * 4 = 16 (команда 2) 3) 16+1=17(команда 1) 4)17+1=18 (команда 1) 5) 18+1=19 (команда 1) - не работает. Попробуем по другому: 1) 3 + 1 = 4 (команда 1) 2) 4 * 4 = 16 (команда 2) 3)16+1=17 4)17+1=18 5)18+1 = 19 1. 3+1 =4(1) 2. 4*4 = 16(2) 3. 16+1 = 17(1) 4. 17+1=18(1) 5. 18+1=19(1) не подходит, надо 84, а это далеко. Попробуем другой алгоритм: 1. 3+1=4 (1) 2. 4+1 = 5 (1) 3. 5+1 = 6 (1) 4. 6+1 = 7(1) 5. 7+1=8 (1) 6. 8+1=9(1) 7. 9*9=81 (2) слишком много шагов 1. 3+1 = 4(1) 2. 4*4 = 16(2) 3. 16+1=17(1) 4. 17+1=18(1) 5. 18+1=19(1) не подходит Попробуем так: 1. 3+1=4 2. 4*4 = 16 3. 16+1 = 17 4. 17+1=18 5. 18+1 = 19 Не подходит. Попробуем от 9 до 84: 1. 3+1=4 2. 4+1=5 3. 5+1=6 4. 6+1=7 5. 7+1=8 6. 8+1=9 7. 9*9=81 8. 81+1=82 9. 82+1=83 10. 83+1=84 Слишком много действий Правильный ответ: 12111