Курс№5. Алгоритм над числами0%
Теория · номер 5 из 27

Алгоритм над числами

Алгоритм по числу N строит новое число R. Пишем функцию точно по условию, перебираем N одной строкой, и остаётся не ошибиться в том, что именно спрашивают.

8 разделов~40 минут1 первичный балл
  1. 1Что проверяет номер
  2. 2Инструменты
  3. 3Приписываем цифры
  4. 4Другая система счисления
  5. 5Первая цифра, замена, копирование
  6. 6Что ищем: N или R, два шага
  7. 7Ловушки перед экзаменом
  8. 8Домашка
Раздел 1 из 8

Что проверяет номер

Дан алгоритм, который по натуральному числу N строит новое число R. Обычно так: число переводят в двоичную или другую запись, что-то делают со строкой, например дописывают цифры, и переводят обратно. Спрашивают, при каком N результат подходит под условие или какое R получится.

Этот номер решаем только на Python, и решение всегда одно и то же:

  1. Пишем функцию f(n) ровно по условию.
  2. Сверяем её с примером из условия, скажем, «для N = 13 получается R = 116». Если не сошлось, ошибка в функции, и искать ответ рано.
  3. Перебираем N одной строкой: print(min(n for n in range(1, 10000) if f(n) > 250)).
Раздел 2 из 8

Инструменты

Всё, что нужно для работы с записью числа:

Что делаемНа Python
В двоичную записьbin(n)[2:], срез убирает приставку 0b
Из двоичной обратноint(s, 2), второй аргумент обязателен
Из другой системыint(s, 3), int(s, 8)
Количество единицs.count('1')
Остаток от деленияn % 2
Приписать справа и слеваs + '01', '1' + s
Последние три цифрыs[-3:]
Первая цифраs[0]
Заменить цифрыs = s.replace('3', '6')
python
n = 13
s = bin(n)[2:]
print(s)              # двоичная запись строкой
print(s + '01')       # приписали справа
print(s.count('1'))   # сколько единиц
print(int(s, 2))      # обратно в десятичную

Перевод в другую систему

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

python
def to_base(x, c):
    s = ''
    while x != 0:
        s = str(x % c) + s    # остаток дописываем слева
        x = x // c
    return s

print(to_base(11, 3))         # 102
print(to_base(64, 8))         # 100

Функция работает для систем с основанием до 10.

Раздел 3 из 8

Приписываем цифры

Признак: «в конец дописывается…», «в начало добавляется…», разные правила для чётных и нечётных.

Пример. Если N нечётное, справа дописывается 01. Если чётное, слева 1, справа 0. R это число из получившейся записи. Найдём наименьшее N, при котором R > 250.

python
def f(n):
    b = bin(n)[2:]
    if n % 2 == 1:
        b = b + '01'          # нечётное: приписали справа
    else:
        b = '1' + b + '0'     # чётное: слева 1, справа 0
    return int(b, 2)

print(f(5), f(4))             # сверка: 5=101 -> 10101=21, 4=100 -> 11000=24

print(min(n for n in range(1, 10000) if f(n) > 250))

Ответ 62. Первая строка вывода это сверка функции: так делаем всегда, если в условии есть пример.

Считаем единицы и повторяем

Признак: «если единиц чётное число, дописывается 0, иначе 1», «действие повторяется ещё раз». Просто пишем одно и то же действие два раза. Второй раз единицы считаются уже в новой строке:

python
def f(n):
    b = bin(n)[2:]

    if b.count('1') % 2 == 0:   # первый раз
        b = b + '0'
    else:
        b = b + '1'

    if b.count('1') % 2 == 0:   # второй раз, уже по новой строке
        b = b + '0'
    else:
        b = b + '1'

    return int(b, 2)

print(f(5))                     # 20: 101 -> 1010 -> 10100

print(min(n for n in range(1, 10000) if f(n) > 100))      # наименьшее N, при котором R > 100
print(min(f(n) for n in range(1, 10000) if f(n) > 100))   # наименьшее R, большее 100

Заметь разницу между двумя последними строками: 25 это N, а 102 это R. Перебор один и тот же, отличается только то, что стоит в начале скобок: n или f(n).

Попробуй самучебная задача

Строится двоичная запись N. Если N чётное, справа дописывается 11. Если нечётное, справа дописывается 00. Найди наименьшее N, при котором R больше 100.

Раздел 4 из 8

Другая система счисления

Признак: в условии «в троичной», «в восьмеричной», «в пятеричной записи». Вместо bin берём to_base, а при переводе обратно указываем то же основание.

Пример. N записываем в троичной системе. Справа дописываем остаток от деления суммы цифр на 3, и так два раза. Сумму цифр удобно считать отдельной маленькой функцией.

python
def to_base(x, c):
    s = ''
    while x != 0:
        s = str(x % c) + s
        x = x // c
    return s

def sum_digits(t):
    s = 0
    for c in t:
        s = s + int(c)
    return s

def f(n):
    t = to_base(n, 3)                   # троичная запись строкой
    t = t + str(sum_digits(t) % 3)      # сумма цифр % 3 в конец
    t = t + str(sum_digits(t) % 3)      # повторили
    return int(t, 3)                    # обратно из троичной!

print(f(11))                            # 99: 102 -> 1020 -> 10200

print(min(n for n in range(1, 10000) if f(n) > 150))      # наименьшее N
print(min(f(n) for n in range(1, 10000) if f(n) > 150))   # наименьшее R

Ответы: N = 17, R = 160. Сумма цифр считается заново по уже изменённой строке, поэтому строка повторяется.

Ловушка: основание при переводе обратно

Если запись троичная, то и int(t, 3). Написать по привычке int(t, 2) здесь значит получить ошибку или неверный ответ.

Раздел 5 из 8

Первая цифра, замена, копирование

Остальные правила это те же операции со строкой. Если понял срезы и replace, новых идей здесь нет.

Условие по первой цифре и замена

Признак: «если первая цифра…», «все цифры 3 заменяются на 6».

python
def to_base(x, c):
    s = ''
    while x != 0:
        s = str(x % c) + s
        x = x // c
    return s

def f(n):
    s = to_base(n, 8)
    if s[0] == '7':                 # смотрим первую цифру
        s = s + '0'
    else:
        s = s.replace('3', '6')     # результат replace нужно присвоить
    return int(s, 8)

print(f(7), f(3), f(27))            # 56, 6, 54

print(min(n for n in range(1, 10000) if f(n) > 500))

Последнюю цифру переносим вперёд

python
def f(n):
    b = bin(n)[2:]
    if n % 4 == 0:
        b = b + '11'            # кратно 4: приписать 11
    else:
        b = b[-1] + b           # иначе последнюю цифру поставить слева
    return int(b, 2)

print(f(8), f(5), f(6))         # 35, 13, 6

Копирование части записи

Если N делится на 3, справа дописываются три последние цифры записи. Иначе справа дописывается двоичная запись числа «остаток, умноженный на 3».

python
def f(n):
    b = bin(n)[2:]
    if n % 3 == 0:
        b = b + b[-3:]              # три последние цифры
    else:
        b = b + bin(n % 3 * 3)[2:]
    return int(b, 2)

print(f(6), f(4), f(1))             # 54, 19, 7

print(min(f(n) for n in range(1, 10000) if f(n) >= 200))
Попробуй самучебная задача

Строится восьмеричная запись N. Все цифры 1 заменяются на 5, а затем справа дописывается цифра 0. Результат переводится обратно. Найди наименьшее N, при котором R больше 1000.

Раздел 6 из 8

Что ищем: N или R, два шага

Перед тем как писать последнюю строку, проговори: что ищем, N или R, и какое, наименьшее или наибольшее. Строка всегда одна, меняются только min или max, n или f(n) и условие в if.

Что просятКод
Наименьшее N, при котором R > Xprint(min(n for n in range(1, 10000) if f(n) > X))
Наименьшее R, большее Xprint(min(f(n) for n in range(1, 10000) if f(n) > X))
Наибольшее N, при котором R < Xprint(max(n for n in range(1, 10000) if f(n) < X))
Наибольшее R, меньшее Xprint(max(f(n) for n in range(1, 10000) if f(n) < X))

Два шага: N при наибольшем R

Самая коварная формулировка: «укажите N, при котором получается наибольшее R, меньшее 200». В ней просят N, но условие задано через R. Поэтому строк две: первая находит R, вторая ищет N, при котором оно получается.

python
def f(n):
    b = bin(n)[2:]
    if n % 4 == 0:
        b = b + '11'
    else:
        b = b[-1] + b
    return int(b, 2)

max_r = max(f(n) for n in range(1, 10000) if f(n) < 200)    # шаг 1: какое R подходит
print(max_r)
print(max(n for n in range(1, 10000) if f(n) == max_r))     # шаг 2: при каком N оно получается

Первый шаг даёт R = 199, второй N = 71. Если сразу написать max(n for n in range(1, 10000) if f(n) < 200), получится 198: это совсем не то N, при котором R максимальное.

Как понять, что range мал

Верхнюю границу ставим с запасом, обычно хватает 10000. Если min упал с ошибкой про пустую последовательность или ответ получился равен верхней границе, значит, границу надо увеличить.

Попробуй самучебная задача

Функция та же, что в примере выше. Найди N, при котором получается наибольшее R, меньшее 100. Если таких N несколько, укажи наибольшее.

Раздел 7 из 8

Ловушки перед экзаменом

ЛовушкаЧто будетКак не попасться
range(1, 50)ValueError: min нечего выбиратьДиапазон с запасом
int('101')101 вместо 5Всегда int(s, 2)
b + 1TypeErrorb + '1' или str(...)
s.replace('3', '6')Строка не измениласьs = s.replace(...)
Нет [2:] у binb[0] это '0', длина на 2 больше, при дописывании слева ValueErrorВсегда bin(n)[2:]
to_base(0, c)Пустая строкаЕсли возможен N = 0, обработай отдельно
Нашли max N вместо N для max RНеверный ответ без ошибокДва шага
Забыли второй проход «повторить»Неверное RНапиши действие второй раз отдельно
Раздел 8 из 8

Домашка

Шесть задач с настоящих экзаменов и из банка ФИПИ. Решай прямо здесь: кнопка «Решать здесь» открывает редактор, а код каждой задачи сохраняется.

Перед тем как писать код, сделай три вещи:

Где теряют балл в этих задачах

Во всех задачах, кроме второй и шестой, спрашивают R, а не N: в начале скобок стоит f(n). В третьей условие задано на N, поэтому range начинается с 17. В пятой запись троичная, и обратно тоже переводим из троичной, а нечётность проверяем у самого R. «Не меньше» это >=, «превышает» это >.

Ещё задачи этого вида лежат в разделе «Задания», №5.

Задачи «Попробуй сам» учебные, в домашке задачи с настоящих экзаменов и из банка ФИПИ. Код в блоках можно менять и запускать, он выполняется прямо в браузере.