Как убить 5 задание ЕГЭ по информатике

Статья написана любителем, который только готовиться к ЕГЭ.

Телеграмм канал по моей подготовке к ЕГЭ

Канал автора (тык)

Сложность: базовый уровень

Необходимые начальные знания - умение переводить числа в разные системы счисления (тык)

Статьи по другим заданиям: тык

Одно из первый несложных заданий, которое можно научиться выполнять за 20 минут, а за час уничтожать 90 % подобных заданий. Перейдём к теории

Немного про строение

В 5 задании нам предлагают проанализировать программу, которая преобразует число в другое. Начнём с наиболее частых типов:

В этом примере число переводиться в двоичную запись, и по правилу видоизменяется. В нашем случае складываются все единицы числа. Исходя из остатка от деления на 2 добавляется разряд. К примеру, число 25 в двоичной записи 11001, сумма всех единиц 3, остаток от деления 2 равен 1, приписываем к числу единицу, получили 110011, проделаем это ещё раз, получим 1100110. Если перевести это в десятичную систему счисления, получится 102. Из этого можно понять, что если число единиц нечётное, то к нему приписывается 10, если чётное, то 00.

Теперь когда разобрались с алгоритмом, можно приступить к решению. Нам нужно найти минимальное число R (результат алгоритма), которое превышает 43.

Приступим! Как это делаю я:

Перевожу число 44 в двоичную СС, получил 101100, как можно заметить число 44 не может являться результатом, так как в нашем алгоритме нужно приписывать 00 только если количество единиц кратно 2.

Число 45 в двоичной СС 101101. К сожалению, это число тоже не подходит, потому что если откинуть 01, то получится 1011, сумма всех единиц равно 3, остаток от деления на 2 равен 1, значит сначала справа нужно приписать 1, а не 0.

Идём дальше

Число 46 нам подходит! Запись в двоичной СС 101110. Отбрасываем последние 2 цифры, складываем все единицы, получаем 3, остаток от деления на 2 равен 1, поэтому число 46 ответ.

46 ответ в этом задании

Давайте теперь решим это задание программой. Для этого вам лучше всего изучить основы языка python (видео по основам python).

Рассмотрим функции для перевода чисел в разные СС

bin(x) - превращает число x в двоичную запись числа в виде строки

hex(x) - превращает число x в шестнадцатеричную запись числа в виде строки

oct(x) - превращает число x в восьмеричную запись числа в виде строки

int(x, base) - превращает строку x в число с основанием 10 из основания base(по умолчанию base = 10, это позволяет конвертировать строку в число, чем, скорее всего, вы часто пользуетесь) К примеру, int('100110' 2) вернёт 38, а int('100110' 10) оставит число прежним

Теперь, мы можем перейти к решению этого задания

Давайте напишем функцию, которая считает количество единиц в числе и проверяет его чётности

def f(x):
    if x.count('1') % 2 == 0:
        return '00'
    else:
        return '10'

Функция x.count('1') возвращает число раз, сколько '1' встречалась в строке x. Если остаток от количества единиц равен 0, то возвращаем '01', иначе '10'.

Запустим цикл, который будет прибавлять к двоичной записи нашего числа результат функции от числа

for i in range(1, 100):
    a = bin(i)[2:]
    a += f(a)
    if int(a, 2) > 43:
        print(int(a, 2))
        break

Создадим переменную a - двоичную запись числа i. Стоит заметить, что первые два элемента строки bin(i) нам не нужны. Они служат для обозначения СС. Чтобы решить эту проблемы, мы воспользуемся срезами

Далее мы прибавляем к a результат работы функции

    a += f(a)

Потом проверяем если результат нашей работы в десятичной СС > 43, то печатаем результат и ломаем цикл, с помощью break, ибо нам нужно минимальное число.

    if int(a, 2) > 43:
        print(int(a, 2))
        break

Код полностью:

def f(x):
    if x.count('1') % 2 == 0:
        return '01'
    else:
        return '10'
        

for i in range(1, 100):
    a = bin(i)[2:]
    a += f(a)
    if int(a, 2) > 43:
        print(int(a, 2))
        break

Примечание:

Как можно заметить, при решении руками, мы начинали с перебора результата (R), но в случае решения прогой, мы перебираем (N). Это намного проще реализовать и проще для понимания

На Решу ЕГЭ много подобных типовых заданий. Чтобы не делать ошибок, стоит прояснить несколько тонкостей:

1) Обращайте внимание на требования

Иногда просят найти не R (результат алгоритма), а N (вводимое число). Разберём такой пример:

Возьмём первое число большее 77.

78 в двоичной СС 1001110. Отбрасываем 2 последние цифры, получили 10011. Сумма всех цифр равна 3, остаток от деления на 2 равен 1.

Значит число 78 нам подходит. Но 78 это результат алгоритма, а нам надо найти первоначальное число. Получается чтобы найти вводимое число, в нашем случае надо отбросить 2 последние цифры и перевести в десятичную СС.

Получили 10011, что в десятичной СС 19.

Ответ в этой задаче 19

Давайте рассмотрим решение прогой

def f(x):
    if x.count('1') % 2 == 0:
        return '00'
    else:
        return '10'
        

for i in range(1, 100):
    a = bin(i)[2:]
    a += f(a)
    if int(a, 2) > 77:
        print(i)
        break

Заметим, что в этом задании, нам нужно найти вводимое число (N), поэтому мы выводим число i вместо int(a, 2)

2) Внимательно читайте условие

Наверное, этот совет можно написать к каждому заданию ЕГЭ. Не стоит думать, что все 5 задания дописывают числа по одному принципу (что я покажу ниже). С таким подходом вы будете часто допускать ошибки, даже в самых лёгких заданиях. Знаю, это сложно заставить себя читать условие полностью, особенно после 20 однотипных задач, но это необходимо

Перейдём ко второму типу задач

Разберём ещё одну вариацию 5 задания:

На вид может показаться немного сложным, но стоит преодолеть страх, и всё становится понятным. Нам нужно найти минимальное число которое после обработки алгоритмом будет равно 1412.

Давайте распишем все возможные суммы, на которые можно разложить 14 и 12

Заметим, что для наименьшего числа нам лучше всего подходит разложение 14 на 9 и 5, а 12 на 9 и 3. Чтобы получить наименьшее число, следует поставить на первое место 3, на второе 9, так как, она есть в разложении и и там, и там, а на последнее 5.

Получается наименьшее число 395.

Ответ в этой задаче 395

Совет:

При решении подобных заданий стоит обращать внимание, что при разложении чисел не всегда приходит сразу верное решение. Следует перепроверить ещё раз перед записью ответа. Также лучше всегда расписывать все возможные суммы, чтобы не допустить ошибки

Интересные и сложные задачи, которые стоит решить для понимая темы

(желательно решать после освоения базовых заданий)

Несложно понять, что наибольшее число к 65536 должно образовываться по первому случаю. Значит, нам нужно найти ближайшее число к 65536 в шестнадцатеричной СС, у которого первая цифра F, а последние 2 - A0. Возьмём первое число меньшее 65536. Число 65535 в шестнадцатеричной СС - FFFF. Это число нам не подходит, но на его примере можно понять, как подобрать нужное число. Цифра F (15 в десятеричной СС), значит, чтобы получить на конце A0, нужно вычесть из разряда единиц F, а из разряда десятков 5, чтобы получить A (10 в десятеричной СС). Таким образом, получаем число FFA0. Отбрасываем F слева, и A0 справа. Получается число F (15 в десятеричной СС).

Вернёмся к первому шагу алгоритма. Он гласит, что число N делится на цело на 2, то есть при делении нечётных чисел на 2, остаток откидывается. Число 15 можно получить двумя начальными N – это 30 и 31. Так как нас просят найти наибольший, то в ответ надо записать 31

Ответ в этой задаче 31

Для решения этой задачи нам нужно знать 2 свойства двоичной СС.

1) В десятичной записи приписывание 0, значит умножение на 10, в пятеричной на 5, в троичной на 3 и так далее. Это происходит из-за перехода разряда в разряд выше

2) Из свойства выше мы можем вывести это. Давайте представим, что когда мы приписываем 1 к числу в двоичной СС, то мы приписываем не 1, а 0 и потом прибавляем 1.

С помощью этих двух свойств мы с легкостью решим это задание. Давайте возьмём число 244, у которого разряд единиц и десятков равны. Умножим его на 2 ( то есть в двоичной СС припишем 0)

Получим число 488. Как видно разряд единиц и десятков всё ещё равны.

Но давайте возьмём число 288.

Умножим его на 2, получим число 576. Заметим, что у этого числа число десятков на 1 больше чем число единиц.

Из этого получаем 4 варианта работы алгоритма

1) Число, у которого количество десятков и единиц равны и больше 4, умноженное на 2(то есть приписывание 0 в двоичной системе)

2) Число, у которого количество десятков и единиц равны и больше 4, умножаем на 2 и прибавляем 1 (то есть приписывание 1 в двоичной системе)

3) Число, у которого количество десятков и единиц равны и меньше 4, умножаем на 2 и прибавляем 1 (то есть приписывание 1 в двоичной системе)

4) Число, у которого количество десятков и единиц равны и меньше 4, умноженное на 2(то есть приписывание 0 в двоичной системе)

В первом случае мы получим число десятков на 1 большее чем число единиц.

Во втором случае мы получим число десятков равное числу единиц.

В третьем случае мы получим число единиц на 1 большее чем число десятков.

В четвёртом случае мы получим число десятков равное числу единиц.

Осталось рассмотреть числа большие 413, у которого либо число десятков равно числу единиц, либо число десятков или единиц превышает на 1 число единиц или десятков.

Получаем число 423, прогоним его через алгоритм, чтобы получить N.

Ответ в этой задаче 21

Давайте разберём задачу, которую легче будет решать прогой

Для такой задачи легче заставить компьютер за нас.

Напишем функцию, которая сравнивает количество единиц и нулей в числе

def f(x):
    if x.count('0') == x.count('1'):
        return x[-1]
    elif x.count('0') > x.count('1'):
        return '1'
    else:
        return '0'

Если количество единиц и нулей равно, но функция возвращает последнюю цифру числа, иначе возвращает ту цифру, которая реже встречалась

Теперь запустим цикл

for i in range(1, 100):
    a = bin(i)[2:]
    for _ in range(3):
        a += f(a)
    if int(a,2)%4 == 0 and int(a,2) % 8 != 0:
        print(a, i)

Создаём переменную a, которая хранит двоичную запись числа.

Далее с помощью цикла, прибавляем трижды результат работы функции

    for _ in range(3):
        a += f(a)

После этого выполняем проверку на делимость и выводим результат

    if int(a,2)%4 == 0 and int(a,2) % 8 != 0:
        print(a, i)

Важно!

Иногда ответ может быть большим числом, поэтому лучше всего проверять себя, ставя диапазон больше. В нашем случае хватит маленького диапазона в 99 чисел

Вот что выведет наша программа

В нашем случае нужно наибольшее число, поэтому в ответ стоит указать 49

Ответ в этой задаче 49

Задача из Статграда (27.10.21):

Как мы можем заметить, данная задача немного отличается от предыдущих. Здесь нам не дано начало отрезка. Сложно найти число, от которого можно начать искать N. Давайте решим это задание программированием!

Создадим функцию f(x), в которую мы поместим наш алгоритм. Также заведём переменные sum1, которая будет считать просто сумму чётных цифр в числе, и sum2, которая будет считать сумму цифр на чётных местах:

def f(x):
    sum1 = 0
    sum2 = 0

Давайте реализуем первый шаг нашего алгоритма. Чтобы было легче работать с числом, переведём его в строку, так мы сможем проходить по цифрам числа с помощью цикла for. Функция str() поможет нам это сделать. Теперь с помощью цикла for пройдём по нашем числу в виде строки и если цифра числа делится на 2, то будем прибавлять его к sum1:

x = str(x)
    for i in x:
        if int(i) % 2 == 0:
            sum1 += int(i)

Теперь реализуем второй шаг алгоритма. Тут не всё так просто. Давайте поймём, что не так на примере числа 2017.

Элементы в строках в языке python начинают счёт с нуля. Так цифра 2 становится на нулевом месте, вместо первого. Решим эту проблему!

С помощью цикла for переберём все цифры от 0 до длины числа не включительно. Будем проверять, если i+1 будет кратно 2, то будем прибавлять к sum2 цифру, которая стоит i-ом месте. Это поможет нам избежать проблемы. Также не забудем преобразовывать символ в число с помощью функции int():

for i in range(len(x)):
        if (i+1) % 2 == 0:
            sum2 += int(x[i])

Остаётся вернуть модуль разности sum1 и sum2. Функция abs() помогает взять модуль от числа:

return abs(sum1 - sum2)

Теперь переберём все числа большие 1. Если результат будет равен 13, то будем выводить число. Так как нам нужно минимальное, то остановим цикл с помощью break:

for i in range(2, 1000000):
    if f(x) == 13:
        print(x)
        break

Программа полностью:

def f(x):
    sum1 = 0
    sum2 = 0
    x = str(x)
    for i in x:
        if int(i) % 2 == 0:
            sum1 += int(i)
    for i in range(len(x)):
        if (i+1) % 2 == 0:
            sum2 += int(x[i])
    return abs(sum1 - sum2)

for i in range(2, 1000000):
    if f(i) == 13:
        print(i)
        break

Результат работы программы:

618

***возможно будут ещё***

На этом разбор 5 заданий можно завершать. Если вам понравилась статья, то прошу в мой телеграмм канал, там много интересного!

Спасибо Алексею Кабанову и Григорию за помощь при создании этой статьи!

Алексей на youtube

Алексей в вк

Группа Алексея по подготовке к ЕГЭ 2022