Особенности решения некоторых задач ЕГЭ по информатике | Миньковская Татьяна Сергеевна. Работа №346517

ОСОБЕННОСТИ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ КОМПЬЮТЕРНОГО ЕГЭ

ПО ИНФОРМАТИКЕ

Аннотация. В работе рассматриваются некоторые задачи КЕГЭ по информатике и приводятся алгоритмы их решения, программная реализация на языке Python.

Ключевые слова: ЕГЭ по информатике и ИКТ в компьютерной форме, алгоритмы решения, язык Python.

Практика показывает, что в целом тема «Программирование» не вызывает у школьников сложностей. Таким образом, 6, 17, 22 задачи КЕГЭ решаются легко.

В некоторых других задачах встречаются задания, для которых недостаточно элементарных знаний программирования, требуются более глубокие знания, в том числе более глубокие знания других предметов, таких, как например, математика.

Рассмотрим типы таких заданий более подробно и приведем решение на языке Python. Рассмотрим прототип задачи 17 из КЕГЭ.

Задача 17.120. Определите количество принадлежащих отрезку [251763; 514827] натуральных чисел, которые делятся без остатка на сумму своих цифр, и наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

Решение.

Можно попытаться решить задачу простым применением алгоритма нахождения суммы цифр числа, а затем делителей числа.

Программа может выглядеть следующим образом:

k=0

a=251763

b=514828

mi=b+1

for i in range (a, b+1):

s=0

x=i

while x>0:

s+=x%10

x//=10

if i%s==0:

mi=min (i, mi)

k+=1

print (k, mi)

25708 251775

Но такая программа при тестировании на маленьких числах выполняется быстро и правильно, а в случае тех чисел, которые даны в условии задачи выполняется дольше, что в случае ограниченности времени экзамена (3 часа 55 минут) может являться критичным.

Приведем пример программы, в которой сумма цифр числа находится несколько «искусственным» способом.

k=0

a=251763

b=514828

mi=b+1

for i in range (a, b+1):

s=0

g=str(i)

for j in range (6):

s+=int(g[j])

if i%s==0:

mi=min (i, mi)

k+=1

print (k, mi)

25708 251775

Далее рассмотрим прототип задачи 25 из КЕГЭ.

Задача 25.24. Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [11275; 16328], числа, имеющие ровно 5 различных делителей. Выведите эти делители для каждого найденного числа в порядке возрастания.

Решение.

Снова решим задачу простым применением алгоритма нахождения делителей числа.

s=0

for i in range (11275,16329):

k=0

for j in range (2, i//2+1):

if i%j==0:

k+=1

if k>3: break if k==3:

print ("1", end=" ")

for j in range (2, i//2+1):

if i%j==0:

print (j, end=" ")

print(i)

1 11 121 1331 14641

Обратим внимание, что в этой задаче числа требуется искать на относительно небольшом промежутке - [11275; 16328]. В следующей задаче промежуток значительно больше.

Задача 25.130. Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Найдите все натуральные числа, принадлежащие отрезку [50034679; 92136895] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе само число и его наибольший нетривиальный делитель. Найденные числа расположите в порядке возрастания.

Решение.

Если применить алгоритм предыдущей задачи, то снова получим долгое время выполнения программы. Следует оптимизировать данный алгоритм, возможно применив математические методы.

Вначале запустим предыдущую программу на относительно небольшом диапазоне чисел и проанализируем полученные результаты.

s=0

for i in range (10,1000):

k=0

for j in range (2, i//2+1):

if i%j==0: k+=1 if k>3: break if k==3:

print ("1", end=" ")

for j in range (2, i//2+1):

if i%j==0:

print (j, end=" ")

print(i)

1 2 4 8 16

1 3 9 27 81

1 5 25 125 625

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

Составим программу, с учетом найденной закономерности. Вначале извлечем корень четвертой степени из чисел 50034679 и 92136895, получим, соответственно, числа 84,104 и 97,973. Так как следует рассматривать натуральные числа, то промежуток будет иметь вид [85, 97], нетрудно заметить, насколько был сокращен диапазон чисел. На этом промежутке остается найти простые числа, четвертая степень таких чисел и будет искомым числом из диапазона, данного в условии задачи:

a=50034679

b=92136895

a1=int (50034679**(0.25)) +1

b1=int (92136895**(0.25))

for i in range (a1, b1+1):

f=0

for j in range (2, i//2+1):

if i%j==0:

f+=1 break if f==0:

print (i**4, i**3)

62742241 704969

88529281 912673

Аналогично можно решить следующую задачу.

Задача 25.147. Найдите все натуральные числа, принадлежащие отрезку [103 000 000; 104 000 000], у которых ровно три различных чётных делителя. В ответе перечислите найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине нетривиальный делитель (не равный 1 и самому числу).

Решение.

Используя «прямой» алгоритм, напишем программу и снова запустим ее на небольшом диапазоне.

for i in range (7,1000):

k=0

for j in range (2, i//2+1,2):

if i%j==0:

k+=1

if k>2:

break

if k==2:

print(i)

8

18

50

98

242

338

578

722

Проанализировав результаты, найдем закономерность - ровно три различных чётных делителя имеют числа, являющиеся удвоенным квадратом простого числа. Обозначим числами a=103000000 и b=104000000 заданный промежуток. Далее, можно разделить на 2 числа а и в, извлечь квадратный корень из полученных значений, и привести к целому типу. К значению а1 требуется еще добавить 1. Далее в новом интервале [a1, b1] = [7177, 7211] достаточно найти простые числа, которые и будут являться вторыми по величине нетривиальными делителями.

a=103000000

b=104000000

a1=int((a//2)**(1/2))+1

b1=int((b//2)**(1/2))

print(a1,a1**2*2)

print(b1,b1**2*2)

for i in range(a1,b1+1):

f=0

for j in range(2,i//2+1):

if i%j==0:

f+=1 break if f==0: print(2*i**2,i)

7177 103018658

7211 103997042

103018658 7177

103305938 7187

103478498 7193

103881698 7207

103997042 7211

Приведем решение еще одной задачи типа 25.

Задача 25.147. Найдите все натуральные числа, N, принадлежащие отрезку [150 000 000; 300 000 000], которые можно представить в виде N = 2m • 3n, где m - чётное число, n - нечётное число. В ответе запишите все найденные числа в порядке возрастания, а справа от каждого числа - сумму m+n.

Решение.

for i in range (150000000,300000001):

if i%12==0 and int((i//12) **0.5) ==(i//12) **0.5:

for n in range (1,200,2):

for m in range (1,100):

if 4**m*3**n==i:

print(i,2*m+n)

break

181398528 21

201326592 27

229582512 19

254803968 25