Задача 25 (массивы)

Тип 1. Маска числа

Задача 25 из «Демонстрационный вариант контрольных измерительных материалов
единого государственного экзамена 2023 года
по ИНФОРМАТИКЕ»

Условие:

Назовём маской числа последовательность цифр, в которой также могут
встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной
длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 1010, найдите все числа,
соответствующие маске 1?2139*4, делящиеся на 2023 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа
в порядке возрастания, а во втором столбце – соответствующие им
результаты деления этих чисел на 2023.
Количество строк в таблице для ответа избыточно

Решение:

#123*4?5
a = 1230405//2023
b = 2023*a   
for i in range(b,10000000000,2023):    
    b = str(i)
    if b[0] == '1' and b[1] == '2' and b[2] == '3' and b[-1] == '5' and b[-3] == '4':
        print(i,'  |  ',end='')
        print(i/2023)

Редкий случай с 2 или более звездочками

# Найти числа по маске 1*0*7 не больше 1000000000 кратные 202039

# 1 создаем список до 999 с нулями впереди
b = []
n = 999 
for i in range(n+1):
    stri = str(i)
    b.append(stri)
    delt = len(str(n))-len(stri)
    while delt > 0:                   
        b.append(delt * '0' + stri)   
        delt = delt - 1          

# 2 сама программа
for i in b:
    for j in b:
        c = '1'+ i + '0' + j + '7'
        if len(c)<=9 and int(c) % 202039 == 0:
            print(c)

Тип 2. Делители числа

Простые задачи (маленький диапазон):

Пример 1. Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [245 690; 245 756] простые числа. Выведите на экран все найденные простые числа в порядке возрастания, слева от каждого числа выведите его порядковый номер в последовательности. Каждая пара чисел должна быть выведена в отдельной строке.

Например, в диапазоне [5; 9] ровно два различных натуральных простых числа  — это числа 5 и 7, поэтому для этого диапазона вывод на экране должна содержать следующие значения:

1 5

3 7

Примечание. Простое число  — натуральное число, имеющее ровно два различных натуральных делителя  — единицу и самого себя.

Неоптимальное решение (простое в написании)

for n in range(245690,245756):
    k = 0
    for i in range(1,n+1):
        if n % i == 0:
            k = k + 1

    if k == 2:
        print(n)

print('=======================')

Оптимальное решение (но сложное в написании)

import math
 
for n in range(245690,245756):
    nn = int(math.sqrt(n))
    k = 0
    for i in range(1,nn+1):
        if n % i == 0:
            k = k + 1
            if int(n/i) != i:
                k = k + 1
            if k > 2:
                break
    if k == 2:
        print(n)

print('=======================')

Пример 2. Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [210 235; 210 300], числа, имеющие ровно четыре различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти четыре делителя в четыре соседних столбца на экране с новой строки. Делители в строке должны следовать в порядке возрастания.

Например, в диапазоне [10; 16] ровно четыре различных натуральных делителя имеет число 12, поэтому для этого диапазона вывод на экране должна содержать следующие значения:

2 3 4 6

Неоптимальное решение (простое в написании)

for n in range(210235,210300):
    k = 0
    m = []
    for i in range(2,n):
        if n % i == 0:
            k = k + 1
            m.append(i)
            
    if k == 4:
        print(n)
        print(m)
 
print('=======================')

Оптимальное решение (но сложное в написании)

import math
 
for n in range(210235,210300):
    nn = int(math.sqrt(n))
    k = 0
    m = []
    for i in range(2,nn):
        if n % i == 0:
            a = i
            k = k + 1
            m.append(a)

            b = int(n/i) 
            if b != a:
                k = k + 1
                m.append(b)
            if k > 4:
                break
    if k == 4:
        print(n)
        print(m)
 
print('=======================')

Сложные задачи (большой диапазон):

Пример 1. Найдите все натуральные числа, принадлежащие отрезку [45 000 000; 50 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.

import math, datetime

for n in range(45000000,46000000+1):
    nn = int(math.sqrt(n))
    k = 0
    m = []
    for i in range(1,nn+1):
        if n % i == 0:
            a = i
            b = int(n/i)
            if a%2 != 0:
                k = k + 1
                m.append(a)
            if b%2 != 0 and b != i:
                k = k + 1
                m.append(b)
            if k > 5:
                break
    if k == 5:
        print(n)
        print(m)

print('=======================)

 

Интересная задача с функцией

Пусть M(N)  — произведение 5 наименьших различных натуральных делителей натурального числа N, не считая единицы. Если у числа N меньше 5 таких делителей, то M(N) считается равным нулю.

Найдите 5 наименьших натуральных чисел, превышающих 200 000 000, для которых 0 < M(N) < N. В ответе запишите найденные значения M(N) в порядке возрастания соответствующих им чисел N.

def m(n):
    k = 0
    m = 1
    for i in range(2,n+1):
        if n%i == 0:
            k = k + 1
            m = m * i
            if k == 5:
                break
    if k < 5:
        rez = 0
    else:
        rez = m
    return(rez)    

k = 0
for i in range(200000001,300000000):
    f = m(i)
    if 0 < f and f < i:
        k = k + 1
        print(i,'===',f)
    if k == 5:
        print('===========');
        break

Ответ

• 1728
• 21632
• 1260
• 1152
• 4127787