2-5 класс
2-6 класс
6-7 класс
7-8 класс
8-11 класс
8-11 класс
8-11 класс
10-11 класс
6-18 лет
от 18 лет
8-17 лет
Python. Простые алгоритмы
Рассматриваются алгоритмы линейной обработки списков, строк - это последовательный поиск и нахождение заданного значения, когда нужно просмотреть все элементы с первого до последнего. Как только будет найден элемент, равный заданному значению, необходимо вывести найденное значение и завершить поиск. Такой алгоритм является простейшим алгоритмом поиска. Сложность поиска O(n).
В программировании «О» большое описывает наихудший сценарий. Допустим, у нас есть массив чисел, где мы должны найти какое-то определенное число при помощи цикла for. Оно может быть найдено при любой итерации, и чем раньше, тем быстрее функция завершит работу. О-нотация всегда указывает на верхнюю границу, т. е., описывает случай, когда алгоритму придется осуществить максимальное количество итераций, чтобы найти искомое число. Как, например, в том случае, если это число окажется последним в перебираемом массиве
Пример. Определить количество чисел, у которых вторая с конца цифра – чётная
Дан список:
a= [1122, 3312, 2233, 6714, 5115, 5116, 7711, 8598, 1929,1]
Способ 1. Использование цикла for и операций // и %
n = len(a)
k=0
for i in range(n):
d = a[i]//10 # отбросить младшую цифру числа
d= d%10 # вторая с конца
if d%2==0 and d > 0:
k+=1
print('k =',k)
# k = 2
Временная сложность: O (n)
Способ 2. Использование генератора списка и операций // и %
b = ([x for x in a if x//10%10%2==0 and x//10%10 > 0])
print('Кол-во=',len(b))
# Кол-во= 2
Временная сложность: O (n)
Способ 3. Использование цикла for и операции среза
k=0
b = ([ str(x) for x in a ])
for x in b:
if len(x) > 1 and x[-2] in ['0','2','4','6','8']:
k+=1
print('Кол-во=',k)
# Кол-во= 2
Временная сложность: O (n)
Дан список:
a= [1,2,3,4,5,5,7,8,0,0]
Способ 1. Использование цикла for
k=0 # количество равных чисел
n= len(a)
for i in range(n):
for j in range(i+1,n):
if a[i]== a[j]:
k += 1
break
print("Кол-во различных чисел:", n-k)
# Кол-во различных чисел: 8
Временная сложность: O (n*n)
Способ 2. Использование среза
count = 0
for i in range(len(a)):
if not a[i] in a[0:i]:
count += 1
print("Кол-во различных чисел:",count)
# Кол-во различных чисел: 8
Временная сложность: O (n)
Способ 3. Использование множества set()
count = len(set(a))
print("Кол-во различных чисел:",count)
# Кол-во различных чисел: 8
Временная сложность: O (1)
Способ 4. Использование цикла for в одном проходе. Требуется сортировка
a.sort()
count = 1
for i in range(1, len(a)):
count += a[i - 1] != a[i]
print("Кол-во различных чисел:",count)
# Кол-во различных чисел: 8
Временная сложность: O(n log n)
Способ 5. Использование генератора. Требуется сортировка
a.sort()
count = len([a[0]] + [a[i] for i in range(1, len(a)) if a[i - 1] != a[i]])
print("Кол-во различных чисел:",count)
# Кол-во различных чисел: 8
Временная сложность: O(n)
Способ 6. Использование вспомогательного списка
b = []
for x in a:
if x not in b:
b.append(x)
print("Кол-во различных чисел:",len(b))
# Кол-во различных чисел: 8
Временная сложность: O(n)
Дан список:
a= [1,2,3,4,5,6,7,8,9,0]
Способ №1. Использование генератора списка и функции sum():
sm1 = sum([x for x in a if x %2==0])
sm2 = sum([x for x in a if x %2!=0])
print("сумма четных", sm1)
print("сумма нечетных", sm2)
# сумма четных 20
# сумма нечетных 25
Временная сложность: O(n)
Способ №2. Использование функции filter()
sm1 = sum(list(filter(lambda x: x %2 == 0, a)))
sm2 = sum(list(filter(lambda x: x %2 != 0, a)))
print("сумма четных", sm1)
print("сумма нечетных", sm2)
# сумма четных 20
# сумма нечетных 25
Временная сложность: O(n)
Способ №3 использование функции enumerate()
sm1 = sum([x for i, x in enumerate(a) if x%2==0])
sm2 = sum([x for i, x in enumerate(a) if x%2!=0])
print("сумма четных", sm1)
print("сумма нечетных", sm2)
# сумма четных 20
# сумма нечетных 25
Временная сложность: O (n)
Способ 4. Использование цикла for
sm1 = 0
sm2 = 0
for x in a:
if x % 2 == 0 :
sm1 += x
elif x % 2 != 0:
sm2 += x
print("сумма четных", sm1)
print("сумма нечетных", sm2)
# сумма четных 20
# сумма нечетных 25
Временная сложность: O (n)
Дан список:
a= [1,2,3,4,5,6,7,8,9,0]
Способ 1. Использование цикла for
sm=0
for x in a:
sm+=x
print("Сумма списка=", sm)
# Сумма списка= 45
Временная сложность: O (n)
Способ 2. Использование функции sum()
sm = sum(a)
print("Сумма списка=", sm)
# Сумма списка= 45
Временная сложность: O (n)
Способ №3 использование функции enumerate()
sm=0
for i,item in enumerate(a):
sm+=item
print("Сумма списка=", sm)
# Сумма списка= 45
Временная сложность: O (n)
Дан список:
a= [12,22,33,44,55,66,77,88,99,0]
Способ 1. Использование цикла for и str()
b = []
for x in a:
sm = 0
for digit in str(x):
sm += int(digit)
b.append(sm)
print("сумма цифр=", b)
# сумма цифр= [3, 4, 6, 8, 10, 12, 14, 16, 18, 0]
Временная сложность: O (n * k),
где n- количество элементов в списке,
k - среднее количество цифр в каждом числе
Способ 2. Использование цикла for и while
b = []
for x in a:
sm = 0
while x > 0:
digit = x%10
sm += digit
x=x//10
b.append(sm)
print("сумма цифр=", b)
# сумма цифр= [3, 4, 6, 8, 10, 12, 14, 16, 18, 0]
Временная сложность: O (n * k),
где n– количество элементов в списке,
k - среднее количество цифр в каждом числе
Способ 3. Использование цикла for и функции sum
b = []
for x in a:
sm = sum(int(digit) for digit in str(x))
b.append(sm)
print("сумма цифр=", b)
# сумма цифр= [3, 4, 6, 8, 10, 12, 14, 16, 18, 0]
Временная сложность: O (n * k),
где n- элементы в списке,
k - среднее количество цифр в каждом числе
Способ 4. Использование генератора
b = [sum(int(digit) for digit in str(x)) for x in a]
print("сумма цифр=", b)
# сумма цифр= [3, 4, 6, 8, 10, 12, 14, 16, 18, 0]
Временная сложность: O (n * k),
где n– количество элементов в списке,
k - среднее количество цифр в каждом числе