Решения заданий ФИПИ ЕГЭ по информатике: «Алгоритмы и исполнители» — с ответами

Минимальное число после алгоритма

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. 1. Строится троичная запись числа $N$. 2. Если число $N$ делится на 3, то к этой записи…

1. 1
   Проверим числа $N$, начиная с тех, которые могут дать результат, немного больший 133. Для числа, кратного 3, к троичной записи дописываются две последние цифры.
2. 2
   Для $N=15$ имеем $15_{10}=120_3$. Число $15$ делится на 3, поэтому дописываем две последние троичные цифры записи $20$ и получаем $12020_3$.

Ещё 2 шага — в полном решении

Обработка двоичной записи числа

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Строится двоичная запись числа $N$. Если сумма цифр в двоичной записи числа чётная, к…

1. 1
   Проверим наибольшие подходящие значения $N$. Для $N=12$ двоичная запись имеет вид $1100_2$. Сумма цифр равна 2, поэтому дописываем справа 0: $11000_2$, затем заменяем два левых разряда на 10 и получаем $10000_2$.$$10000_2=16_{10}\leq19$$
2. 2
   Для следующего числа $N=13$ имеем $1101_2$. Сумма цифр равна 3, поэтому дописываем справа 1: $11011_2$. Первые два разряда уже равны 11, поэтому результат не меняется.$$11011_2=27_{10}>19$$

Ещё 1 шаг — в полном решении

Максимальное число после алгоритма

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. 1. Строится двоичная запись числа $N$. 2. Далее эта запись обрабатывается по следующему…

1. 1
   Если $N$ делится на 3, к его двоичной записи дописываются три последние цифры. Поэтому $R=8N+(N\bmod 8)$. При условии $R\leq208$ максимальное подходящее $N$, кратное 3, равно 24, и тогда $R\leq192$.
2. 2
   Если $N$ даёт остаток 1, дописывается двоичная запись числа 3, то есть $11_2$. Поэтому $R=4N+3$. При $R\leq208$ имеем $N\leq51$, но наибольшее $N\leq51$ с остатком 1 при делении на 3 — это $49$.

Ещё 3 шага — в полном решении

Минимальное число по алгоритму

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Строится двоичная запись числа $N$. К этой записи справа дописываются два разряда…

1. 1
   Для всех шестизначных двоичных записей максимальным числом является $N=63$. Его двоичная запись содержит шесть единиц, поэтому первый добавленный разряд равен $0$, а второй также равен $0.$$63_{10}=111111_2\ \longrightarrow\ 11111100_2=252_{10}$$
2. 2
   Полученный результат не превосходит 253, поэтому проверяем следующее число $N=64$.$$64_{10}=1000000_2$$

Ещё 2 шага — в полном решении

Минимальное исходное число

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Сначала строится троичная запись числа $N$. Если число $N$ делится на 3, к этой записи…

1. 1
   Проверяем натуральные числа по возрастанию, преобразуя их в троичную систему и дописывая требуемую последовательность цифр.
2. 2
   Для числа $N=11$ имеем $11_{10}=102_3$. Число 11 при делении на 3 даёт остаток 2.

Ещё 4 шага — в полном решении

Минимальное число после обработки

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Сначала строится троичная запись числа $N$. Если число $N$ делится на 3, то слева к нему…

1. 1
   Проверим значения $N$ начиная с наименьших. Для $N=7$ имеем $7=21_3$. Остаток от деления на 3 равен 1, поэтому дописываем троичную запись числа $1\cdot5=5$, то есть $12_3$.$$R=2112_3=68_{10}$$
2. 2
   Для $N=8$ имеем $8=22_3$. Остаток от деления на 3 равен 2, поэтому дописываем троичную запись числа $2\cdot5=10$, то есть $101_3$.$$R=22101_3=2\cdot3^4+2\cdot3^3+1\cdot3^2+1=220_{10}$$

Ещё 1 шаг — в полном решении

Построение числа в троичной системе

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. 1. Строится троичная запись числа $N$. 2. Далее эта запись обрабатывается по следующему…

1. 1
   Проверим значения $N$, дающие результаты около границы 180. Для $N=16$ имеем $16_{10}=121_3$, остаток при делении на 3 равен 1, поэтому дописываем $5_{10}=12_3$: $R=12112_3=176_{10}$.
2. 2
   Для $N=17$ имеем $17_{10}=122_3$, остаток равен 2, поэтому дописываем $10_{10}=101_3$. Получаем $R=122101_3=514_{10}$.

Ещё 4 шага — в полном решении

Минимальное число по алгоритму

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Сначала строится двоичная запись числа $N$. Если число $N$ делится на 3, к этой записи…

1. 1
   Для чисел, делящихся на 3, к двоичной записи дописываются три последние двоичные цифры. Поэтому значение результата вычисляется как $R=8N+(N\bmod 8)$.
2. 2
   Среди чисел, меньших 26 и делящихся на 3, наибольшее число — 24. Для него $24_{10}=11000_2$, поэтому $R=11000000_2=192$, что меньше 200.

Ещё 2 шага — в полном решении

Алгоритм Евклида

Определите значение переменной $m$ после выполнения фрагмента алгоритма. В начале работы алгоритма переменным присваиваются значения $m := 81$ и $n := 48$. Если $m = n$, выполнение завершается. Если…

1. 1
   При каждом проходе из большего значения вычитается меньшее, пока значения $m$ и $n$ не станут равными.$$m,n \to \gcd(81,48)$$
2. 2
   Выполняем последовательные вычитания: $81-48=33$, затем $48-33=15$, $33-15=18$, $18-15=3$.

Ещё 1 шаг — в полном решении

Подсчёт точек в фигурах

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси…

1. 1
   По первой последовательности команд определяется прямоугольная область с целочисленными координатами: по горизонтали расположено 13 возможных координат, по вертикали — 15.$$N_1 = 13 \cdot 15 = 195$$
2. 2
   После поднятия хвоста Черепаха перемещается к началу второй фигуры. Последний цикл строит прямоугольник шириной 6 единиц и высотой 13 единиц. С учётом границ в нём 7 и 14 целочисленных координат соответственно.$$N_2 = 7 \cdot 14 = 98$$

Ещё 2 шага — в полном решении

Угол поворота Черепашки

Исполнитель Черепашка перемещается по экрану компьютера, оставляя след в виде линии. Команда «Вперёд $n$» перемещает Черепашку на $n$ шагов в направлении движения, а команда «Направо $m$» изменяет…

1. 1
   При переходе от одной стороны правильного шестиугольника к следующей Черепашка должна поворачивать на внешний угол.$$n = \dfrac{360^\circ}{6}$$
2. 2
   Вычисляем величину угла поворота.$$n = 60^\circ$$

Отбор чисел по условиям

Рассматривается множество целых чисел, принадлежащих числовому отрезку [12 014; 49 635], остаток от деления которых на 13 равен 7, и при этом они не делятся ни на 5, ни на 12. Найдите количество…

1. 1
   Числа, дающие остаток 7 при делении на 13, имеют вид $n=13k+7$. Из принадлежности отрезку получаем $924\leqslant k\leqslant3817$.$$n\in\{12019,12032,\ldots,49628\}$$
2. 2
   Количество всех таких чисел равно $3817-924+1=2894$.$$N=2894$$

Ещё 4 шага — в полном решении

Пересечение фигур Черепахи

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси…

1. 1
   Выберем начало координат, начальное направление движения примем за положительное направление оси ординат. Последовательно выполним команды и нанесём на координатную плоскость все отрезки, построенные при опущенном хвосте.
2. 2
   В первой части алгоритма команда «Повтори 2» формирует первую ломаную. После перемещения с поднятым хвостом Черепаха занимает положение, из которого строится вторая фигура.

Ещё 1 шаг — в полном решении

Периметр пересечения прямоугольников

Исполнитель Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. Черепаха выполняет команды: «Вперёд $n$», «Назад $n$», «Направо…

1. 1
   Первая последовательность команд строит прямоугольник со сторонами 19 и 22. Его границы: $0 \leq x \leq 22$, $0 \leq y \leq 19$.$$P_1 = 2(19+22)$$
2. 2
   После завершения первого прямоугольника Черепаха перемещается без рисования: сначала на 3 единицы вверх, затем на 1 единицу вправо. Начальная точка построения второго прямоугольника — $(1,3)$.

Ещё 3 шага — в полном решении

Поиск минимума функции

Напишите число, которое будет напечатано в результате выполнения алгоритма. Алгоритм перебирает целые значения $t$ от $-20$ до $20$, вычисляет значение функции $F(t)=2(t^2-49)^2+5$ и сохраняет…

1. 1
   Функция имеет вид $F(t)=2(t^2-49)^2+5$. Её минимальное значение достигается, когда квадрат $(t^2-49)^2$ равен нулю.$$t^2-49=0$$
2. 2
   Целые значения, при которых достигается минимум функции: $t=-7$ и $t=7$.

Ещё 2 шага — в полном решении

Подсчёт точек внутри области

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси…

1. 1
   После команды «Направо 315» начальное направление движения задаётся углом 135 градусов относительно положительного направления оси абсцисс. Последовательно моделируем 7 повторений команд и получаем координаты всех вершин замкнутой ломаной.
2. 2
   По координатам вершин определяем минимальные и максимальные значения абсциссы и ординаты, то есть ограничивающий прямоугольник области.

Ещё 2 шага — в полном решении

Анализ работы алгоритма

Напишите число, которое будет напечатано в результате выполнения следующего алгоритма.

1. 1
   Функция имеет вид $F(t)=2(t^2-25)^2+27$. Её минимальное значение достигается, когда $t^2=25$, то есть при $t=-5$ и $t=5$.$$F(-5)=F(5)=27$$
2. 2
   При переборе сначала встречается $t=-5$, но затем при $t=5$ выполняется условие $F(t)\leq R$, поэтому переменная $M$ заменяется на 5.

Ещё 1 шаг — в полном решении

Число итераций цикла

Определите, при каком наибольшем введённом значении переменной $s$ программа выведет число 64. Программа выполняет одну и ту же операцию на четырёх языках программирования: пока $s \geq 5$, из $s$…

1. 1
   После каждой итерации цикла значение $n$ удваивается. Чтобы получить 64, найдём число итераций:$$2^k = 64 \Rightarrow k = 6$$
2. 2
   За 6 итераций из начального значения $s$ будет вычтено $6 \cdot 5 = 30$. Чтобы шестая итерация состоялась, должно быть $s \geq 30$.

Ещё 2 шага — в полном решении

Подсчёт точек в объединении фигур

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси…

1. 1
   Первая последовательность команд рисует прямоугольник с координатами $0 \leqslant x \leqslant 18$, $0 \leqslant y \leqslant 8$. Число целочисленных точек в нём:$$(18+1)(8+1)=19\cdot9=171$$
2. 2
   После поднятия хвоста Черепаха перемещается в точку $(10,4)$ и поворачивается вверх. Вторая последовательность рисует прямоугольник с координатами $10 \leqslant x \leqslant 17$, $4 \leqslant y \leqslant 21$. Число целочисленных точек в нём:$$(17-10+1)(21-4+1)=8\cdot18=144$$

Ещё 2 шага — в полном решении

Подсчёт точек в объединении фигур

Исполнитель Черепаха начинает движение в начале координат, направив голову вдоль положительного направления оси ординат. При опущенном хвосте Черепаха оставляет след. Выполняется алгоритм: Повтори 7…

1. 1
   Первый цикл рисует прямоугольник с координатами $0\leq x\leq49$ и $0\leq y\leq83$. Повторение цикла не меняет границы фигуры.$$(49-0+1)(83-0+1)=50\cdot84=4200$$
2. 2
   После перемещения с поднятым хвостом Черепаха оказывается в точке $(-19,47)$. Второй цикл рисует прямоугольник с координатами $-19\leq x\leq16$ и $-17\leq y\leq47$.$$(16-(-19)+1)(47-(-17)+1)=36\cdot65=2340$$

Ещё 2 шага — в полном решении