Леонид: Спасибо
20-09-2023
Читать статью
Калужский Александр: Леонид, цикл x повториться 300 раз, цикл..
Леонид: Почему k == 90000 в примере (x > A) ∨ (y..
Всем привет! Добрались мы до 25 задания из ЕГЭ по информатике 2023.
Рассмотрим типовые задачи, а так же новые формулировки 25 задания из ЕГЭ по информатике 2023.
Приступаем к первой классической задаче.
Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 700 000, в порядке возрастания и ищет среди них такие, для которых значение M оканчивается на 8. Выведите первые пять найденных чисел и соответствующие им значения M.
Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем – значение М. Строки выводятся в порядке возрастания найденных чисел.
Количество строк в таблице для ответа избыточно.
На ЕГЭ по информатике 2023 удобно писать программы на языке Python.
count=0 for i in range(700001, 800000): m=0 a=[] for j in range(2, int(i**0.5)+1): if i%j==0: a.append(j) b=i//j if j!=b: a.append(b) if len(a)>=1: a.sort() m=a[0]+a[-1] if m%10==8: print(i, m) count = count + 1 if count == 5: break
В данной программе перебираются числа в цикле for, начиная с 700001.
Для каждого числа i заводим искомую переменную m и список a, где будем хранить все делители этого числа, не считая 1 и самого числа. Затем, с помощью ещё одного цикла for перебираются числа с 2 до корня числа i (включительно).
Если до корня числа включительно не встретился ни один делитель, значит, у числа нет делителей, кроме 1 и самого числа.
Пусть у нас есть число A. Если у этого числа есть делитель d1, то он находится до корня этого числа (или равен корню числа). А вот то число (так же делитель d4), на которое умножается d1, чтобы получить A, будет находиться после корня A (или равен корню).
Получается, что у каждого делителя есть своя пара. У единицы - это само число. Причём, один делитель из пары находится до корня, другой после корня. Исключением будет тот случай, когда из числа А извлекается целый корень. Тогда для этого корня не будет пары (парой и будет само это число √A * √A = A).
Таким образом, нам достаточно пройтись до корня числа включительно, чтобы найти все делители числа i. Мы идём от 2, значит, единица и само число не рассматривается.
Если переменная j является делителем, то мы её заносим в список a. Сразу ищем "брата" b делителя j. Если "брат" b и переменная j не равны друг другу (равны они могут быть, если из числа i извлекается корень, например 16 = 4*4), то заносим переменную b так же в список a. Нет смысла заносить в список a одинаковые делители.
После того, как закончился цикл j, в списке a будут все делители числа i, кроме единицы и самого числа.
Если там есть хотя бы один делитель, то, значит, имеется максимальный и минимальный делитель. Мы сортируем список a, чтобы все делители были в порядке возрастания, т.к. изначально они не были упорядочены.
Находим число m. Это сумма максимального и минимального делителя. Первый элемент a[0] - это минимальный делитель. Последний элемент a[-1] - это максимальный делитель.
Если число, m подходит по условию, то мы печатаем число i и m.
Счётчик count нужен, чтобы распечатать первые пять чисел.
Напишите программу, которая перебирает целые числа, большие 550 000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель, не равный самому числу, не является простым числом.
Программа должна найти и вывести первые 6 таких чисел и соответствующие им значения упомянутых делителей.
Формат вывода: для каждого из 6 таких найденных чисел в отдельной строке сначала выводится само число, затем упомянутый делитель. Строки выводятся в порядке возрастания найденных чисел.
Например, для числа 105 наибольший натуральный делитель 35 не является простым, для числа 15 наибольший натуральный делитель 5 — простое число, а для числа 13 такого делителя не существует.
Здесь мы ищем наибольший делитель числа, как и в прошлом решении.
def Pr(x): for i in range(2, int(x**0.5)+1): if x%i==0: return False return True count=0 for i in range(550001, 1000000): a=[] for j in range(2, int(i**0.5) + 1): if i%j==0: a.append(j) b=i//j if j!=b: a.append(b) if len(a)>=1: a.sort() if not(Pr(a[-1])): count=count+1 print(i, a[-1]) if count==6: break
Чтобы проверить число, является ли оно простым, напишем функцию Pr(). Там мы проходим до корня числа. Если не встретился не один делитель, значит, число простое — возвращаем True. Если до корня хотя бы один делитель встретили — возвращаем False.
Остальное похоже на предыдущую задачу.
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [258274; 258297], числа, имеющие ровно 4 различных делителя. Выведите для каждого найденного числа два наибольших делителя в порядке возрастания.
import math for i in range(258274, 258298): a=[] for j in range(1, int(math.sqrt(i))+1): if i%j==0: a.append(j) b=i//j if j!=b: a.append(b) if len(a)==4: a.sort() print(a[2], a[3])
Здесь для каждого числа i заводим массив a, где будем сохранять все его делители. Идём как всегда до корня. Если мы нашли делитель, мы добавляем его в массив a c помощью команды append и ищем его "брата". Второй делитель ("брат") не должен равняться самому делителю j, т.к. нам сказали, что все делители должны быть различны. Одинаковые делители j и b могут получится, если из нашего числа i извлекается целый корень. Ведь для делителя √i является парой этот же делитель ( √i* √i=i).
После прохождения внутреннего цикла (с переменной j) в массиве a будут сидеть все делители числа i. Если их ровно 4, то сортируем массив a и выводим на экран два наибольших.
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Найдите все натуральные числа, принадлежащие отрезку [4234679; 10157812] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе само число и его наибольший нетривиальный делитель. Найденные числа расположите в порядке возрастания.
import math for i in range(4234679, 10157813): if int(math.sqrt(i))**2 == i: a=[] for j in range(2, int(math.sqrt(i))+1): if i%j==0: a.append(j) b=i//j if j!=b: a.append(b) if len(a)==3: a.sort() print(i, a[2])
Как у нас могут быть три различных нетривиальных делителя, когда делители идут, как мы выяснили, парами? Это может быть, когда существует целый корень из этого числа. Тогда в паре два числа будут одинаковыми (√i* √i = i). Поэтому в этой задаче нас интересуют числа из которых извлекается целый корень.
Если этим рассуждением не воспользуемся, то программа будет считать очень долго, потому что здесь диапазон и сами числа очень большие.
Далее, решаем, как и в прошлый раз.
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ "?" означает ровно одну произвольную цифру;
— символ "*" означает любую последовательность цифр произвольной длины; в том числе "*" может задавать и пустую последовательность.
Например, маске 123*4?5 соответсвуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 108, найдите все числа, соответствующие маске 1234*7, делящиеся на 141 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 141.
Здесь самый главный момент заключается в том, что есть верхняя граница 108. Т.е. самое большое число, которое нужно рассмотреть 1234[999]7 <= 108 = 100000000. Нижняя граница тоже задана, когда вместо звёздочки ни одной цифры не будет 12347.
i=12347 #Вместо звёздочки ноль разрядов if i%141==0: print(i, i//141) #Вместо звёздочки один разряд for x in '0123456789': s = '1234' + x + '7' i=int(s) if i%141==0: print(i, i//141) #Вместо звёздочки два разряда for x in '0123456789': for y in '0123456789': s = '1234' + x + y + '7' i=int(s) if i%141==0: print(i, i//141) #Вместо звёздочки три разряда for x in '0123456789': for y in '0123456789': for z in '0123456789': s = '1234' + x + y + z + '7' i = int(s) if i%141==0: print(i, i//141)
Таким образом, нужно рассмотреть, когда вместо звёздочки ноль разрядов, один разряд, два разряда и три разряда.
Каждый разряд перебираем как цифры (символы). Формируем строку s, а затем её переводим в тип int.
Когда два разряда или три разряда нужно перебирать строку с помощью вложенных циклов.
Функция fnmatch() модуля fnmatch проверяет, соответствует ли строка имени файла шаблонной строке, возвращая True или False .
Пример использования:
from fnmatch import * s = ['Привет','пакет','приток','перемена'] for x in s: if fnmatch(x,'п*е?'): print(x,'yes') else: print(x,'no')
Результат запуска:
from fnmatch import * for i in range(141, 10**8+1, 141): if fnmatch(str(i), '1234*7'): print(i, i//141)