Задание 22

Каналы авторов Физмат на сотку, Я обязательно сдам ЕГЭ по ИНФОРМАТИКЕ

Сложность: средний уровень

Время на решение одной задачи: около 5 минут

Начальные знания: основы python, генераторы массивов, системы счисления

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

Что из себя представляет эта задача?

Умение анализировать заданный алгоритм, работать с разными системами счисления (далее СС)

Данное задание делю на 2 вида:

1) алгоритмы на СС кратные 10

2) алгоритмы на СС не кратные 10.

В этой статье мы рассмотрим задачи на оба вида 22 заданий

1) Алгоритмы на СС кратные 10

Для начала решим такую задачу.

Текст задачи:

В данной статье во всех заданиях мы будем анализировать алгоритм на языке python.

Разберёмся с работой программы. Сначала, вводим значение переменной x, далее переменным a и b присваиваем значения равные 0.

x = int(input())
a, b = 0, 0

Рассмотрим конструкцию цикла while. На каждой итерации к переменной a прибавляется единица. Зная это, можно сказать точное число повторений цикла while.

while x > 0:
    a = a + 1

Переменная b считает сумму остатков x на 100. В десятичной СС это последние 2 цифры числа x.

Далее x делится нацело на 100. В десятичной СС при делении на 100 последние 2 цифры числа x отбрасываются.

В конце программа выводит сначала переменную a, затем b

print(a)
print(b)

Из данной программы можно понять, что количество итераций равно 2 (значение переменной a), а сумма остатков от деления на 100 равно 13 (значение переменной b).

Для более большего понимания, рассмотрим работу программы на примере x = 119

На первой итерации цикла программа будет работать так:

while x > 0:  #x = 119
    a = a + 1
    b = b + x%100  #b += 19
    x = x//100  #x = 1

На второй итерации так:

while x > 0:  #x = 1
    a = a + 1
    b = b + x%100  #b += 1
    x = x//100  #x = 0

Чтобы получить минимальное число нам следует учесть 2 момента:

1) Число разрядов должно быть минимально возможным

2) На первом месте в числе должна стоять наименьшая цифра из возможных

Казалось бы, наименьшая сумма, которую можно получить из числа 13 - это 13+0. И в ответ указать 13. Но наше число должно поделиться на 100 два раза, а 13 делиться лишь один. Это важная тонкость, которую надо учесть при решении этого задания. Поэтому правильно будет разложить число 13 на 12+1 и составить из этого число 112.

Ответ в этой задаче: 112

22 задания также можно решать с помощью полного программного перебора. Программой лучше решать "гробы" или на поиск минимального числа. В остальных случаях решать руками будет проще чем программой.

Давайте разберём решение этого задание программой:

Перепишем программу, данную в задании, переделав его в функцию.

1) Уберём строку x = int(input()), переменная x будет получена с помощью вызова функции:

a, b = 0, 0
while x > 0:
    a = a + 1
    b = b + x%100
    x = x//100

print(a)
print(b)

2) Добавим строку def f(x): и табуляцию:

def f(x):
    a, b = 0, 0
    while x > 0:
        a = a + 1
        b = b + x%100
        x = x//100

    print(a)
    print(b)

3)Заменим print на return. В данном случае лучше возвращать кортеж (a, b)

def f(x):
    a, b = 0, 0
    while x > 0:
        a = a + 1
        b = b + x%100
        x = x//100

    return (a, b)

Теперь можно с помощью цикла for перебрать все возможные числа x и отобрать подходящий:

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

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

def f(x):
    a, b = 0, 0
    while x > 0:
        a = a + 1
        b = b + x%100
        x = x//100

    return (a, b)

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

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

112

Рассмотрим задачу на поиск максимального числа.

Текст задачи:

Программа на python:

В этой задаче переменная b - произведение остатков от деления на 100. 5 - простое число, поэтому произведения может выглядеть только так 5*1. Чтобы наше число поделилось на 100 дважды и было максимальным, в ответ нужно записать 501.

Ответ в этом задании: 501

Рассмотрим решение этой задачи программой:

def f(x):
    a, b = 0, 1
    while x > 0:
        a = a + 1
        b = b * (x%100)
        x = x//100

    return (a, b)

m = 0

for x in range(1, 1000000):
    if f(x) == (2, 5):
        m = max(m, x)
        
print(m)

В данном случае при верном результате функции f(x), его сравнивают с максимальным значением на данный момент.

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

Рассмотрим более сложное задание.

Текст задачи:

Программа задания на python:

Первое, что может запутать, это последняя строка:

print("%d\n%d" % (a, b))

Выражение "%d\n%d" разделяет кортеж на числа и выводит каждое число на новой строке. Это выражение никак не влияет на решение этого задания.

Перейдём тонкости этого задания. В предыдущих примерах мы искали число, которое должно было поделиться на 100 ровно два раза. В этот же раз наше число должно поделиться на 100 ровно три раза. Какое максимальное произведение трёх чисел даст нам число 18? Несложно догадаться, что это 18*1*1. Самое главное правильно составить число. Возможно вы подумали, что ответом является число 18011. Если да, то вы были недостаточно внимательны.

Давайте рассмотрим первую итерацию нашей программы с входным числом 18011:

while x > 0: #18011
  a = a + 1  #a = 1
  b = b * (x % 100) #b = 11
  x = x // 100  #x = 180

Как можно заметить, значение переменной b равно 11. Это явно не то, что нам нужно. В подобных заданиях надо быть внимательнее. Правильный ответ в этом задании 180101. Так, на первых двух итерациях будут считываться единицы.

Ответ в этом задании: 180101

Рассмотрим решение этого задания программой:

def f(x):
    a = 0; b = 1
    while x > 0:
      a = a + 1
      b = b * (x % 100)
      x = x // 100
    return (a, b)

m = 0

for i in range(1, 1000000):
    if f(i) == (3, 18):
        m = max(m, i)

print(m)

В данном задании стоит возвращать кортеж (a, b) без дополнительных выражений.

Рассмотрим задачу на подсчёт подходящих чисел.

Текст задачи:

Программа задания на python:

В данном задание нам нужно найти не минимальное или максимальное число, а количество подходящих чисел.

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

Так как нам нужно, чтобы число делилось на 100 ровно два раза, то нам нужно составить трёхзначные и четырёхзначные числа.

Как можно заметить, число 606 повторяется 2 раза. Из этого можно понять, что если делится на 2, то количество чисел чётное, иначе нечётное. Этот факт может помочь вам при проверке задания.

Ответ в этом задании: 12

Решим это задание программой:

def f(x):
    a = 0; b = 0
    while x > 0:
      a = a + 1
      b = b + (x % 100)
      x = x // 100
    return (a, b)
    

k = 0

for i in range(100, 10000):
    if f(i) == (2, 12):
        print(i)
        k += 1

print(k)

Можно заметить, что нужные нам в диапазоне трёхзначных чисел, поэтому в цикле for лучше будет указать диапазон от 100 до 10000 не включительно.

2) Алгоритмы на СС некратные 10:

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

Рассмотрим 22 задание из досрочного ЕГЭ 2020 года.

Текст задачи:

Текст программы на python:

Как можно заметить, в этой задаче на вход даётся число в десятеричной СС, а берём остаток и делим мы в восьмеричной СС.

Чтобы было проще решать такие задания, давайте представим, что на вход дано число в восьмеричной СС. Это значит, что мы можем использовать цифры от 0 до 7.

Когда мы обговорили условия нашей игры, более подробно рассмотрим алгоритм.

Вводится переменная x и создаются переменные M и L:

x = int(input())
L = 0
M = 0

Теперь перейдём к циклу while. Переменная M является счётчиком итераций:

while x > 0:
  M = M + 1

Теперь самое главное условие. Если переменная x при делении на 2 не равна 0 (то есть x - нечётное число), то к переменной L прибавляется остаток от деления на 8:

while x > 0:
  M = M + 1
  if x % 2 != 0:
    L = L + x % 8

В конце итерации x делится нацело на 8:

while x > 0:
  M = M + 1
  if x % 2 != 0:
    L = L + x % 8
  x = x // 8

Важно! В программе сначала выводится переменная L (сумма нечётных остатков), а потом M (число итераций):

print(L)
print(M)

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

Надеюсь, вы помните правила игры? Сумма нечётных чисел равна 2 (переменная L), а число разрядов равно 3 (переменная M).

Из этого можно понять, что в нужном числе есть чётная цифра

Причём единственная нечётная сумма, которая даёт 2, выглядит как 1+1.

Так как нам нужно наибольшее число, то несложно заметить, что наше число выглядит так:

Максимальное чётное число в восьмеричной СС это 6. Поэтому нужное нам число 611.

Но число 611 - это восьмеричное число. А на вход подаётся число в десятеричной СС. Поэтому нам надо перевести 611 в десятеричное число, получается 393.

Ответ в этом задании: 393

Решим данную задачу с помощью программы:

def f(x):
    L = 0
    M = 0
    while x > 0:
      M = M + 1
      if x % 2 != 0:
        L = L + x % 8
      x = x // 8
    return (L, M)
m = 0
for i in range(1, 100000):
    if f(i) == (2, 3):
        m = max(m, i)
        
print(m)

Другие СС никак не влияют на решение задания программой

Закрепим материал на данной задаче.

Текст задачи:

Программа на python:

Как можно заметить, произведение остатков от деления на 6 равно 6. Число 6 в данном случае можно разложить только на 3*2.

Но почему нельзя разложить на 6*1? Дело в том, что цифры 6 нет в шестеричной СС.

Дело осталось за малым! Так как число разрядов в нашем числе равно 3 (переменная a), то число 6 надо представить в виде 3*2*1. Из этого можно составить конечное число 123. Но стоит помнить, что число 123 - нужное нам число в шестеричной СС, а алгоритм принимает на вход число в десятеричной СС. Поэтому ответ в данной задаче 51.

Ответ в данной задаче: 51

Решим данную задачу с помощью программы:

def f(x):
    a = 0; b = 1
    while x > 0:
      a = a + 1
      b = b * (x % 6)
      x = x // 6
    return (a, b)

for i in range(1, 100000000):
    if f(i) == (3, 6):
        print(i)
        break

Как можем заметить, решение 22 заданий в некратных десяти СС отличаются лишь переводом в десятеричную СС. Поэтому не стоит бояться решать подобные задания.

Рассмотрим решение задание на двоичную СС.

Текст задачи:

Программа на python:

Как мы можем заметить, переменная L считает количество нечётных цифр в двоичной СС числа, то есть количество единиц.

Так как нам нужно минимальное число и количество разрядов равно 6, нужное нам число - 100011. Осталось перевести число 100011 перевести в десятеричную СС.

Ответ в этой задаче: 35

Решим это задание с помощью программы:

def f(x):
    L = 0; M = 0
    while x > 0:
      M = M + 1
      if x % 2 != 0:
        L = L + 1
      x = x // 2
    return (L, M)

for i in range(1, 100000):
    if f(i) == (3, 6):
        print(i)
        break

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

Гуляя по просторам интернета, я нашёл вот такую задачу.

Текст задачи:

Текст программы на python:

Давайте подробно проанализируем этот алгоритм.

В начале считывается x. В переменную L присваивается значение x. В переменную M присваивается 65:

x = int(input())
L = x
M = 65

Если L делиться на 2, то в M присваивается 52:

if L % 2 == 0:
  M = 52

Теперь самое интересное!

while L != M:
  if L > M:
    L = L - M
  else:
    M = M - L

Данный цикл называется алгоритм Евклида, он находит НОД от M и L.

Чтобы решить данное задание, давайте разложим числа 52, 65, 26 на простые множители:

Как найти НОД двух чисел, если они разложены на простые множители?

В таком случае нужно нужно брать числа с наименьшей степенью. Давайте рассмотрим наглядно на примере двух чисел 52 и 65. Разложим числа на одинаковые простые множители:

После разложения выберем числа с наименьшей степенью. Если степени одинаковые, то берём число с этой степенью:

НОД этих двух чисел равен произведению 13*5⁰*2⁰, то есть 13.

Зная это, мы можем решить это задание!

Заметим, что наше число точно чётное. Чтобы получить после алгоритма 26, нам нужно, чтобы наименьшая степень двойки была равна 1, а в числе 65 два находится в нулевой степени, поэтому надо чтобы переменная M была равна 52.

Давайте рассмотрим множители 52 и 26. Все множители числа 26 имеются в числе 52, поэтому 26 вполне может быть вводимым числом, если бы не условие задания. В условии нас просят найти наименьшее большее 100 число.

Давайте подумаем, какой множитель надо добавить к произведению, чтобы итог алгоритма не поменялся, а вводимое число было больше 100. Несложно заметить, что достаточно домножить наше число на 5. Так вывод алгоритма не поменяет, потому что в числе 52 пять в нулевой степени.

Ответ в этом задании: 130

Решение программой нечем не меняется от решения предыдущих заданий:

def f(x):
    L = x
    M = 65
    if L % 2 == 0:
      M = 52
    while L != M:
      if L > M:
        L = L - M
      else:
        M = M - L
    return M

for i in range(100, 100000):
    if f(i) == 26:
        print(i)
        break

Сложные и интересные задачи:

Текст задачи:

Программа на python:

Помогли решить данную задачу эти ребята.

В данной задаче нам предстоит работать сразу в двух СС.

Давайте приступим! Начнём с анализа программы.

Сначала вводится переменная x, переменной s присваивается 0:

x = int(input()) 
s = 0 

Перейдём к циклу while. Переменная s считает сумму остатков от деления на 9. Далее x делится нацело на 3:

while x > 0: 
  s = s + x % 9 
  x = x // 3

В конце программа выводит s:

print(s)

Перейдём к решению! Интересным фактом будет то, что 81 это 100₉ и 10000₃. Из этого можно понять, что искомое число четырёхзначное в троичной СС. Давайте теперь рассмотрим первую итерацию алгоритма на примере числа 1233 в троичной СС:

while x > 0: # x = 1233
  s = s + x % 9 # s = 33
  x = x // 3 # x = 123

Можно заметить, что переменная операция x%9, берёт последние 2 цифры от троичной СС.

Давайте представим вводимое число в троичной СС как abcd. Рассмотрим результат работы алгоритма:

Давайте теперь поймём важную вещь. Результат работы алгоритма в десятеричной СС равно 17. Так давайте переведём это выражение в десятеричную СС и приравняем к 17:

Приведём подобные слагаемые:

Давайте теперь подберём число abcd, которое при постановке в наше выражение будет равно 17. И тут на помощь нам приходит факт, который мы вывели в начале. Так как 81 = 10000₃, то несложно подобрать нужное. Число 10121 отлично нам подходит. При подстановке в выражение оно даст на 17, а также это число минимально.

Осталось перевести число 10121 в десятеричную СС.

Ответ в этой задаче: 97

Решим это задание с помощь программы:

def f(x):
    s = 0 
    while x > 0: 
      s = s + x % 9 
      x = x // 3 
    return s

for i in range(80, 1000000):
    if f(i) == 17:
        print(i)
        break

Подведём итоги:

Мы научились решать все типы 22 заданий, анализировать алгоритмы, считать в разных СС.

каналы авторов Физмат на сотку, Я обязательно сдам ЕГЭ по ИНФОРМАТИКЕ

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