ЕГЭ. Реализация алгоритмических задач на Python

Реализация алгоритмических задач из ЕГЭ на Python

Возможные алгоритмические задачи для подраздела 1.1 перечня требований к уровню подготовки выпускников, достижение которых проверяется на ЕГЭ (согласно документу ФИПИ - "Кодификатор элементов содержания и требований к уровню подготовки выпускников образовательных организаций для проведения единого государственного экзамена по информатике и ИКТ")¶

1. Нахождение минимума и максимума двух, трех, четырех данных чисел без использования массивов и циклов.

В стили Python (не используем на ЕГЭ!):

In [14]:

print(min(map(int,input().split())))

6 4 5 3 8
3

Подходит для любого количества чисел.

Для ЕГЭ в классическом стиле :

Один из возможных вариантов для четырех чисел:

In [7]:

a,b,c,d=map(int,input().split())
m=a
if m>b: m=b
if m>c: m=c
if m>d: m=d
print(m)

5 4 3 6
3

2. Нахождение всех корней заданного квадратного уравнения.

In [16]:

from math import sqrt
a,b,c = map(int,input().split())
d = b*b - 4*a*c
if d==0:
    print('Один корень x=', -b/(2*a))
elif d>0:
    print('Два корня: x1=',(-b-sqrt(d))/(2*a),', x2=',(-b+sqrt(d))/(2*a))
else:
    print('Нет корней в области действительных чисел.')

1 3 2
Два корня: x1= -2.0 , x2= -1.0

In [ ]:

1 2 1
Один корень x= -1.0
2 2 2
Нет корней в области действительных чисел.

3. Запись натурального числа в позиционной системе с основанием, меньшим или равным 10. Обработка и преобразование такой записи числа.

В качестве ответа получаем строку y из символов-цифр в системе счисления q:

In [4]:

x,q = map(int,input().split())
t = x
y = ''
while t:
    y = str(t%q) + y
    t //= q
print(y)

18 4
102

В качестве ответа получаем список y из цифр в системе счисления q:

In [7]:

x,q = map(int,input().split())
t = x
y = []
while t:
    y.append(t%q)
    t //= q
print(y)

18 4
[2, 0, 1]

4. Нахождение сумм, произведений элементов данной конечной числовой последовательности (или массива).

В стили Python (не используем на ЕГЭ!):

In [1]:

print(sum(map(int,input().split())))

15

Для ЕГЭ в классическом стиле :

сумма последовательности:

In [3]:

s=0
for a in input().split():
    s += int(a)
print(s)

15

произведение последовательности:

In [4]:

p=1
for a in input().split():
    p *= int(a)
print(p)

120

сумма элементов имеющегося списка x (вместо массива):

In [5]:

x=[2,4,3,5,1]
s=0
for a in x:
    s += a
print(s)

15

5. Использование цикла для решения простых переборных задач (поиск наименьшего простого делителя данного натурального числа, проверка числа на простоту и т.д.).

наименьшей делитель r данного натурального числа n:

In [ ]:

n=int(input())
r=2
while n%r and r*r<=n: r +=1
if  r*r<=n: print(r)
else: print (n)

35 

5 

36 

2 

37 

37

проверка числа n на простоту

In [9]:

n=int(input())
r=2
while n%r and r*r<=n: r +=1
if  r*r<=n: print('Составное')
else: print ('Простое')

35
Составное

In [ ]:

37
Простое

наименьшей простой делитель r 

данного натурального числа n:

In [36]:

n=int(input())
r=2
prostoe=True
while n%r and r*r<=n: r +=1
if  r*r<=n:
    print(r)
    prostoe=False
if prostoe: print ('Число является простым')

Число является простым

35

5

наибольший общий делитель a и b:

In [38]:

a,b = map(int,input().split())
while a^b:
    if a>b: a -= b
    else: b -= a
print(a)

7

наименьшее общее кратное a и b- НОК(𝑎,𝑏)=𝑎∗𝑏НОД(𝑎,𝑏)$НОК(a,b)=\frac{a\ast b}{НОД(a,b)}$:

In [10]:

a,b = map(int,input().split())
x,y = a,b
while a^b:
    if a>b: a-=b
    else: b -=a
print(x*y//a)

14 35
70

6. Заполнение элементов одномерного и двумерного массивов по заданным правилам.

Ввод элементов одномерного массива (списка) a с клавиатуры

Все элементы в одной строке:

In [22]:

a=list(map(int,input().split()))
print(a)

3 2 5 4
[3, 2, 5, 4]

N элементов, каждый с новой строки

In [25]:

N=int(input())
a=[]
for __ in range(N):
    a.append(int(input()))
print(a)

4
3
2
5
4
[3, 2, 5, 4]

Ввод элементов двумерного NxN массива (списка) a с клавиатуры

In [26]:

a=[]
N=int(input())
for __ in range(N):
    a.append(list(map(int,input().split())))
print(a)

3
1 2 3
2 3 4
3 4 5
[[1, 2, 3], [2, 3, 4], [3, 4, 5]]

Заполнение массива a 10-ю одинаковыми значениями (0)

In [27]:

a=[0]*10
print(a)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Заполнение массива a значениями последовательности. Например, геометрическая прогрессия с 𝑎0$a_0=4$ и 𝑞$q=1.5$ до an

In [28]:

N=int(input())
a=[4*1.5**i for i in range(N)]
print(a)

10
[4.0, 6.0, 9.0, 13.5, 20.25, 30.375, 45.5625, 68.34375, 102.515625, 153.7734375]

7. Операции с элементами массива.

Линейный поиск элемента

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

In [81]:

a=[7, 31, 53, 34]
print(sum(1 for i in a if i&1 and i%10==3)>0)

True

In [82]:

a=[7, 31, 35, 34]
print(sum(1 for i in a if i&1 and i%10==3)>0)

False

Положение первого элемента со значением x

In [62]:

a=[7, 31, 35, 34]
x=10
print(x in a and a.index(x))

False

In [64]:

a=[7, 31, 35, 34]
x=31
print(x in a and a.index(x))

1

Вставка и удаление элементов в массиве.

Вставка в позицию k1 значения x и удаление из элемента позиции k2

In [67]:

a=[7, 31, 35, 34]
print(a)
k1,x = 2,50
a.insert(k1,x)
print(a)
k2=1
a.pop(k2)
print(a)

[7, 31, 35, 34]
[7, 31, 50, 35, 34]

Out[67]:

31

[7, 50, 35, 34]

Перестановка элементов данного массива в обратном порядке.

In [68]:

a=[7, 31, 35, 34]
a=a[::-1]
print(a)

[34, 35, 31, 7]

Суммирование элементов массива.

В стиле Python

In [69]:

a=[7, 31, 35, 34]
print(sum(a))

107

По некоторому уловию. Например, cумма четных

In [76]:

a=[8, 31, 35, 34]
print(sum(i for i in a if i&1^1))

42

В классическом стиле

In [70]:

a=[7, 31, 35, 34]
s=0
for i in a:
    # if ... могут быть условия:
    s += i
print(s)

107

Проверка соответствия элементов массива некоторому условию.

Все элементы с заданными свойствами. Например, нечетные и положительные

In [84]:

a=[7, 31, 53, 34]
print(sum(1 for i in a if i&1 and i>0)==len(a))

False

In [83]:

a=[7, 31, 53, 35]
print(sum(1 for i in a if i&1 and i>0)==len(a))

True

Более рационально:

In [92]:

a=[7, 31, 53, 35]
L=len(a)
i=0
while i<L and a[i]&1 and a[i]>0:
    i +=1
print(i==L)

True

Является ли массив упорядоченным по возрастанию:

In [93]:

a=[7, 31, 53, 35]
L=len(a)
i=1
while i<L and a[i-1]<=a[i]>0:
    i +=1
print(i==L)

False

In [94]:

a=[7, 31, 35, 53]
L=len(a)
i=1
while i<L and a[i-1]<=a[i]>0:
    i +=1
print(i==L)

True

8. Нахождение второго по величине (второго минимального) значения в данном массиве за однократный просмотр массива

In [97]:

a=[47, 31, 9, 35, 53, 7]
m1=a[0]
m2=a[1]
if m2<m1: m1,m2 = m2,m1
for x in a[2:]:
    if x<m1:
        m2,m1 = m1,x
    elif x<m2:
        m2 = x
print(m2)

9

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

In [103]:

a=[17, 17, 11, 19, 35, 11, 27]
m,k = a[0],1
for x in a[1:]:
    if x<m:
        m,k = x,1
    elif x==m:
        k += 1
print(m,k)  

11 2

10. Операции с элементами массива, отобранных по некоторому условию

нахождение минимального четного элемента в массиве

In [107]:

a=[17, 18, 11, 12, 35, 11, 27]
m=False
for i in range(len(a)):
    if a[i]&1^1:
        if not m : m=a[i]
        elif i and a[i]<m: m=a[i]
print(m)        

12

In [108]:

a=[17, 17, 11, 19, 35, 11, 27]
m=False
for i in range(len(a)):
    if a[i]&1^1:
        if not m : m=a[i]
        elif i and a[i]<m: m=a[i]
print(m)        

False

нахождение количества и суммы всех четных элементов в массиве

In [110]:

a=[17, 18, 11, 12, 35, 11, 27]
k=0; s=0
for x in a:
    if x&1^1:
        k,s = k+1,s+x
print(k,s)   

2 30

11. Сортировка массива.

В стиле Python:

In [111]:

a=[17, 18, 11, 12, 35, 11, 27]
a.sort()
print(a)

[11, 11, 12, 17, 18, 27, 35]

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

Простые виды сортировки

1. Сортировку обменом (пузырьковая) - не эффективна со всех сторон (проверок - $N^2$ перестановок -  𝑁$N^2$) - рассматривать не будем

1. Сортировка выбором, по крайней мере, перестановок -  $N$

In [112]:

a=[17, 18, 11, 12, 35, 11, 27]
L=len(a)
for i in range(L-1):
    m=i
    for j in range(i,L):
        if a[j]<a[m]: m=j
    if m>i:
        a[m],a[i] = a[i],a[m]
print(a)

[11, 11, 12, 17, 18, 27, 35]

1. Сортировка вставками - хорошо работает на частично упорядоченных массивах

In [120]:

a=[17, 18, 11, 12, 35, 11, 27]
L=len(a)
for i in range(1,L):
    j=i
    while j and a[j]<a[j-1]:
        a[j],a[j-1] = a[j-1],a[j]
        j -= 1
print(a)

[11, 11, 12, 17, 18, 27, 35]

1. Сортировка подсчетом - хорошо работает, если диапазон значений значительно меньше количества элентов 
   $N$

In [1]:

a=[3, 5, 4, 3, 5, 4, 5, 4, 4]
k=[0]*6
for i in a:
    k[i] += 1
for i in range(6):
    for j in range(k[i]):
        print(i, end=' ')

3 3 4 4 4 4 5 5 5 

Слияние двух упорядоченных массивов в один без использования сортировки.

In [2]:

a=[11, 12, 17, 18, 27]
b=[9, 15, 23, 25, 41, 50]
c=[]
ia=ib=0
while ia<len(a) and ib<len(b):
 if a[ia]<=b[ib]:
  c.append(a[ia])
  ia += 1
 else:
  c.append(b[ib])
  ib += 1
if ia<len(a):
 c.extend(a[ia:])
else:
 c.extend(b[ib:])
print(c)

[9, 11, 12, 15, 17, 18, 23, 25, 27, 41, 50]

12. Обработка отдельных символов данной строки. Подсчет частоты появления символа в строке.

1. Сколько раз в строке 𝑎$a$ встречается символ (строка) 
   $b$

In [6]:

a=input('введите строку: ')
b=input('введите символ (строку): ')
print(a.count(b))

введите строку: abracadabra
введите символ: ra
2

1. Определить в строке 𝑎$a$ позицию первого вхождения символа (строки) 
   $b$(или -1)

In [4]:

a=input('введите строку: ')
b=input('введите символ (строку): ')
print(a.find(b))

введите строку: abracadabra
введите символ: r
2

1. Есть ли в строке 
   $a$ символ (строка) 𝑏$b$

In [7]:

a=input('введите строку: ')
b=input('введите символ (строку): ')
print(b in a)

введите строку: abracadabra
введите символ: ad
True

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

1. Разбиение на слова попробельным символами.

In [9]:

print(input().split())

Разбиение на слова попробельным символами
['Разбиение', 'на', 'слова', 'попробельным', 'символами']

1. Удаление из строки 
   $a$ подстроки 
   $b$

In [15]:

a='abracadabra'
b='br'
print(''.join(a.split(b)))

aacadaa

1. Змена в строке 
   $a$ подстроки 
   $b$ на строку 
   $c$

In [16]:

a='abracadabra'
b='br'
c='dub'
print(a.replace(b,c))

adubacadaduba