Прочие прототипы —Каталог задач по ЕГЭ - Информатика БУ

Тема 5. Алгоритмы – анализ простейших алгоритмов

5.04 Прочие прототипы

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела алгоритмы – анализ простейших алгоритмов

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#60717

Некий исполнитель умеет делать всего две команды, которым присвоены номера:

1. прибавь 1

2. умножь на пять

Первая из них увеличивает число на экране на 1, вторая умножает число на 5. Запишите порядок команд в программе получения из 3 числа 425, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.

Например, 21211 — это программа, которая преобразует число 2 в 57.

Показать ответ и решение

Пойдём от числа 425 к числу 3 с помощью противоположных команд, то есть используя команды:

1. "вычти 1"

2. "раздели на 5"

Получаем последвательность команд:

2. $425∕5 = 85$

2. $85∕5 = 17$

1. $17 − 1 = 16$

1. $16 − 1 = 15$

2. $15∕5 = 3$

Так как команды мы считали в обратном порядке, то в ответ записываем команды снизу вверх, то есть 21122.

Ответ: 21122

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#60024

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

Из числа N вычитается остаток от деления N на 7, после чего прибавляется остаток от деления N на 5.
Строится двоичная запись полученного результата.
К этой записи дописываются справа ещё два разряда по следующему правилу:
складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа).
над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись является двоичной записью искомого числа R. Укажите минимальное число R, большее 46, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе.

Показать ответ и решение

mn = 10**10
for n in range(1, 500):
    n = n - n % 7 + n % 5
    b = bin(n)[2:]
    b += str(b.count(’1’) % 2)
    b += str(b.count(’1’) % 2)
    if int(b, 2) > 46:
        mn = min(mn, int(b, 2))
print(mn)

Ответ: 58

Ошибка.
Попробуйте повторить позже

Задача 3#60020

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

Строится семиричная запись числа N
В начало записи (слева) дописывается остаток от деления числа N на 5, а в конец записи (справа) остаток от деления N на 3.
Результат переводится из семиричной системы в десятичную и выводится на экран.

Какое наибольшее трехзначное число может появиться на экране в результате работы этого алгоритма?

Показать ответ и решение

for n in range(1, 1000):
    s = ’’
    x = n
    while x > 0:
        s = str(x % 7) + s
        x = x // 7
    s = str(n % 5) + s + str(n % 3)
    r = int(s, 7)
    if len(str(r)) == 3:
        print(r)

Ответ: 982

Ошибка.
Попробуйте повторить позже

Задача 4#57743

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. В четверичной записи числа N дублируется последняя цифра.
2. Получившееся число переводится в двоичное представление.
3. В получившейся записи дублируется последняя цифра.
4. Полученное в результате этих операций число переводится в десятичную систему счисления.

Укажите максимальное число, которое может являться результатом выполнения алгоритма, меньшее 280.

Показать ответ и решение

mx = 0
for n in range(1, 300):
    f = ’’
    while n > 0:
        f = str(n % 4) + f
        n = n // 4
    f += f[-1]
    b = bin(int(f, 4))[2:]
    b += b[-1]
    r = int(b, 2)
    if r < 280:
        mx = max(r, mx)
print(mx)

Ответ: 276

Ошибка.
Попробуйте повторить позже

Задача 5#57742

Автомат получает на вход трехзначное число. По этому числу строится новое число по следующим правилам.
1. Из цифр, образующих десятичную запись N, строится наибольшее и наименьшее возможные двузначные числа (числа не могут начинаться с нуля)
2. На экран выводится разность полученных двузначных чисел.

Чему равно количество чисел N в отрезке [300,700], в результате обработки которых на экране появится число 10?

Показать ответ и решение

c = 0
for n in range(300, 701):
    s = str(n)
    mn = 10**10
    mx = -10**9
    for i in range(len(s)):
        for j in range(i+1, len(s)):
            if s[i] != ’0’:
                mx = max(int(s[i]+s[j]), mx)
                mn = min(int(s[i]+s[j]), mn)
            if s[j] != ’0’:
                mx = max(int(s[j]+s[i]), mx)
                mn = min(int(s[j]+s[i]), mn)
    if mx-mn == 10:
        c += 1
print(c)

Ответ: 24

Ошибка.
Попробуйте повторить позже

Задача 6#54389

Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу

1334134241

Какую последовательность из шести команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?

Показать ответ и решение

Нарисуем схему передвижения робота по заданной программе. Мы видим, что для возвращения на исходную точку нам нужно сделать два шага вниз, но так как необходимо сделать шесть шагов, то между двумя командами вниз нужно вставить по два повторяющихся шага влево/вправо. Исходя из схемы, нам нужно сначала сдвинуться на две позиции вправо, а затем на две позиции влево. $PIC$

Ответ: 233442

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#54388

Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

влево

вправо

вверх

вправо

вверх

вправо

вниз

вверх

вправо

влево

вниз

вверх

Укажите наименьшее возможное число команд, которое необходимо для того, чтобы Робот вернулся в ту же клетку, из которой начал движение.

Показать ответ и решение

# Вычисляем,
# на сколько единиц мы продвинулись по осям X(влево-вправо) и Y(вверх-вниз) от начала координат
x = -1-1+1+1+1+1+1-1
y = +1+1+1-1+1-1+1

# Получаем x = 2 и y = 3, берём модули от чисел и складываем их,
# именно столько ходов нам потребуется сделать
# (x = 2, значит, нужно сделать два хода влево,
# y = 3, значит, нужно сделать три хода вниз,
# итого, ответ — 5)
print(x, y)

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 8#54387

Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды:

Сместиться на вектор (а, b) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали.

Запись: Повторить 5[Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз.

Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм:

Сместиться на вектор (251,39)

Сместиться на вектор (-246, 8)

Повторить 9[Сместиться на вектор (0,-1)]

Сместиться на вектор (4, 2)

На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма?

Показать ответ и решение

# Сначала вычисляем итоговую координату по осям X и Y
x = 251 - 246 + 9*0 + 4
y = 39 + 8 + 9*(-1) + 2
# Чтобы найти расстояние от нулевой координаты до итоговой,
# нужно воспользоваться теоремой Пифагора и вычислить гипотенузу предполагаемого треугольника,
# который получается, если провести стороны из итоговой координаты до осей X и Y
c = (x**2 + y**2)**0.5
print(c)

Ответ: 41

Ошибка.
Попробуйте повторить позже

Задача 9#5962

У исполнителя Шаг- $2$ есть $2$ команды:

1. Прибавить к числу $5$ ;

2. Прибавить к числу $2$ ;

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

Показать ответ и решение

Программой

for q in [1, 2]:
    for w in [1, 2]:
        for e in [1, 2]:
            for r in [1, 2]:
                for t in [1, 2]:
                    for y in [1, 2]:
                        prog = str(q) + str(w) + str(e) + str(r) + str(t) + str(y)
                        start = 3
                        for x in prog:
                            if x == ’1’:
                                start += 5
                            if x == ’2’:
                                start += 2
                        if start == 21:
                            print(prog)

Руками

Одним из оптимальных методов решения является написание программы шаг за шагом приближающей число к ответу. По началу выполняем команды увеличивающие число на наибольшую возможную величину, в данном случае при помощи первой команды. Так доходим до $13$ т. к. $13$ последнее нечетное число меньшее $21$ при прибавлении $5$ каждым шагом. Далее добавляем недостающие $4$ двойки до $21$ . В данном задании несколько вариантов правильных комбинаций команд т. к. их последовательность не имеет значения.

Варианты правильных ответов:

112222
121222
122122
122212
122221
211222
212122
212212
212221
221122
221212
221221
222112
222121
222211

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел