Занятие 1 (часть 1)

Лабораторная работа 1 (часть 1)¶

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

Циклы и вложенные циклы.
Списки.
Строки.
Функции.
Множества(set), словари(dict).

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¶

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

Пусть даны два числа A и B.
Большее число делим на меньшее.
Если делится без остатка, то меньшее число это НОД.
Если есть остаток, то большее число заменяем на остаток от деления.
Переходим к пункту 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))

1.3 break и continue¶

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

break – досрочное завершение цикла
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. Списки¶

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

Основные характеристики списков¶

Упорядоченность: Элементы в списке имеют фиксированный порядок, и вы можете получить доступ к элементам по их индексу (начиная с 0).
Изменяемость: Списки можно изменять после их создания; вы можете добавлять, удалять, изменять элементы.
Разнотипность: Списки могут содержать элементы разных типов (например, строки, числа, другие списки и т. д.).

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

In [ ]:

# Создание пустого списка
empty_list = []
print(empty_list)

# Создание списка с элементами
my_list = [1, 2, 3, 'четыре', 5.0]
print(my_list)

In [ ]:

first_element = my_list[0]  # Получения первого элемента (1)
print(first_element)
last_element = my_list[-1]   # Получение последнего элемента (5.0)
print(last_element)

In [ ]:

# Изменение элементов списка, с присваиванием им новых значение:
my_list[3] = 'четыре (изменено)'  # Изменение 'четыре' на 'четыре (изменено)'
print(my_list[3])

2.1 Оператор in¶

В Python оператор in используется для проверки наличия элемента в списке (или в других итерируемых объектах, таких как строки, кортежи и множества). Этот оператор возвращает True, если элемент найден, и False, если нет. Вот как это работает на практике:

In [1]:

# Пример
numbers = [1, 2, 3, 4, 5]

if 3 in numbers:
    print("Число 3 есть в списке.")
else:
    print("Числа 3 нет в списке.")

Число 3 есть в списке.

2.2 Методы списка: index, count.¶

В Python списки имеют несколько встроенных методов, которые позволяют эффективно работать с данными. Два из этих методов, index() и count(), используются для поиска элементов в списке.

In [3]:

# Пример count
# Создаем список чисел
numbers = [1, 2, 2, 3, 2, 4]

# Подсчитываем количество вхождений числа 2
count_of_twos = numbers.count(2)
print(f"Количество двоек в списке: {count_of_twos}")  # Вывод: 3

# Подсчитываем количество вхождений числа 5
count_of_fives = numbers.count(5)
print(f"Количество пятерок в списке: {count_of_fives}")  # Вывод: 0

Количество двоек в списке: 3
Количество пятерок в списке: 0

In [4]:

# Пример метода index()
# Создаем список слов
fruits = ['яблоко', 'банан', 'вишня', 'банан', 'груша']

# Находим индекс первого вхождения 'банан'
index_of_banana = fruits.index('банан')
print(f"Индекс первого вхождения 'банан': {index_of_banana}")  # Вывод: 1

Индекс первого вхождения 'банан': 1

2.3 Изменяемость списка list в Python.¶

Списки в Python являются изменяемыми (mutable), что означает, что вы можете изменять их содержимое после создания. Это включает в себя добавление, изменение и удаление элементов. Рассмотрим три основных метода для добавления элементов в список: append(), extend() и insert().

Метод append() добавляет один элемент в конец списка.

Метод extend() добавляет все элементы из итерируемого объекта (например, другого списка) в конец списка.

Метод insert() вставляет элемент по указанному индексу. При этом все элементы, находящиеся справа от данного индекса, смещаются на одну позицию вправо.

In [5]:

# Создаем пустой список
# Пример использования метода append
fruits = []
fruits.append('яблоко')
fruits.append('банан')
print(fruits)  # Вывод: ['яблоко', 'банан']

# Пример использования метода extend
more_fruits = ['вишня', 'апельсин']
fruits.extend(more_fruits)
print(fruits)  # Вывод: ['яблоко', 'банан', 'вишня', 'апельсин']

# Пример использования метода insert
fruits.insert(1, 'киви')
print(fruits)  # Вывод: ['яблоко', 'киви', 'банан', 'вишня', 'апельсин']

['яблоко', 'банан']
['яблоко', 'банан', 'вишня', 'апельсин']
['яблоко', 'киви', 'банан', 'вишня', 'апельсин']

2.4 Удаление из списка¶

В Python для удаления элементов из списка можно использовать оператор del, а также методы pop() и remove(). Каждый из этих способов имеет свои особенности и области применения. Давайте рассмотрим их детально.

Оператор del используется для удаления элемента по индексу или для удаления всего списка. Если вы используете del для удаления элемента, все элементы, находящиеся справа от данного индекса, смещаются влево.

Метод pop() удаляет элемент по указанному индексу и возвращает его. Если индекс не указан, удаляется последний элемент списка. Это удобно, если вам нужно как удалить элемент, так и получить его значение.

Метод remove() удаляет первое вхождение указанного элемента. Если элемент не найден, будет вызвано исключение ValueError. Это полезно, если вам нужно удалить элемент по его значению, а не по индексу.

In [6]:

fruits = ['яблоко', 'банан', 'вишня', 'груша']

# Удаляем элемент с индексом 1 ('банан')
del fruits[1]
print(fruits)  # Вывод: ['яблоко', 'вишня', 'груша']

# Пример использования pop
last_fruit = fruits.pop()
print(f"Удаленный фрукт: {last_fruit}")  # Вывод: 'груша'
print(fruits)  # Вывод: ['яблоко', 'банан']

# Удаляем элемент с индексом 1 ('банан')
banana = fruits.pop(1)
print(f"Удаленный фрукт: {banana}")  # Вывод: 'банан'
print(fruits)  # Вывод: ['яблоко']

# Пример использования remove
fruits = ['яблоко', 'банан', 'вишня', 'банан']

fruits.remove('банан')
print(fruits)  # Вывод: ['яблоко', 'вишня', 'банан']

try:
    fruits.remove('апельсин')  # Элемент не существует
except ValueError:
    print("Элемент 'апельсин' не найден в списке.")  # Вывод: Элемент 'апельсин' не найден в списке.

['яблоко', 'вишня', 'груша']
Удаленный фрукт: груша
['яблоко', 'вишня']
Удаленный фрукт: вишня
['яблоко']
['яблоко', 'вишня', 'банан']
Элемент 'апельсин' не найден в списке.

Задача 4¶

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

Создайте список
Продемонстрируйте доступ к элементу, срезы, добавление новых элементов, удаление элементов, подсчёт значение.
Отсортируйте список методом 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 строки являются объектами и предлагают множество встроенных методов для обработки текста. Рассмотрим несколько распространенных методов строк, таких как lower, upper, replace и join. Это полезные инструменты для работы с текстовыми данными.

Методы строк:¶

lower(): Приводит все символы строки к нижнему регистру.
upper(): Приводит все символы строки к верхнему регистру.
replace(old, new): Заменяет подстроку old на new во всей строке.
join(iterable): Объединяет элементы итерируемого объекта (например, список строк) в одну строку с использованием строки, на которой был вызван метод, в качестве разделителя.

In [7]:

# Исходная строка
text = "Hello, World! Welcome to Python."

# Приведение строки к нижнему регистру
lowered_text = text.lower()
print("Нижний регистр:", lowered_text)

# Приведение строки к верхнему регистру
uppered_text = text.upper()
print("Верхний регистр:", uppered_text)

# Замена подстроки
replaced_text = text.replace("World", "Universe")
print("После замены:", replaced_text)

# Создание списка строк
words = ['Hello', 'World', 'this', 'is', 'Python']

# Объединение списка строк в одну строку с пробелом в качестве разделителя
joined_string = " ".join(words)
print("Объединенная строка:", joined_string)

Нижний регистр: hello, world! welcome to python.
Верхний регистр: HELLO, WORLD! WELCOME TO PYTHON.
После замены: Hello, Universe! Welcome to Python.
Объединенная строка: Hello World this is Python

Задача 6¶

Напишите программу, которая удаляет все запятые из строки
Напишите программу, которая возвращает число буква b в строке.

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))

Кроме того, с помощью рекурсии можно вычислить 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(*)¶

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

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

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

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

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

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}.$

$c$ - количество элементов, общих для множества A и B
$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(Решето Эратосфена)¶

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

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

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

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

In [ ]:

Задача 16 (Частотный анализ)¶

Частотный анализ — это метод, позволяющий выявить, как часто встречаются различные значения в наборе данных. Он может быть визуализирован с помощью гистограмм, которые позволяют легко видеть распределение значений. В Python для выполнения частотного анализа можно использовать списки (массивы), а для визуализации – библиотеку matplotlib.

Задача¶

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

Для этого необходимо сделать следующие шаги:

Подготовка строки:

Строка приводится к нижнему регистру, и пробелы удаляются.

Создание массива для частоты:

Используем массив frequencies длиной 26 для хранения частот букв. Индекс 0 соответствует букве 'a', 1 — букве 'b' и так далее.

Подсчет частоты:

Проходим по каждому символу в строке. Если символ является буквой (проверка через диапазон ASCII), увеличиваем соответствующий индекс в массиве.

Построение гистограммы:

Используем matplotlib для создания гистограммы, где на оси X будут буквы, а на оси Y — их частота.

Вывод результата:

Выводим частоту каждой буквы, которая встречается в строке.

In [ ]:

s = input() # ваше слово

#letters = ... буква 
#frequencies = ... число данной буквы в слове

# Создание списка букв для оси X
letters = [chr(i) for i in range(ord('a'), ord('z') + 1)]

# Построение гистограммы
plt.bar(letters, frequencies)
plt.xlabel('Буквы')
plt.ylabel('Частота')
plt.title('Гистограмма частоты букв')
plt.xticks(rotation=45)
plt.tight_layout()  # Для предотвращения наложения меток
plt.show()

# Вывод частот
for letter, freq in zip(letters, frequencies):
    if freq > 0:
        print(f"Буква '{letter}': {freq}")