ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Составление команд исполнителя.
| КЭС: | 3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность 3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат 3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена» 3.5 Многоразрядные целые числа, задачи длинной арифметики |
| Тип ответа: | Краткий ответ |
Ответ: 121211
Команда 1 прибавляет 2, а команда 2 умножает текущее число на 3. Требуется преобразовать 0 в 28 и уложиться в 6 команд. В ответе нужны номера команд, записанные в порядке выполнения, а не промежуточные значения.
Удобно искать подходящий путь от результата к началу: обратное действие для прибавления — вычитание 2, а для умножения — деление на 3, когда оно даёт целое число. Выберем обратную цепочку:
28 → 26 → 24 → 8 → 6 → 2 → 0.
Проверим каждый переход, выполнив разрешённые команды в прямом порядке. Такой способ не требует предполагать, что любой выбор обратной операции обязательно приводит к короткой программе.
1) команда 1: 0 + 2 = 2;
2) команда 2: 2 · 3 = 6;
3) команда 1: 6 + 2 = 8;
4) команда 2: 8 · 3 = 24;
5) команда 1: 24 + 2 = 26;
6) команда 1: 26 + 2 = 28;
Проверка. Получилась цепочка 0 → 2 → 6 → 8 → 24 → 26 → 28. Она начинается с 0 и заканчивается числом 28. Каждая соседняя пара связана именно той командой, которая указана в строке вычислений. Выполнено 6 команд, что не превышает разрешённые 6. Читая их номера сверху вниз, получаем 121211. Все операции допустимы, поэтому эта программа удовлетворяет условию.
Ответ: 121211.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFF68808.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.