Решение некоторых заданий ЕГЭ по информатике: «От простого к сложному»

XIX Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке

Решение некоторых заданий ЕГЭ по информатике: «От простого к сложному»

Хубулова Л.Г. 1
1МБОУ СОШ №30
Дзиова М.П. 1
1МБОУ СОШ №30
Автор работы награжден дипломом победителя III степени
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Введение

Известный автор-фантаст ХХ века Артур Кларк сказал, что «любая достаточно развитая технология неотличима от магии». Программирование действительно можно сравнить с волшебством, но только пока не научишься творить его сам.

Если говорить серьезно, то программирование — фундаментальный навык по той простой причине, что оно заставляет мыслить абстрактно. В его основе лежат принципы анализа и синтеза, или композиции и декомпозиции — это одно и то же по своей сути. В английском языке существует понятие «computational thinking», которое можно определить как совокупность умений мыслить абстрактно, критически и разделять задачу на небольшие части. Именно этому может научить программирование. Также все это здорово дисциплинирует и помогает мыслить структурно и стратегически.

При изучении раздела информатики «Алгоритмизация и программирование» уже с первых уроков преподаватель стала делать акценты на том, что эта тема будет необходима при решении заданий ЕГЭ по информатике. Каждый урок по программированию – открытие, приближающее к решению задач ЕГЭ.

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

  1. Целочисленная арифметика.

Операторы присваивания, циклы и условные операторы

в языке программирования.

Операции целочисленного деления (//) и взятия остатка (%)

Хорошие задачи, наглядно демонстрирующие работу, изучаемых операторо.

Дележ яблок - 1

n школьников делят k яблок поровну, неделящийся остаток остается в корзинке. Сколько яблок достанется каждому школьнику? Программа получает на вход числа n и k и должна вывести искомое количество яблок. (Пример: ввод: 3 14; вывод: 4)

Дележ яблок - 2

n школьников делят k яблок поровну, неделящийся остаток остается в корзинке. Сколько яблок останется в корзинке? Программа получает на вход числа n и k и должна вывести искомое количество яблок. (Пример: ввод: 3 14; вывод: 2)

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

А % B = 0

- условие делимости целого A на целое B.

A % 2 = 0

- условие чётности целого A.

A % 2 != 0

A% 2 =1

A% 2 >0

- условия нечётности целого A.

A% 10

- значение последней цифры в десятичной записи целого  А (например, 987 mod 10 = 7).

A // 10

число, десятичная запись которого получится отбрасыванием последней цифры в десятичной записи целого числа А (например, 987// 10 =98).

A % p

- значение последней цифры в p-ичной записи целого  А (например, при p=2, A mod 2 – последняя цифра записи А в двоичной системе счисления);

A // p

- число, p-ичная запись которого получится отбрасыванием последней цифры в p-ичной записи целого числа А (например, 510=1012;  510 // 2 =210=102; т.е. из 1012 получили 102);

  1. Дано двузначное число. Найти сумму его цифр.

a=int(input())

b=a//10+a%10

print(b)

  1. Дано трехзначное число. Найти сумму его цифр.

a=int(input())

b=a//100+a//10%10+a%10

print(b)

Усложняем задачу: находить сумму любого, вводимого с клавиатуры числа.

Найти сумму цифр любого, вводимого с клавиатуры числа.

a=int(input())

b=0

while a>0:

b=b+ a%10

a=a//10

print(b)

Определить количество цифр любого, вводимого с клавиатуры числа.

a=int(input())

b=0

while a>0:

b=b+ 1

a=a//10

print(b)

Сумма и количество цифр в введенном с клавиатуры числа z:

z = int(input())

s = 0

k = 0

while z>0:

k+=1

d = z%10

s +=d

z=z//10

print ('s=', s)

print ('k=',k)

Количество цифр в числе:

n=int(input())

l= len(str(n))

print(l)

Произведение цифр в введенном с клавиатуры числа z. (правильная инициализация)

z = int(input())

p = 1

while z>0:

d = z%10

p *=d

z=z//10

print ('pr =', p)

Сумма нечетных цифр в введенном с клавиатуры числа z. (добавляем условия)

z = int(input())

s = 0

while z>0:

d = z%10

if d%2!=0:

s +=d

z=z//10

print ('sn =', s)

Анализ программ, содержащих циклы и ветвления

Одно дело умение писать программы, а другое их правильно и грамотно читать.

Задача №1. Ниже записан алгоритм. Укажите наименьшее из таких чисел , при вводе которых алгоритм печатает сначала 2, а потом 15.

x = int(input())

a = 0

b = 1

while x>0 :

a = a+1

b = b*(x % 10)

x = x // 10

print(a)

print(b)

Анализируем программу:

  • видим, что в последней строке выводятся на экран переменные a и b, поэтому сначала нужно определить, что они обозначают в программе

  • перед началом цикла переменная a обнуляется, а переменная b равна 1

  • на каждом шаге цикла при выполнении некоторого условия переменная a увеличивается на 1, а b умножается на x % 10, то есть, на остаток от деления x на 10 – это последняя цифра десятичной записи числа x

  • в конце каждого шага цикла операция x = x // 10 отсекает последнюю цифру в десятичной записи числа

  • цикл заканчивается, когда перестаёт выполняться условие x > 0, то есть, когда все цифры исходного числа отброшены

  • таким образом, делаем вывод: после завершения цикла в переменной a находится количество цифр в десятичной записи числа, а в переменной b – их произведение

  • если было выведено 2 и 15, то в числа 2 цифры, и их произведение равно 15 таким образом, нам нужно найти минимальное двузначное число, в котором произведение значений цифр равно 15

  • поскольку число 15 может быть разложено на два сомножителя, меньших 10, только как 35, минимальное подходящее число – 35.

  • ответ: 35.

Задача №2. Ниже записана программа. Получив на вход число , эта программа печатает два числа, и . Укажите наибольшее из таких чисел , при вводе которых алгоритм печатает сначала 3, а потом 7.

x = int(input())

L = 0; M = 0

while x > 0:

L = L + 1

M = M + (x % 10)

x = x // 10

print(L, M)

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

Анализируем: переменная L (L:=0, L:= L + 1) работает как счетчик, что считает? Количество вхождений в цикл, а цикл работает до тех пор, пока моё число X, введенное с клавиатуры не «закончится» (whilex > 0 do), при каждом вхождении мы «отбрасываем» последнюю цифру числа (x:= xdiv 10;), таким образом становится очевидно, что в результате выполнения этой программы в переменной Lокажется число, равное количеству, значащих цифр в введенном числе X.Разобрались, введенное число будет трехзначным. Переменная M (M:=0, M:= M + xmod 10) считает сумму цифр, введенного числа X. С эти не сложно будет разобраться, т.к. учениками были самостоятельно написаны аналогичные программы. В результате проведенного анализа задача свелась к нахождению максимального трехзначного числа, сумма цифр которого равна 7. Необходимо еще сделать акцент на слове «максимальное». Очевидно, что результат программы будет таким же при вводе чисел 124,241,340,412,502,520,610…, но нас просили найти из всех возможных чисел максимальное, при вводе которого, программа печатает сначала 3, а потом 7, и подвести таким образом к верному ответу 700.

Задача №3. Ниже записан алгоритм. Сколько существует таких чисел , при вводе которых алгоритм печатает сначала 2, а потом 12?

x = int(input())

a = 0

b = 0

while x>0 :

a = a + 1

b = b + (x % 10)

x = x // 10

print(a)

print(b)

  • видим, что в последней строке выводятся на экран переменные a и b, поэтому сначала нужно определить, что они обозначают в программе

  • перед началом цикла переменные a и b обнуляются

  • на каждом шаге цикла при выполнении некоторого условия переменная a увеличивается на 1, а b увеличивается на x % 10, то есть, на остаток от деления x на 10 – это последняя цифра десятичной записи числа x

  • в конце каждого шага цикла операция x = x // 10 отсекает последнюю цифру в десятичной записи числа

  • цикл заканчивается, когда перестаёт выполняться условие x > 0, то есть, когда все цифры исходного числа отброшены

  • таким образом, делаем вывод: после завершения цикла в переменной a находится количество цифр в десятичной записи числа, а в переменной b – их сумма

  • если было выведено 2 и 12, то в числе 2 цифры, и их сумма равна 12 таким образом, нам нужно найти все двузначные числа, в котором сумма значений цифр равна 12

  • число 12 может быть разложено на два слагаемых, меньших 10, как

12 = 3 + 9 = 4 + 8 = 5 + 7 = 6 + 6 = 7 + 5 = 8 + 4 = 9 + 3,

  • нам подходят числа 39, 48, 57, 66, 75, 84 и 93

  • всего таких чисел - 7

  • ответ: 7.

III. Системы счисления.

«Миром правят цифры!» Это высказывание великого ученого Пифагора Самосского стало крылатой фразой. Существует много различных интерпретаций этого выражения, одни говорят, что Пифагор подходил к этому с мистических позиций, другое предположение - что все закономерности мира можно выразить с помощью чисел.

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

Перевод из 2-ой СС в 10-ую

z2 = int(input())

z10 = 0

k=1

while z2>0:

d = z2%10

z10 +=d*k

z2=z2//10

k *=2

print ('z10 =', z10)

Перевод из 10-ой СС в 2-ую

z10 = int(input())

z2 = 0

k=1

while z10>0:

d=z10 % 2

z2=z2 + d*k

z10=z10//2

k *=10

print ('z2 =', z2)

Эти же алгоритмы можно реализовать, используя строковые переменные:

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

z10 = int(input('число'))

q = int(input('основание'))

s=''

while z10>0:

d=z10%q

s+=str(d)

z10//=q

s=s[::-1]

print (s)

z10 = int(input('число'))

q = int(input('основание'))

s=''

while z10>0:

d=z10%q

s=str(d)+s

z10//=q

print (s)

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

В этом варианте сразу собираем остатки в нужном порядке.

Задача, нахождения суммы цифр числа, введенного с клавиатуры, представленного в двоичной СС.

Что меняется в коде для решения этой задачи в отличие от нашей «классической» задачи, нахождения суммы цифр числа? (d=z % 2 и z=z//2)

Эту задачу можно интерпретировать, как задачу подсчет количества «1» в двоичной записи числа ( в двоичной записи числа будут только единицы и нули, поэтому для двоичной СС сумма цифр и количество единиц одно и тоже)

Сумма цифр и количество «1» в двоичной записи числа

z=int (input())

k = 0

while z >0:

d=z % 2

k+=d

z=z//2

print ('kol 1 =', k)# print ('sum=', k)

Количество «1» в двоичной записи числа

z10=int (input())

k = 0

while z10>0:

d=z10 % 2

if d==1:

k+=1

z10=z10//2

print ('kol 1 =', k)

Что изменится, если в задаче идёт речь о СС отличной от двоичной ?

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

z10 = int(input())

s = 0

while z10>0:

d=z10 % 8

s+=d

z10=z10//8

print ('s =', s)

Количество заданных цифр (с) в восьмеричной записи числа.

z10 = int(input())

k=0

s = 0

while z10>0:

d=z10 % 8

if d==c:

k+=1

z10=z10//8

print ('kol c =', k)

Попробуем изменить основание СС, т.е что изменится если я хочу написать программу для переводе в троичную, восьмеричную и т.д. СС?

Далее можно рассмотреть блоки заданий ЕГЭ 14, 16, 17, 22 (системы счисления, анализ программы, содержащей циклы и ветвления), широко представленные на сайте http://kpolyakov.spb.ru/index.htm

Решение заданий ЕГЭ14

(повышенный уровень)

Позиционные системы счисления

Основываясь на этом приёме можно легко решить задание ЕГЭ 14

Задача №1. Значение арифметического выражения 43∙7103 – 21∙757 + 98 записали в системе счисления с основанием 7. Найдите сумму разрядов получившегося числа и запишите её в ответе в десятичной системе счисления.

z= 43*7**103-21*7**57+98

s=0

while z>0:

s+=z%7

z//=7

print (s)

ответ:276

Задача №2. Сколько единиц в двоичной записи числа

8115 – 4123 + 2543 – 15?

Можно рассмотреть решение этой задачи с использованием, знакомых формул из раздела СС:

  • приведем все слагаемые к основанию 2

2345-2246+2543-24+20

  • расположим все слагаемые в порядке убывания

2543+2345-2246-24+20

  • преобразуем

2543+2345-2247+2246-24+20

  • применим формулу

2345-2247= 11…11100…000 (345-246=98 единиц и 246 нулей)

2246-24= 11…1110000 (246-4=242 единицы и 4 нуля)

  • Считаем единицы

1+98+242+1=342 – это ответ!

А теперь, учитывая всё выше сказанное, напишем код, для решения этой задачи:

z10 = 8**115 - 4**123+2**543-15

k = 0

while z10>0:

d=z10 % 2

k+=d

z10=z10//2

print ('kol 1 =', k)

Задача №3. Значение арифметического выражения: 497 + 721 – 7 – записали в системе счисления с основанием 7. Сколько цифр 6 содержится в этой записи?

x = 49**7 + 7**21 - 7

k6 = 0

while x>0:

if x % 7 == 6:

k6 += 1

x //= 7

print( k6 )

Задача №4. Значение арифметического выражения: 6410 + 290 - 16 записали в системе счисления с основанием 8. Сколько цифр «7» содержится в этой записи?

  • Приведём все числа к степеням восьмерки, учитывая, что 16 = 64 - 48 =82-6∙81

6410 + 290 - 16 = (82)10 + 23∙30 – (82 – 48) = 820 + 830 – 82 + 6∙81

  • Перепишем выражение, располагая степени восьмёрки в порядке убывания:
    820 + 830 – 82 + 6∙81 = 830 +820 – 82 + 6∙81

  • Очевидно, что «семёрки» в восьмеричной записи значения выражения возникнут только за счёт вычисления разности 820 – 82, их количество равно 20-2=18

  • Ответ: 18

Код решения этой задачи:

x = 64**10 + 2**90 - 16

k7 = 0

while x>0:

if x % 8 == 7:

k7 += 1

x //= 8

print( k7 )

Задача №5. Число 1234 записали в системах счисления с основаниями от 2 до 10 включительно. При каком основании сумма цифр в записи этого числа будет максимальной? Если таких оснований несколько, то укажите максимальное из них.

Код решения этой задачи:

x=1234

q=0

sm=0

for os in range (2,11):

s=0

z=x

while z>0:

s+=z%os

z=z//os

if s>=sm:

sm=s

q=os

print (q)

Решение заданий ЕГЭ16

(повышенный уровень)

Рекурсия. Рекурсивные процедуры и функции

Задача №1. Алгоритм вычисления функции F(n) задан следующими соотношениями:

F(n) = n· n5 при n > 15

F(n) = n· F(n+2) + n + F(n+3), если n  15

Чему равна сумма цифр значения функции F(1)?

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

s=0

while z>0:

s=s+z%10

z=z//10

def f(n):

if n>15:

return n*n-5

else:

return n*f(n+2)+n+f(n+3)

z=f(1)

s=0

while z>0:

s=s+z%10

z=z//10

print(s)

Задача №2. Алгоритм вычисления функции F(n) задан следующими соотношениями:

F(n) = n· n + n + 4, при n > 30

F(n) = F(n+1) + 3· F(n+4), при чётных n  30

F(n) = 2· F(n+2) + F(n+5), при нечётных n  30

Определите количество натуральных значений n из отрезка [1; 1000], для которых сумма цифр значения F(n) равна 27.

def f(n):

if n>30:

return n*n+5*n+4

else:

if n%2==0:

return f(n+1)+3*f(n+4)

else:

return 2*f(n+2)+f(n+5)

k=0

for n in range (1,1001):

z=f(n)

s=0

while z>0:

s+=z%10

z=z//10

if s==27:

k+=1

print (k)

ответ: 137

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

Перебор целых чисел на заданном отрезке.

Разбиение числа на отдельные цифры

Здесь можно рассмотреть «веселые» задачи про счастливые билеты (перебор чисел от 1000 до 9999).

  1. Назовём натуральное пятизначное число N (10000 N  99999) счастливым, если суммы двух его первых и двух последних цифр равны (или различаются не более, чем на 2). Найдите количество таких чисел.

kb=0

for b in range (10000,100000):

s12=b//10000+(b//1000)%10

s45=b%10+(b%100)//10

if s12==s45:

kb+=1

print (b)

print (kb)

  1. Назовём натуральное число N (10008  N  77778) счастливым, если суммы двух первых и двух последних цифр его восьмеричной записи равны. Найдите количество таких чисел.

  2. Назовём натуральное число N (10008  N  77778) счастливым, если суммы двух первых и двух последних цифр его восьмеричной записи различаются не больше, чем на 2. Найдите количество таких чисел.

  3. Решение заданий ЕГЭ 17

(повышенный уровень)

Перебор целых чисел на заданном отрезке. Проверка делимости

Задача №1. Рассматривается множество целых чисел, принадлежащих числовому отрезку [3721; 7752], которые удовлетворяют следующим условиям:

− сумма цифр числа кратна 3;

− двоичная запись числа не заканчивается на 000.

Найдите количество таких чисел и минимальное из них.

И в этих задачах внедряется, знакомый уже алгоритм нахождения суммы цифр. И знание систем счисления:

  • Что значит условие «двоичная запись числа не заканчивается на 000»? Можно разными способами выделить последние три цифры (пытаться переводить в двоичную СС, воспользоваться функцией перевода в дв.СС и выделить последние три символа и сравнивать их с «000», как символьные переменные, а можно подумать:

  1. Что происходит с двоичным числом, если к нему приписать 0?

  2. А если два нуля «00»?

  3. А если три нуля «000»?

Таким образом, десятичное число, оканчивающееся на три нуля в двоичной записи кратно 8. Вот мы и получили реализацию второго условия ( if x%8!=0:). Причем, рекомендую осуществлять эту проверку в первую очередь, дабы считать сумму цифр только этих чисел, а не всех в заданном интервале.

  • И вот он опять, знакомый нам алгоритм, нахождения суммы цифр числа:

z=x

s=0

while z>0:

s=s+z%10

z=z//10

В первой строке, мы переназначаем значение параметра цикла x переменной z!

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

if x<min:

min=x

Можно для нахождения мин, в цикле задать обратный перебор (с шагом -1) и в этом случае, последнее найденное число, удовлетворяющее выше перечисленным условиям и будет минимальным!

k=0

min=7760

for x in range (3721,7752+1):

if x%8!=0:

z=x

s=0

while z>0:

s=s+z%10

z=z//10

if s%3==0:

k+=1

if x<min:

min=x

print (k, min)

k=0

min=0

for x in range (7752,3721-1,-1):

if x%8!=0:

z=x

s=0

while z>0:

s=s+z%10

z=z//10

if s%3==0:

k+=1

min=x

print (k, min)

Задача №2. Рассматривается множество целых чисел, принадлежащих числовому отрезку [3912; 9193], которые удовлетворяют следующим условиям:

− сумма цифр числа кратна 9;

− шестнадцатеричная запись числа не заканчивается на 21.

Найдите количество таких чисел и максимальное из них.

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

  1. Если шестнадцатеричное число заканчивается «00», то это значит, что десятичное число кратно (265=162)

  2. Ну, а если оно заканчивается на 21, то это означает, что при делении на 256 исходное число в остатке даст 33 (2116=3310)

  3. Таким образом, наше условие запишется следующим образом:

if x%256!=33:

Задача №3. Рассматривается множество целых чисел, принадлежащих числовому отрезку [1000; 9999], запись которых в пятеричной системе имеет не менее 6 цифр и заканчивается на 21 или 23. Найдите количество таких чисел и минимальное из них.

k=0

min=0

for x in range (9999,1000-1,-1):

if x>=5**5 and (x%25==11 or x%25==13):

k+=1

min=x

print (k, min)

В этой задаче необходимо проанализировать условия:

  1. не менее 6 цифр в 5-ой СС – означает, что мое десятичное число должно быть не менее, чем 55

  2. ну а признаки «заканчивается на 21 или 23» мы уже оговорили!

Решение заданий ЕГЭ 25

(высокий уровень)

Обработка целых чисел. Проверка делимости

Задача №1. Cреди целых чисел, принадлежащих числовому отрезку [87921; 88187], найдите числа, сумма цифр которых кратна 14, а произведение цифр кратно 18 и не равно 0. Для каждого найденного числа запишите сумму и произведение его цифр в таблицу на экране с новой строки.

for x in range (87921,88188):

z=x

s=0

p=1

while z>0:

s+=z%10

p*=z%10

z=z//10

if s%14==0 and p%18==0 and p!=0:

print (s,p)

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

Задача №2. Среди целых чисел, принадлежащих числовому отрезку [2031; 14312], найдите числа, которые не содержат цифру 2, если записать их в системе счисления с основанием 11. Ответом будет максимум среди найденных чисел.

mx=0

for x in range (2031,14313):

z=x

k2=0

while z>0:

d=z%11

if d==2:

k2+=1

z=z//11

if k2==0:

mx=x

print (mx)

А в этой задаче мы используем знакомый алгоритм поиска заданных цифр в представлении числа в позиционной системе с заданным основанием.

Задача №3. Уникальным назовём число, если у него только третья и пятая цифры чётные. Для интервала [33333;55555] найдите количество таких чисел, которые не делятся на 6, 7, 8 и разность максимального и минимального из них. В ответе укажите два числа: сначала количество чисел, а потом разность.

k=0

min =55600

max=0

for x in range (33333,55556):

d=[0]*5

if x%6!=0 and x%7!=0 and x%8!=0:

z=x

for i in range (5):

d[i]=z%10

z=z//10

if d[0]%2==0 and d[2]%2==0 and d[1]%2!=0 and d[4]%2!=0 and d[3]%2!=0:

k+=1

max=x

if x<min:

min=x

print (k, max-min)

В этой задаче необходимо проверить четность конкретных цифр разрядов, поэтому мы сформировали массив из цифр числа, удовлетворяющих пока остальным условиям (не делятся на 6, 7, 8 ). И уже потом проанализировали конкретные цифры, но с учетом нумерации элементов массива.

IV. Алгоритм Эвклида.

В основе решения многих задач, в том числе и олимпиадных, лежит алгоритм Эвклида

Идея алгоритма Евклида

Идея этого алгоритма основана на:

1. Свойство, что если M>N, то НОД(М, N) = НОД(М - N, N).

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

Доказательство: пусть К - общий делитель М и N (M> N). Это значит, что М = mК, N = nК, где m, n - натуральные числа, причем m > n. Тогда М - N = К(m - n), откуда следует, что К - делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N, в том числе и наибольший общий делитель.

2.Второе очевидное свойство: НОД(М, М) = М.

Для "ручного" счета алгоритм Евклида выглядит так:

1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;

2) заменить большее число разностью большего и меньшего из чисел;

3) вернуться к выполнению п. 1.

Программа

Блок-схема алгоритма Евклида

print ('vved 2 chisla');

m = int(input())

n= int (input())

while m!=n:

if m>n:

m=m-n

else:

n=n-m

print ('nod', m)

 
  1. Выполнить на компьютере программу Evklid. Протестировать ее на значениях М= 32, N = 24;

М = 696, N = 234.

  1. Проверить, являются ли два данных числа взаимно простыми. Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.

И вот теперь, когда ученик не просто знает, как это работает, но и написал эту программу самостоятельно, ему не должно составить труда решать задачи следующего типа.

 

x = int(input())

L = x - 30

M = x + 30

while L != M:

    if L > M:  L = L - M

    else:   M = M - L

print(M)

Задача №1. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 15.

Ключевой момент решения: нужно узнать в строках программы, которые выделены, АЛГОРИТМ ЕВКЛИДА для вычисления наибольшего общего делителя (НОД) чисел, записанный в переменные M и L, которые, в свою очередь образованы из введенного с клавиатуры числа x.

Если не знать, что делают эти 5 строк, то решить эту задачу достаточно сложно! Но, мы то уже в теме...

Задача №2. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 2.

x = int(input())

L = x - 12

M = x + 12

while L != M:

    if L > M:

        L = L - M

    else:

        M = M - L

print(M)

Решение заданий ЕГЭ 25

(высокий уровень)

Обработка целых чисел. Проверка делимости

  1. Напишите программу, которая выводит все делители числа, введенного с клавиатуры.

  2. Напишите программу, которая выводит все простые числа на заданном отрезке [30,151]

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

1

2

ответ

for x in range (258274,258298):

kd=0

for d in range (1,x+1):

if x%d==0:

kd+=1

if kd==4:

for d in range (1,x+1):

if x%d==0:

print (d)

for x in range (258274,258298):

kd=[]

for d in range (1,x+1):

if x%d==0:

kd.append (d)

if len(kd)==4:

print (*kd)

создаем массив для делителей каждого числа x и выводим, только те, длина которых =4.

1 17 15193 258281
1 181 1427 258287
1 173 1493 258289
1 7 36899 258293
1 5 51659 258295

Задача №2. Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [394441; 394505], числа, имеющие максимальное количество различных делителей. Если таких чисел несколько, то найдите минимальное из них. Выведите количество делителей найденного числа и два наибольших делителя в порядке убывания.

md=0

c=0

for x in range (394441,394506):

kd=[]

for d in range (1,x+1):

if x%d==0:

kd.append (d)

if len(kd)>md:

md=len (kd)

c=x

kdd=[]

kdd=kd

print (md, kdd[-1], kdd[-2])

Результат:

48 394450 197225

Задача №3. Два числа называются дружественными если сумма собственных делителей (то есть всех положительных делителей, отличных от самого́ числа) любого их них равна другому числу. Например, числа 220 и 284 дружественные.

Выведите в порядке возрастания числа в диапазоне [2; 30000], имеющие дружественное число, большее чем само это число, и через пробел это дружественное число. Каждое следующее число из указанного диапазона выводите на новой строке.

for x in range (2,30001):

sd=0

for d in range (1,x):

if x%d==0:

sd+=d

sdd=0

for dd in range (1,sd):

if sd%dd==0:

sdd+=dd

if x>sd and x==sdd:

print (sd,x)

Результат:

220 284

1184 1210

2620 2924

5020 5564

6232 6368

10744 10856

12285 14595

17296 18416

V. Заключение

Очень интересен этот процесс познания «от простого к сложному»! Решение проблем – это ключевой навык, который полезен в жизни каждого человека. Программирование – отличный способ развить этот тип навыков для людей всех возрастов, особенно детей. Изучать команды, с помощью которых можно достичь определенной цели. Разбивать большую сложную проблему на несколько простых, менее сложных и, следовательно, которые можно легче решать. Благодаря программированию учимся решать проблемы и анализировать их, развивают привычку искать лучшие и более эффективные решения. С навыками программирования появляется возможность с нуля создать продукт или реализовать идею — приложение, сайт, программу — так, как это нужно именно тебе. Буду продолжать изучать программирование и решать задачи повышенной сложности.

Список литературы:

  1. «Изучем Python», Марк Лутц

  2. Сайт http://kpolyakov.spb.ru/index.htm

  3. Python для начинающих, https://pythonworld.ru/samouchitel-python

Просмотров работы: 1663