У исполнителя Квадратор две команды: прибавь 3 и возведи в квадрат
Формулировка задания: У исполнителя Квадратор две команды, которым присвоены номера: 1 - прибавь 3; 2 - возведи в квадрат. Первая из них увеличивает число на экране на 3, вторая возводит его во вторую степень. Исполнитель работает только с натуральными числами. Составьте алгоритм получения из числа A числа B, содержащий не более K команд. В ответе запишите только номера команд. Если таких алгоритмов более одного, то запишите любой из них.
Задание входит в ЕГЭ по информатике для 11 класса под номером 6 (Анализ и построение алгоритмов для исполнителей).
Рассмотрим, как решаются подобные задания на примере.
У исполнителя Квадратор две команды, которым присвоены номера:
1 - прибавь 3;
2 - возведи в квадрат.
Первая из них увеличивает число на экране на 3, вторая возводит его во вторую степень. Исполнитель работает только с натуральными числами. Составьте алгоритм получения из числа 4 числа 58, содержащий не более 5 команд. В ответе запишите только номера команд. (Например, 22111 — это алгоритм: возведи в квадрат, возведи в квадрат, прибавь 3, прибавь 3, прибавь 3, который преобразует число 3 в 90.) Если таких алгоритмов более одного, то запишите любой из них.
Нужно получить число 58 из 4, используя не более 5 команд. Лучше всего решать эту задачу обратным путем – получить из числа 58 число 4. Так как возвести в квадрат можно любое число, а извлечь квадратный корень возможно не из любого числа.
Заменим команды на обратные: «прибавь 3» на «вычти 3», а «возведи в квадрат» на «извлеки квадратный корень». И решим задачу обратным путем.
Так как корень из 58 извлечь нельзя, первой командой будет «вычти 3»:
58 – 3 = 55
Так как корень из 55 извлечь нельзя, следующей командой будет «вычти 3»:
55 – 3 = 52
Так как корень из 52 извлечь нельзя, следующей командой будет «вычти 3»:
52 – 3 = 49
Из 49 можно извлечь корень. Если сейчас выполнить «вычти 3», то следующее число, из которого извлекается корень, равно 36. Чтобы достичь этого числа, потребуется более 5 шагов. Поэтому выполняем команду «извлеки квадратный корень»:
√49 = 7
Так как корень из 7 извлечь нельзя, следующей командой будет «вычти 3»:
7 – 3 = 4
Ровно за 5 команд мы получили из числа 58 число 4. Осталось изменить порядок команд на обратный и заменить названия команд на номера исходных. Таким образом, число 58 из 4 мы можем получить выполнением команд: «прибавь 3», «возведи в квадрат», «прибавь 3», «прибавь 3», «прибавь 3» или 12111.
Проверим, что все сделано верно:
(4 + 3)2 + 3 + 3 + 3 = 58
12111
Нашли ошибку? Выделите текст и нажмите Ctrl + Enter.
Есть другой способ решения?