Занятие 1

Лабораторная работа 1

Цель сегодняшнего семинара вспомнить базовые инструменты языка Python, разбиравшиеся вами в прошлом году. А именно:

  1. Циклы и вложенные циклы.
  2. Списки.
  3. Строки.
  4. Функции.
  5. Множества(set), словари(dict).
  6. Itertools

1. Циклы

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

1.1 while

while условие цикла:
    тело цикла

Задача 1.

Возведите число n в степень k, используя while

n = int(input()) # число
k = int(input()) # степень
In [ ]:

1.2 for

for <итерация> in <итерируемый объект>:
    тело

Функция range() возвращает последовательность чисел в заданном диапазоне. Выведем все числа от 0 до 10 включительно:

In [4]:
for i in range(10):
    print(i, end=" ")

0 1 2 3 4 5 6 7 8 9

Вспомним, что у range() есть аргументы - range(начало диапазона, конец диапазона, шаг). К примеру, мы можем вывести все нечётные числа от 1 до 30 таким образом.

In [3]:
for i in range(1, 30, 2):
    print(i, end=" ")

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29

Задача 2.

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

n = int(input()) # число
In [ ]:

Задача 3

Алгоритм нахождения НОД делением.

  1. Пусть даны два числа A и B.
  2. Большее число делим на меньшее.
  3. Если делится без остатка, то меньшее число это НОД.
  4. Если есть остаток, то большее число заменяем на остаток от деления.
  5. Переходим к пункту 1.
    a = int(input())
b = int(input()) 
while a != 0 and b != 0:
 # ваш код
print(a + b)
    Реализуйте алгоритм нахождение НОД делением с помощью цикла while.
In [ ]:

В модуле math языка программирования Python есть функция gcd, вычисляющая НОД.

In [5]:
import math
print(math.gcd(40, 20))

20

1.3 break и continue

Важно понимать, что:

  1. break – досрочное завершение цикла
  2. continue – пропуск одной итерации цикла

Рассмотрим два примера иллюстрирующих работу break и continue.

In [8]:
for n in range(1, 6):
    for x in range(2, n):
        if n % x == 0:
            print(n, 'равно', x, '*', n//x)
            break
    else:
        print(n, 'простое число')

1 простое число
2 простое число
3 простое число
4 равно 2 * 2
5 простое число
In [9]:
for num in range(1, 6):
    if num % 2 == 0:
        print(num, "- это число чётное")
        continue
    print(num, "- это число нечётное")

1 - это число нечётное
2 - это число чётное
3 - это число нечётное
4 - это число чётное
5 - это число нечётное

2. Списки

Вспомним некоторые вещи. Список — это упорядоченный набор элементов. При этом каждый элемент имеет свой индекс, нумерация начинается с 0. Списки в Python динамическими структурами данных, так можно удалить один или несколько элементов, заменить или добавить новые элементы. Вспомним некоторые действия со списками:

1. Создание списка: a = [1, 5, 9]
2. В одном списке одновременно могут находиться данные разных типов: a = ['hello', 2, True]
3. Доступ к элементу: a[2]
4. Срез списка от m до n + 1 с шагом k: a[m:n:k]
5. Добавление элемента в конец списка: a.append(x)
6. Вставка элемента на i позицию: a.insert(i, x)
7. Удаление элемента со значение x: a.remove(x)
8. Расчёт элементов списка: a.count(x)
9. Сортировка списка: a.sort(*, key=None, reverse=False)

Подробнее о действия со списками можно почитать в документации: https://docs.python.org/3/tutorial/datastructures.html

Задача 4

Давайте поработаем со списками.

  1. Создайте список
  2. Продемонстрируйте доступ к элементу, срезы, добавление новых элементов, удаление элементов, подсчёт значение.
  3. Отсортируйте список методом sort по убыванию и возрастанию.
In [ ]:

Задача 5 (Сортировка пузырьком)

Суть алгоритма в следующем.

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

Реализуйте данный алгоритм на Python, отсортировав следующий список:

In [12]:
from random import randint
n = 50
a = []
# создаём список из 50 элементов со случ. числами от 1 до 100.
for i in range(n):
    a.append(randint(1, 100))
print('неотсортированный список:', a)
# ваша сортировка:


# 
print('отсортированный список:', a)

неотсортированный список: [89, 94, 87, 3, 88, 98, 92, 39, 61, 65, 70, 20, 16, 9, 93, 1, 18, 53, 41, 14, 84, 74, 53, 1, 100, 78, 9, 5, 51, 82, 90, 64, 44, 24, 36, 19, 64, 40, 51, 96, 42, 5, 58, 54, 78, 42, 84, 16, 100, 49]
отсортированный список: [89, 94, 87, 3, 88, 98, 92, 39, 61, 65, 70, 20, 16, 9, 93, 1, 18, 53, 41, 14, 84, 74, 53, 1, 100, 78, 9, 5, 51, 82, 90, 64, 44, 24, 36, 19, 64, 40, 51, 96, 42, 5, 58, 54, 78, 42, 84, 16, 100, 49]

Подумайте, сколько сравнений будет совершенно в худшем случае.

Ваш ответ:

Посчитайте сколько сравнений совершает ваш алгоритм.

Ваш ответ:

3. Строки

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

s = 'hello'
s = "hello"

Рассмотрим базовые операции со строками:

1. Дублирование строки: print('hello' * 2)
2. Конкатенация строк: print('hello' + 'World')
3. Длина строки (функция len): len('hello')
4. Доступ по индексу: s[1]
5. Срезы строк: s[1:3]

Задача 6

Давайте поработаем со строками.

  1. Создайте строку.
  2. Продемонстрируйте дублирование строки, конкатенацию, доступ по индексу, срезы строк.
In [ ]:

Задача 7.

Напишите программу, которая определяет, является ли данное слово палиндромом, не используя reversed.

In [ ]:

С использованием reversed решение выглядит компактнее, но зато мы поработали со строками:)

In [14]:
s = input()
rev_s = reversed(s)
if list(s) == list(rev_s):
   print("Палиндромом")
else:
   print("Не палиндромом")

hello
Не палиндромом

4. Функции

Вспомним функции в Python. Функция - это именованный блок кода. Функция имеет имя, список аргументов и возвращаемое значение. Синтаксис функции представлен следующим образом:

def function_name(arg1, arg2, ...):
    # тело функции

Задача 8(Числа Фибоначчи).

Последовательность чисел Фибоначчи $F_{n}$ задаётся линейным рекуррентным соотношением: $F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$.

Напишите функцию fib, которая возвращает n-ное число Фибоначчи. Используейте цикл!

In [ ]:
def fib(n):
    # тело функции
    
    
n = int(input())
print(fib(10))

Теперь поговорим о рекурсии. С точки зрения функций рекурсия – это функция, которая сама вызывает себя. Рассмотрим классическую задачу нахождение факторила числа. С помощью рекурсии можно получить вполне компактный код.

In [15]:
def factorial_rec(n):
    if n == 1:
        return n
    else:
        return n*factorial_rec(n-1)

print(factorial_rec(5))

120

Кроме того, с помощью рекурсии можно вычислить n-ое число Фибоначчи.

Задача 9(Числа Фибоначчи).

Напишите функцию fib, которая возвращает n-ное число Фибоначчи. Используейте рекурсию!

In [5]:
def fib_rec(n):
    # код
print(fib_rec(10))

  File "C:\Users\79826\AppData\Local\Temp\ipykernel_11136\1798929870.py", line 5
    print(fib_rec(10))
    ^
IndentationError: expected an indented block

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

Задача 10(*)

Алгоритм сортировки слиянием:

  1. Сортируемый массив(список) разбивается на две части примерно одинакового размера.
  2. Каждая из получившихся частей сортируется отдельно, можно той же сортировкой.
  3. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы(или определённого выбранного значения)
  4. Два упорядоченных массива половинного размера соединяются в один отсортированный массив, также рекурсивным образом.

Рассмотрим пример. Пусть дан массив [5, 3, 8, 4, 1, 7, 2, 6].

  1. Разбиваем массив на два подмассива: [5, 3, 8, 4] и [1, 7, 2, 6]
  2. Каждый подмассив разбиваем на ещё два подмассива: [5, 3] и [8, 4] и [1, 7] и [2, 6]
  3. Повторяем процедуру ещё раз: [5] и [3] и [8] и [4] и [1] и [7] и [2] и [6]
  4. Соединяем наши подмассивы в отсортированные под массивы: [3, 5] и [4, 8] и [1, 7] и [2, 6]
  5. Продолжаем наши действия рекурсивно.

Реализуйте сортировку слиянием, используя рекурсию.

In [ ]:
from random import randint
n = 50
a = []
# создаём список из 50 элементов со случ. числами от 1 до 100.
for i in range(n):
    a.append(randint(1, 100))
print(a)
# ваша сортировка:

Подумайте, сколько сравнений будет совершенно в худшем случае.

Ваш ответ:

Посчитайте сколько сравнений совершает ваш алгоритм.

Ваш ответ:

Подумайте, сколько сравнений будет совершенно в лучшем случае.

Ваш ответ:

Сравните полученные результаты с сортировкой пузырьком

Функция map

Вспомним, что такое map в Python. Это функция, принимающая другую функцию и несколько итерируемых объектов (возможно и один объект) и применяет полученную функцию к элементам итерируемых объектов, возвращая объект map.

Объект map является итератором и содержит в себе результаты "неявно". Результаты можно "достать" из итератора, преобразовать его в коллекцию (list, set и т.д)

Рассмотрим простой пример работы с map:

In [17]:
# Создамим список, элементами которого являются строки
s = []
for i in range(1000000):
    s.append(str(i))
# Убедимся, что элементами списка являются переменные типа str
type(s[1])
Out[17]:
str
In [18]:
from time import time
# Чтобы создать список int из исходного списка достаточно написать:
now = time()
new_s = list(map(int, s))
print('map выполняется за:', time() - now)

map выполняется за: 19.74245047569275

Задача 11

Создайте список без использования map, а с использованием цикла. Расчитайте время выполнения операций. Сравните время с выполнением map.

In [ ]:

5. Множества и словари

Повторим несколько базовых вещей, связанных с множествами. Set — это коллекция уникальных объектов.

1. Создание множества : s = {1, 5, 9} или
2. Добавление элемента: s.add(new_element)
3. Добавление нескольких элементов: s.add((new_element1, new_element2))
4. Удаление элемента: s.remove(element)
In [7]:
# Объдинение множеств
set1 = {1, 2}
set2 = {3, 4}
print(set1.union(set2))

{1, 2, 3, 4}
In [9]:
# Разность множеств
set1 = {1, 2, 3, 4, 5, 6}
set2 = {3, 4, 5, 6, 7, 8}
print(set1.difference(set2))

{3, 4, 5, 6}
In [10]:
# Пересечение множеств
set1 = {1, 2, 3, 4, 5, 6}
set2 = {3, 4, 5, 6, 7, 8}
print(set1.intersection(set2))

{3, 4, 5, 6}
In [12]:
# Проверка вхождения элемента в множество
print(1 in set1)
print(10 in set1)

True
False

Задача 12

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

Подсказка: используйте len()

In [ ]:

Задача 13

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

In [ ]:

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

In [25]:
# Создадим словарь, содержащий название книги и её цену
dictionary = {'Book1': 100, 'Book2': 200, 'Book3' : 400, 'Book4': 50}
# Получим значеник конкретного ключа(цену книги, зная её название)
print("цена Book1 :", dictionary['Book1'])
# Добавим новую книгу и её цену
dictionary['Book5'] = 1000
# Удалим книгу с ценой 200
del dictionary['Book2']

цена Book1 : 100

Больше о методах словаря можно почитать здесь https://www.geeksforgeeks.org/python-dictionary-methods/.

Вспомнив базовые вещи, мы можем перейти к решению нескольких интересных задач.

Задача 14 (коэффициент Жаккара)

Пусть есть два множества A и B. Коэффициент Жаккара $ = \frac{c}{a + b - c}.$

  1. $c$ - количество элементов, общих для множества A и B
  2. $a$ и $b$ - количество элементов множества A и B соответственно

Т.е коэффициент Жаккара есть отношение пересечения множеств к их объединению.

In [31]:
l1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
l2 = [2, 2, 4, 5, 5, 6, 6, 8, 8, 0]
l3 = [2, 2, 8, 9, 4, 1, 5, 12, 13, 7]
l4 = [2, 0, 1, 7, 6, 6, 6, 8, 8, 8]
l5 = [0, 2, 5, 5, 5, 6, 5, 8, 8, 8]

Реализуйте функцию, вычисляющую коэффициент Жаккара между двумя множествами(списками). Какие из двух списков имеют максимальный коэффициент.

In [ ]:

Задача 15(Решето Эратосфена)

Решето Эратосфена – это алгоритм нахождения простых чисел до заданного натурального числа путем постепенного отсеивания составных чисел. Алгоритм заключается в следующем:

  1. Выписать подряд все целые числа от двух до n.
  2. Пусть переменная k изначально равна двум — первому простому числу.
  3. Зачеркнуть в списке числа от 2k до n, считая шагами по k (это будут числа, кратные k: 2k, 3k …).
  4. Найти первое незачёркнутое число в списке, большее чем k, и присвоить значению переменной k это число.
  5. Повторять шаги 3 и 4, пока возможно.

Все незачёркнутые числа в списке — это все простые числа от 2 до n.

Реализуйте Решето Эратосфена и найдите все простые числа до 10000 включительно.

In [ ]:

itertools

Импортируем библиотеку itertools.

Данный ниже код, как можно наблюдать, позволяет вывести всевозможные сочетания трёх элементов из 5-ти элементного множества(A, B, C, D, F).

In [2]:
import itertools as it
for x, y, z in it.permutations("ABCDF", 3):
    print(x, y, z, sep='', end=' ')

ABC ABD ABF ACB ACD ACF ADB ADC ADF AFB AFC AFD BAC BAD BAF BCA BCD BCF BDA BDC BDF BFA BFC BFD CAB CAD CAF CBA CBD CBF CDA CDB CDF CFA CFB CFD DAB DAC DAF DBA DBC DBF DCA DCB DCF DFA DFB DFC FAB FAC FAD FBA FBC FBD FCA FCB FCD FDA FDB FDC

Задача 16

Витя выбирает 3 предмета, которые он будет сдавать на ЕГЭ. Всего предметов 10. Сколько всего сочетаний предметов он может выбрать?

Решите задачу, используя it.permutation

In [ ]:

Рассмотрите пример с it.product. Проанализируйте его работу.

In [3]:
for x, y in it.product("123", "ABC"):
    print(x, y)

1 A
1 B
1 C
2 A
2 B
2 C
3 A
3 B
3 C

Задача 17

Два вектора представлены списками. Вычислите их скалярное произведение, используя it.product.

In [4]:
a = [1, 5, 3, 7, 8] # вектор 1
b = [2, 3, 2, 1, 0] # вектор 2
In [ ]: