Как написать алгоритм на питоне

2017-2018 Алгоритмы и структуры данных на Python 3, all playlist

• Youtube channel Тимофей Хирьянов

• Материалы курса находятся на сайте

• https://www.python.org/

• https://pythonworld.ru/

Оглавление

• Лекция №1. Введение, базовый синтаксис Python. Концепция присваивания. Арифметические операции. Цикл while and for. range(). continue and break.
• Лекция №2. Алгебра Логики. Законы де Моргана. Тип bool. Конструкция else + if = elif
• Лекция №3. Системы счисления. Литералы чисел. Разложение числа на цифры. Однопроходные алгоритмы без реализации.
• Лекция №4. Функции. Декомпозиция задачи. Структурное программирование. Стек. Полиморфизм в Python. Duck typing. Параметры
• Лекция №5. Массивы. Список. Линейный поиск. Копирование. Сдвиг. Добавление элемента. Удаление элемента. Ссылочная модель. Решето Эратосфена.
• Лекция №6. Методы append(), pop() и функция len() для списка. Списковые включения. Cортировки.
• Лекция №7. Рекурсия. Прямой и обратный ход рекурсии. Факториал. Алгоритм Евклида. Ханойские башни.
• Лекция №8. Генерация комбинаторных объектов. Рекурсивная генерация всех чисел длины M. Генерация всех перестановок (рекурсивная). Быстрые или Рекуррентные сортировки: Тони Хоара и слиянием (без реализации).
• Лекция №9. Быстрая сортировка Тони Хоара и Сортировка слиянием (реализация). Слияние двух упорядоченных массивов. Устойчивость сортировок. Проверка упорядоченности массива за O(N).
• Лекция №10. Вычисление чисел Фибоначчи и проблема перевычислений. Одномерное динамическое программирование на примере чисел Фибоначчи. Задачи о кузнечике (количество траекторий, траектория наименьшей стоимости). Двумерные массивы (списки списков). Оператор is.
• Лекция №11. Двумерное динамическое программирование. Наибольшая общая подпоследовательность. Наибольшая возрастающая подпоследовательность.
• Лекция №12. Расстояние Левенштейна. Проверка равенства строк. Наивный поиск подстроки в строке. Алгоритм Кнута-Морриса-Пратта
• Лекция №13. Стек. Автоматическое тестирование функций модуля (библиотека doctest). Проверка корректности скобочной последовательности. Обратная Польская нотация
• Лекция №14. Тип list. Изменяемость списка. Тип кортежа tuple как замороженный список. Насколько не изменяем кортеж?. Список кортежей и цикл for с двумя переменными. Тип строк str. Неизменяемость строки. Методы строки find, count, replace. Срезы строк и списков. Присваивание в срез списка. Стандартные функции len, max, min, sum. Методы split и join. Структура данных Куча/Пирамида (Heap)
• Лекция №16. Асимптотика алгоритмов (потребление ресурсов) . Индуктивные функции. Однопроходные алгоритмы. NP- полные задачи. Тест простоты Ферма. Числа Кармайкла. Алгоритм шифрования RSA
• Лекция №17. Рекурсия и динамическое программирование. Факториал рекурсивно и динамически. Числа Фибоначчи рекурсивно, рекурсивно с кешированием и динамически. Задача о рюкзаке рекурсивно и динамически
• Лекция №18. ООП, Классы, Объекты, Именованный кортеж, Связный список
• Лекция №19. Дерево, Куча (Heap), алгоритм сортировка HeapSort
• Лекция №20. Хеш-таблица
• Лекция №21. Множества / set, Словари / dict
• Лекция №22. Графы
• Лекция №23. Варианты хранения Графа в памяти. Web программирование
• Лекция №24. Обход графа в глубину (DFS). Выделение и подсчёт компонент связности. Проверка графа на двудольность. Выделение компонент сильной связности орграфа алгоритмом Косарайю. Топологическая сортировка через алгоритм Тарьяна.
• Лекция №25. Взвешенный граф. Обход графа в ширину.Очередь при обходе в ширину и её асимптотика. Выделение компонент связности (обходом в ширину). Нахождение кратчайшего цикла в невзвешенном графе.
• Лекция №26. Графы, кратчайший путь, Алгоритм Дейкстры с очередью. Алгоритмы Флойда-Уоршелла.
• Лекция №27. Двоичные деревья поиска. Асимптотика основных операций. Балансировка деревьев. Малый левый и правый повороты. Большой левый и правый повороты.
• Лекция №28. Цикл Эйлера и цикл Гамильтона. Жадный алгоритм Дейкстры.

К оглавлению

Лекция №1. Введение, базовый синтаксис Python. Концепция присваивания. Арифметические операции. Цикл while and for. range(). continue and break.

Программирование включает, по степени важности:

1. Алгоритмы и структуры данных
2. Практика программирования
3. Дизайн ПО (архитектура приложения)
4. Синтаксис языка программирования
5. Прикладные библиотеки
6. Групповая разработка, коммуникация

«Код читается намного больше раз, чем пишется» @Гвидо ван Россум

My version:

flyboroda@MacBook-Air-Artem ~ % python3
Python 3.8.9 (default, Feb 18 2022, 07:45:33) 
[Clang 13.1.6 (clang-1316.0.21.2)] on darwin

x = "Hello, World"
print(x)
print(type(x)) # узнаем какой тип у имени х
x = 1 + 2 + 3

Переменных нет, есть имена, х это имя, ссылающееся на строковое значение в памяти «Hello, World». Х это именнованная ссылка на значение «Hello, World». Оператор присваивания = в Python это ссылка. Есть сборщик мусора который сразу же убирает не именованные или безхозные объекты из памяти. В Питоне х не привязан к конкретной области памяти. Далее х привязывается к новому числовому значению равному 6, и теряет связь с «Hello, World».

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

hypot.py

a = 179
b = 197
c = (a ** 2 + b ** 2) ** 0.5
print (c)

Здесь мы используем переменные — объекты, в которых можно сохранять различные (числовые, строковые и прочие) значения. В первой строке переменной a присваивается значение 179, затем переменной b присваивается значение 97, затем переменной c присваивается значение арифметического выражения, равного длине гипотенузы. После этого значение переменной c выводится на экран.

flyboroda@MacBook-Air-Artem examples % touch hypot.py
flyboroda@MacBook-Air-Artem examples % open hypot.py
flyboroda@MacBook-Air-Artem examples % python3 hypot.py
266.1766330841233

Типы данных

Числа записываются последовательностью цифр, также перед числом может стоять знак минус, а строки записываются в одинарных кавычках. 2 и ‘2’ — это разные объекты, первый объект — число, а второй — строка. Операция + для целых чисел и для строк работает по-разному: для чисел это сложение, а для строк — конкатенация.

Кроме целых чисел есть и другой класс чисел: действительные (вещественные числа), представляемые в виде десятичных дробей. Они записываются с использованием десятичной точки, например, 2.0.

Определить тип объекта можно при помощи функции type:

>>> type(2)
<class 'int'>
>>> type('2')
<class 'str'>
>>> type(2.0)
<class 'float'>

Обратите внимание — type является функцией, аргументы функции указываются в скобках после ее имени.

Операции с числами

Вот список основных операций для чисел:

A + B — сумма;

A - B — разность;

A * B — произведение;

A / B — частное;

A ** B — возведение в степень, двойное умножение, работает не только с целыми числами

Полезно помнить, что квадратный корень из числа x — это x ** 0.5, а корень степени n — это x ** (1 / n).
Например корень из 3 это 3**0.5

Есть также унарный вариант операции -, то есть операция с одним аргументом. Она возвращает число, противоположное данному. Например: -A.

В выражении может встречаться много операций подряд. Как в этом случае определяется порядок действий? Например, чему будет равно 1+2*3**1+1? В данном случае ответ будет 8, так как сначала выполняется возведение в степень, затем — умножение, затем — сложение.

a += 1
a = a + 1

a -= 1
a = a - 1

a /= 1
a = a / 1

a // = 1 # с отбрасыванием остатка
a = a // 1

a %= 1 # интересует остаток, по модулю
a = a % 1

a *= 1
a = a * 1

Правила определения приоритетов операций такие:

1. Выполняются возведения в степень справа налево, то есть 3**3**3 это 3²⁷ (7625597484987).

2. Выполняются унарные минусы (отрицания) -x.

3. Выполняются умножения и деления слева направо. Операции умножения и деления имеют одинаковый приоритет.

# деление с отбрасыванием остатка
x = 16
y = 3
z = x // y
print(z)  # будет 5 и остаток 1 отбрасываем

# если интересует остаток, то
x = 16
y = 3
z = x % y
print(z) # 1

x = -12
y = 5
z = x // y
s = x % y
print(z) # - 3
print(s) # 3

x = -11
y = 10
z = x // y
s = x % y
print(z) # -2
print(s) # 9

1. Выполняются сложения и вычитания слева направо. Операции сложения и вычитания имеют одинаковый приоритет.

Операции над строками

A + B — конкатенация;

A * n — повторение n раз, значение n должно быть целого типа.

Каскадное (трамвайное) присваивание

Множественное присваивание (кортеж)

Обмен значений двух переменных через третью.

a = 1
b = 2

tmp = a
a = b
b = tmp

Обмен значений двух переменных через две дополнительных.

a = 1
b = 2

tmp1 = b
tmp2 = a
a = tmp1
b = tmp2

Можно применить множественное присвание (ниже), и сократить код. Это обмен через временный кортеж с 2 дополнительными переменными (кортеж это множественное присваивание x, y = 1, 2, кортеж — пачка имен и присваиваемых значений). Как только выражение вычислится, кортеж исчезнет. Кортеж представляет из себя ссылки на числовые объекты, сами объекты не копируются.

a = 1
b = 2

tmp1, tmp2 = b, a
a, b = tmt1, tmp2

# или еще лучше
a, b = b, a

Присваивание в Python, это связывание имени и объекта.
a = 5 -> a += 1 -> a = 6, a — имя, число — объект.

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

Ветвление

Ветвление (или условная инструкция) в Python имеет следующий синтаксис:

if Условие:
    Блок_инструкций_1
else:
    Блок_инструкций_2

Блок_инструкций_1 будет выполнен, если Условие истинно. Если Условие ложно, будет выполнен Блок_инструкций_2.

В условной инструкции может отсутствовать слово else и последующий блок. Такая инструкция называется неполным ветвлением. Например, если дано число x и мы хотим заменить его на абсолютную величину x, то это можно сделать следующим образом:

if x < 0:
    x = -x
print(x)

В этом примере переменной x будет присвоено значение -x, но только в том случае, когда x<0. А вот инструкция print(x) будет выполнена всегда, независимо от проверяемого условия.

Для выделения блока инструкций, относящихся к инструкции if или else в языке Python используются отступы. Все инструкции, которые относятся к одному блоку, должны иметь равную величину отступа, то есть одинаковое число пробелов в начале строки. Рекомендуется использовать отступ в 4 пробела.

Вложенные условные инструкции

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

Пример программы, которая по данным ненулевым числам x и y определяет, в какой из четвертей координатной плоскости находится точка (x,y):

x = int(input()) — считываем введенное значение с клавиатуры, оно будет строковым, прообразуем в число, и присваиваем его значение имени х

x = int(input())
y = int(input())
if x > 0:
    if y > 0:               # x>0, y>0
        print("Первая четверть")
    else:                   # x>0, y<0
        print("Четвертая четверть")
else:
    if y > 0:               # x<0, y>0
        print("Вторая четверть")
    else:                   # x<0, y<0
        print("Третья четверть")

Комментариями в Pythonе является символ #.

Операторы сравнения

Как правило, в качестве проверяемого условия используется результат вычисления одного из следующих операторов сравнения:

<	   Меньше — условие верно, если первый операнд меньше второго.
>	   Больше — условие верно, если первый операнд больше второго.
<=	 Меньше или равно — условие верно, если первый операнд меньше или равен второму.
>=	 Больше или равно — условие верно, если первый операнд больше или равен второму.
==	 Равенство. Условие верно, если два операнда равны.

Например, условие (x * x < 1000) означает «значение x * x меньше 1000», а условие (2 * x != y) означает «удвоенное значение переменной x не равно значению переменной y».

Операторы сравнения можно объединять в цепочки, например, a == b == c или 1 <= x <= 10.

Тип данных bool

Значения логического типа могут принимать одно из двух значений: True (истина) или False (ложь). Если преобразовать логическое True к типу int, то получится 1, а преобразование False даст 0. При обратном преобразовании число 0 преобразуется в False, а любое ненулевое число в True. При преобразовании str в bool пустая строка преобразовывается в False, а любая непустая строка в True.

Каскадные условные инструкции

Пример программы, определяющий четверть координатной плоскости, можно переписать используя «каскадную« последовательность операцией if... elif... else:

x = int(input())
y = int(input())
if x > 0 and y > 0:
    print("Первая четверть")
elif x > 0 and y < 0:
    print("Четвертая четверть")
    # если x<0, y>0, то
elif y > 0:
    print("Вторая четверть")
    # если x<0, y<0, то
else:
    print("Третья четверть")

В такой конструкции условия if, ..., elif проверяются по очереди, выполняется блок, соответствующий первому из истинных условий. Если все проверяемые условия ложны, то выполняется блок else, если он присутствует.

Цикл while («пока»)

Позволяет выполнить одну и ту же последовательность действий, пока проверяемое условие истинно. Условие записывается до тела цикла и проверяется до выполнения тела цикла. Как правило, цикл while используется, когда невозможно определить точное значение количества проходов исполнения цикла.

Синтаксис цикла while в простейшем случае выглядит так:

while Условие:
    Блок_инструкций

При выполнении цикла while сначала проверяется условие. Если оно ложно, то выполнение цикла прекращается и управление передается на следующую инструкцию после тела цикла while. Если условие истинно, то выполняется инструкция, после чего условие проверяется снова и снова выполняется инструкция. Так продолжается до тех пор, пока условие будет истинно. Как только условие станет ложно, работа цикла завершится и управление передастся следующей инструкции после цикла.

Например, следующий фрагмент программы напечатает на экран всех целые числа, не превосходящие n:

a = 1
while a <= n:
    print(a)
    a += 1

Общая схема цикла while в данном случае для перебора всех подходящих значений такая:

a = начальное_значение
while а_является_подходящим_числом:
    обработать_a
    перейти_к_следующему_a

Выводем все степени двойки, не превосходящие числа n:

a = 1
while a <= n:
    print(a)
    a *= 2

Цикл for

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

Нужен чтобы пробегать какой-то диапозон арифметической прогрессии.

Более краткая альтернатива циклу while.

Для последовательного перебора целых чисел из диапазона [0; n) можно использовать цикл for:

for i in range(10):
   print(i)

Этот код по выполняемым действиям полностью соответствуют циклу while:

i = 0
while i < 10:
  print(i)
  i += 1

Итерация — это однократное выполнение тела цикла.

Можно задавать начальные и конечные значения для переменной цикла, а также шаг (последнее значение):

for i in range(20, 10, -2):
  print(i)

Result: 20 18 16 14 12

Универсальный генератор арифметической прогрессии, range(start, stop, step), значение stop не включается, значение на позиции start всегда включается, [start, stop)

range(5) — диапозон, старт будет с 0, шаг 1, до 5
range(5, 10) — диапозон от и до
range(5, 10, 2) — диапозон от и до, с шагом

for i in range(5):
   print(i)

Result: 1, 2, 3, 4, 5

for x in range(5, 0, -1):
  print(x ** 2)

Result: 25 16 9 4 1

Цикл for имеет работать с двумя переменными:

A = [(1, "A"), (2, "B"), (3, "C")]
for x,y in A:
    print(y,x)

или тоже самое только с помощью enumerate которое пронумерует строку

A = enumerate("ABC")
for x,y in A:
    print(y,x)

Аналогичный цикл while

i = 20
while i > 10:
  print(i)
  i -= 2

break

Экстренный выход из цикла, перепрыгивание на следующую инструкцию программы минуя else if и тп, аналогия «пожар». Чаще всего используется с проверкой условия if что-то там, то break.

continue
Телепортация сразу на следующую итерацию. С середины тела цикла, могу снова попасть, телепортироваться на следующую новую итерацию.

Черепаха

Стандартная библиотека Python содержит модуль turtle, предназначенный для обучения программированию. Этот модуль содержит набор функций, позволяющих управлять черепахой. Черепаха умеет выполнять небольшой набор команд, а именно:

Команда Значение

forward(X)	# Пройти вперёд X пикселей
backward(X)	# Пройти назад X пикселей
left(X)		# Повернуться налево на X градусов
right(X)	# Повернуться направо на X градусов
penup()		# Не оставлять след при движении
pendown()	# Оставлять след при движении
shape(X)	# Изменить значок черепахи (“arrow”, “turtle”, “circle”, “square”, “triangle”, “classic”)
stamp()		# Нарисовать копию черепахи в текущем месте
color()		# Установить цвет
begin_fill()	# Необходимо вызвать перед рисованием фигуры, которую надо закрасить
end_fill()	# Вызвать после окончания рисования фигуры
width()		# Установить толщину линии
goto(x, y)	# Переместить черепашку в точку (x, y)

Практика: Черепаха

IDE repl.it

Рисуем букву S

import turtle

turtle.shape('turtle')
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.right(90)
turtle.forward(50)
turtle.right(90)
turtle.forward(50)

Рисуем круг

import turtle

# Create a turtle
turtle.speed(10)
turtle.width(10)
turtle.color("red")

# Draw a circle starting at (x, y)
radius = 100
turtle.circle(radius)

# Make it all work properly
turtle.done()

Рисуем вложенные квадраты, один в другой с уменьшением шага

import turtle
 
a = int(input())  # сторона квадрата
turtle.shape('turtle')
while a > 1:
    turtle.pendown()
    for i in range(4):
        turtle.forward(a * 10)
        turtle.right(90)
    turtle.penup()
    turtle.forward(10)
    turtle.right(90)
    turtle.forward(10)
    turtle.left(90)
    a -= 1
input()

Рисуем паука, с заданным количеством лап

import turtle

a = int(input())  # количество лап паука
turtle.shape('turtle')
for i in range(a):
    turtle.forward(100)
    turtle.backward(100)
    turtle.right(360 / a)
input()

Рисуем спираль

Нужно подключить модуль math

from math import pi, sin, cos
import turtle

turtle.shape('turtle')
for i in range(200):
    t = i / 10 * pi
    dx = t * cos(t)
    dy = t * sin(t)
    turtle.goto(dx, dy)

or

import turtle

turtle.shape('turtle')
x = 0.5
for i in range(20):
    for j in range(30):
        turtle.forward(x)
        turtle.left(6)
    x += 0.5

Рисуем квадратную спираль

import turtle

turtle.shape('turtle')
x = 15
for i in range(20):
    for j in range(30):
        turtle.forward(x)
        turtle.left(90)
        x += 5

Написание функции

Как было сказано раньше, функции — это своего рода готовые кирпичики, из которых строится программа. До этого момента мы использовали стандартные функции (print, input, функции модуля turtle), теперь настало время написать функцию:

>>> def hello(name):
...     print('Hello, ', name, '!')
...
>>> hello('world')

Hello, world!

Это простейший пример функции, которая принимает в качестве параметра имя, а затем выводит на экран сообщение Hello, <имя>. Как видно из примера, функции в языке Python описываются при помощи ключевого слова def:

def Имя_функции(параметр_1, параметр_2, ...):
    Блок_операций

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

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

hello('world')

Внутри функции можно использовать те же синтаксические конструкции, что и вне её — циклы, ветвления, можно даже описывать новые функции. Естественно, внутри функции можно работать и с переменными.

Написанная ранее функция имеет особенность — она просто выводит текст на экран и не возвращает никакого результата. Многие функции, напротив, занимаются вычислением какого-либо значения, а затем возвращают его тому, кто эту функцию вызвал. В качестве примера можно рассмотреть функцию для сложения двух чисел:

>>> def sum(a, b):
...     return a + b
...
>>> sum(1, 2)
3
>>> sum(5, -7)
-2

Для возврата значения из функции используется оператор return: в качестве параметра указывается значение, которое требуется вернуть.

Рисуем 10 вложенных правильных многоугольников. Используйте функцию, рисующую правильный n-угольник.
Формулы для нахождения радиуса описанной окружности.

import turtle
import math
turtle.shape('turtle')
n = 3
r = 10 #задаем радиус первой окружности
def more_agles(n, m): #опеределяем функцию, рисующую многоугольник
    q = 360 / n
    while n > 0:
        
        turtle.left(q)
        turtle.forward(m)
        n -= 1
        
while n < 13:
    m = 2 * r * math.sin(math.pi / n) #считаем размер стороны многоугольника по формуле "Площадь правильного многоугольника вписанного в окружность"(a=2Rsin (360/2n))
    x = (180 - 360 / n ) / 2
    turtle.left(x)
    
    more_agles(n,m)
    turtle.right(x)
    turtle.penup()
    turtle.forward(10)# задаем расстояние между окружностями
    
    turtle.pendown()
    n += 1
    r += 10 #раз расстояние между окружностями 10, увеличиваем радиус на 10

Рисуем простой цветок

import turtle

my_turtle = turtle.Turtle()
for i in range(6):
    my_turtle.circle(50)
    my_turtle.right(60)

Рисуем бабочку

import turtle

radius = 20
turtle.left(90)

for i in range(5):
  turtle.circle(radius)
  turtle.circle(-radius)
  radius += 10

Рисуем пружину

import turtle
turtle.shape('turtle')
turtle.speed(3)
turtle.penup()
# отодвинем черепашку назад, чтобы поместилась пружина
turtle.setx(-450)
turtle.pendown()

for _ in range(4):
    # Повернуть черепашку под углом to_angle к вертикали (0 — наверх, 90 — направо);
    turtle.setheading(90)
    turtle.circle(-100, 180)
    turtle.circle(-20, 180)
turtle.circle(-100, 180)
turtle.done()

Рисуем смайлик

import turtle
lion=turtle.Turtle()
lion.up()
lion.goto(0, -100)  
lion.down()

lion.begin_fill()
lion.fillcolor("yellow")  
lion.circle(100)
lion.end_fill()

lion.up()
lion.goto(-67, -40)
lion.setheading(-60)
lion.width(5)
lion.down()
lion.circle(80, 120)    
lion.fillcolor("black")

for i in range(-35, 105, 70):
    lion.up()
    lion.goto(i, 35)
    lion.setheading(0)
    lion.down()
    lion.begin_fill()
    lion.circle(10)   
    lion.end_fill()
    
lion.hideturtle()

Рисуем звезду

import turtle
turtle.pensize(5)
turtle.pencolor("red")
turtle.forward(200)
for i in range(4):
    turtle.right(144)
    turtle.fd(200)
turtle.done()

Рисуем 11-ти конечную звезду

from turtle import *
t = Turtle()
for i in range(11):
# угол - 180-180/11 градусов
    t.right(180-180/11)
    t.fd(200)

К оглавлению

Лекция №2. Алгебра Логики. Законы де Моргана. Тип bool. Конструкция `else + if = elif

Любая функция — это отображение множества на множество, область определения и множество значений.

Законы алгебры логики

Законы де Моргана — логические правила, связывающие пары логических операций при помощи логического отрицания. В краткой форме звучат так:

Отрицание конъюнкции есть дизъюнкция отрицаний.

Отрицание дизъюнкции есть конъюнкция отрицаний.

== — оператор сравнения двух значений

В Питоне если нужно перенести строку с выражением используем скобки (…..), так как он очень внимателен к переносам и требует сдвига, иначе будет ошибка выражения.

Python: Конструкция else + if = elif

Это способ задать несколько альтернативных условий.

Функция get_type_of_sentence() из предыдущего урока различает только вопросительные и обычные предложения. Давайте попробуем добавить поддержку восклицательных предложений:

def get_type_of_sentence(sentence):
    last_char = sentence[-1]

    if last_char == '?':
        sentence_type = 'question'

    if last_char == '!':
        sentence_type = 'exclamation'
    else:
        sentence_type = 'normal'

    return 'Sentence is ' + sentence_type

print(get_type_of_sentence('Who?'))  # => 'Sentence is normal'
print(get_type_of_sentence('No'))    # => 'Sentence is normal'
print(get_type_of_sentence('No!'))   # => 'Sentence is exclamation'

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

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

Ветка else описана именно для второго условия, но не для первого (именно поэтому вопросительное предложение становится «normal»).

Для исправления ситуации воспользуемся ещё одной возможностью условной конструкции:

def get_type_of_sentence(sentence):
    last_char = sentence[-1]

    if last_char == '?':
        sentence_type = 'question'
    elif last_char == '!':
        sentence_type = 'exclamation'
    else:
        sentence_type = 'normal'

    return 'Sentence is ' + sentence_type

print(get_type_of_sentence('Who?'))  # => 'Sentence is question'
print(get_type_of_sentence('No'))    # => 'Sentence is normal'
print(get_type_of_sentence('No!'))   # => 'Sentence is exclamation'

Теперь все условия выстроены в единую конструкцию. elif — это «если не выполнено предыдущее условие, но выполнено текущее». Получается такая схема:

• если последняя буква ?, то ‘question’

• иначе, если последняя буква !, то ‘exclamation’

• иначе ‘normal’

Выполнится только один из блоков кода, относящихся ко всей конструкции if.

Конструкция с несколькими elif может также служить отличной заменой конструкции switch - case

a = int(input())
if a < -5:
    print('Low')
elif -5 <= a <= 5:
    print('Mid')
else:
    print('High')

К оглавлению

Лекция №3. Системы счисления. Литералы чисел. Разложение числа на цифры. Однопроходные алгоритмы без реализации.

Бит — двоичный разряд
8 бит = 1 байт

base = 7 # можно любое
x = int(input())
while x > 0 :
  digit = x % base
  print(digit)
  x //= base

К оглавлению

Лекция №4. Функции. Декомпозиция задачи. Структурное программирование. Стек. Полиморфизм в Python. Duck typing. Параметры

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

Имя должно отражать содержание того, что делает функция.

def hello():
	print("hello, world")
	
hello()
f = hello # без скобок, и f становится ссылкой на функцию hello
f()

Result:
hello, world
hello, world

def hello(name):
	print("hello, ", name)
	
hello("Artem")
f = hello("Artem")

Result:
hello,  Artem
hello,  Artem

Можно задать параметр по умолчанию

def hello(name = "world"): 
	print("hello, ", name)
hello("Artem")
f = hello("Artem")
hello()

Result:
hello,  Artem
hello,  Artem
hello,  world

def max3(x, y):
  if x > y:
    return x
  return y
	
z = maxTwo(5, 6)
print(z)

def max2(x, y):
  if x > y:
    return x
  return y
	
def max3(x, y, z):
  return max2(x, max2(y,z))

number = max3(5,6,7)
print(number)

Duck typing — «если это похоже на утку и крякает как утка, то это утка». Утиный полифорфизм, утиная типизация. Любое нечто которое можно сравнивать друг с другом, допустимо для аргументов этой функции

def max2(x, y):
  if x > y:
    return x
  return y
	
def max3(x, y, z):
  return max2(x, max2(y,z))

number = max3(5,6,7)
print(number)
print(max3(5.1, 5.2, 5.3))
print(max3("a", "ab", "abc"))
print(max3("cat", "cot", "cit"))

Именованные параметры

def hello_separator(name = "World", separator = "***"):
	print("Hello", name, sep = separator)
hello_separator()
hello_separator(separator = "---")
hello_separator(separator = "+++", name = "John")

Result:
Hello***World
Hello---World
Hello+++John

Структурное программирование

Проектирование «сверху -> вниз». В последовательности разработки, в ее проектировании, заключается и вся фишка.

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

От главной функции мы итеративно идем к более метким функциям, как от задачи к подзадачам для достижения цели. Этих мелких функций выполняющих какие-то более мелкие задачи может и не быть еще, но самое важное в том, что мы изначально правильно выстраиваем ход разработки программы, понимаем что нам нужно и какой опционал нам понадобится. Мы придумываем функции и пишем их, они еще не работают, но у нас в замыслах они уже выполняются, т.е делаем набросок проекта.

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

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

Так итеративно идем от версии к версии. В каждой версии (ее реализации) программа работает. Вначале пути программа расширяется, затем решая более мелкие подзадачи она уменьшается до задуманной цели.

Функции нужно называть так, чтобы имя отражало ее содержание. Что она делает?

Метод грубой силы (Brute force)

Есть область определения и множество значений, и алгоритм состоит в том, чтобы по исходным данным найти ответ.

Если метод предполагает перебор всех ответов, то это метод грубой силы

Строковые литералы могут занимать несколько строк. тройные кавычки: """...""" или '''...'''
Это многострочная документ строка.

print("""
Usage: thingy [OPTIONS]
	same text
	sate text
""")

def is_simple_number(x):
  """ Определяет, является ли число простым.
      х - целое положительное число.
      Если простое, то возвращает True,
      а иначе - False
  """
  divisor = 2
  while divisor < x:
    if x % divisor == 0:
      return print("False")
    divisor += 1
  return print("True")
print(is_simple_number(8))
help(is_simple_number) # вызов документа-строки

Result: False

Help on function is_simple_number in module __main__:

is_simple_number(x)
    Определяет, является ли число простым.
    х - целое положительное числ�.
    Если простое, то возвращает True,
    а иначе - False

К оглавлению

Лекция №5. Массивы. Список. Линейный поиск. Копирование. Сдвиг. Добавление элемента. Удаление элемента. Ссылочная модель. Решето Эратосфена.

Массив (Тип list). Это контейнер для хранения данных. Есть имя и внутри контейнера содержатся данные (объекты), все они имеют одинаковый тип.

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

a = [1, 2, 3, 4]
for i in a:
	print(i, type(i)) # type i int
print(type(a)) # type a list

1 <class 'int'>
2 <class 'int'>
3 <class 'int'>
4 <class 'int'>
<class 'list'>

Модель данных в Pythone

Есть изменяемые и неизменяемые типы данных(объекты).

a = [1, 2, 3, 4]
for i in a:
	print(i) # type i int
	i += 1
	print(i)

print(a)

1
2 # i += 1
2
3 # i += 1
3
4 # i += 1
4
5 # i += 1
[1, 2, 3, 4]

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

a = [1, 2, 3, 4]
for i in range(4):
	a[i] = a[i] * a[i]
print(a)

Ссылочная модель, неизменяемость чисел

x = 1 
y = x # 1

y += 1 # 2, так как любая арифметическая операция создает новое число, новый объект

x = 1 # значение в них не изменится, число неизменяемый тип
y = 1

Создание и использование массивов
Одномерный массив (список) заданной длины в Python создаётся так:

N = int(input())
A = [0]*N

# Использовать элементы массива можно по индексу:
for i in range(N):
    print(A[i])

Расмышляем о стеке

A = [0] * 3
top = 0
x = int(input())
while x != 0:
    A[top] = x
    top += 1
    x = int(input())
    print(A)
for k in range(4, -1, -1):
    print(A[k])

Result: 
3
4
[3, 0, 0]
5
[3, 4, 0]
6
[3, 4, 5]

Создадим массив, копирование массивов

N = int(input())
A = [0] * N # созданим массив элементов числа введенного с клавиатуры, и заполним нулями
B = [0] * N

for k in range(N):
    A[k] = int(input()) # заполним массив числами
print(A)

for k in range(N):
    B[k] = A[k] # скопируем в другой массив каждый элемент
print(B)   

# если мы к примеру сделаем `C = A`, то новый объект не создается, и С является всего лишь ссылкой на массив А

C = A
A[0] = 100
print(C[0]) # 100, ссылается на значение A[0]

# есть в языке возможность сделать дубликат массива с помошью list()
C = list(A)
print("Дубликат списка А -", C)

Result: 
3 # это первая строка N = int(input())
# далее вводим числа массива
4
5
6
[4, 5, 6]
[4, 5, 6]

100

Дубликат списка А - [4, 5, 6]

pass — оператор-заглушка, равноценный отсутствию операции. В ходе исполнения данного оператора ничего не происходит, поэтому он может использоваться в качестве заглушки в тех местах, где это синтаксически необходимо, например: в инструкциях, где тело является обязательным, таких как def, except и пр.

Зачастую pass используется там, где код пока ещё не появился, но планируется. Кроме этого, иногда, его используют при отладке, разместив на строчке с ним точку остановки.

def array_search(A:list, N:int, x:int):
    """ Осуществляет поиск числа х в массиве А
        от 0 До N-1 индекса включительно.
        Возвращает индекс элемента х в массиве А.
        Или -1, если такого нет.
        Если в массиве несколько одинаковых 
        элементов, равных х, то вернуть индекс 
        первого по счёту.
    """
pass

def test_array_search():
    A1 = [1, 2, 3, 4, 5]
    m = array_search(A1, 5, 8)
    if m == -1:
        print("#test1 - ok")
    else:
        print("#test1 - fail")
    
    A2 = [-1, -2, -3, -4, -5]
    m = array_search(A2, 5, -3)
    if m == 2:
        print("#test2 - ok")
    else:
        print("#test2 - fail")
        
    A3 = [10, 20, 30, 10, 10]
    m = array_search(A3, 5, 10)
    if m == 0:
        print("#test3 - ok")
    else:
        print("#test3 - fail") 

test_array_search()

Result: 
#test1 - fail
#test2 - fail
#test3 - fail

def array_search(A:list, N:int, x:int):
    """ Осуществляет поиск числа х в массиве А
        от 0 До N-1 индекса включительно.
        Возвращает индекс элемента х в массиве А.
        Или -1, если такого нет.
        Если в массиве несколько одинаковых 
        элементов, равных х, то вернуть индекс 
        первого по счёту.
    """
    for k in range(N):
	    if A[k] == x :
            return k
    return -1

def test_array_search():
    A1 = [1, 2, 3, 4, 5]
    m = array_search(A1, 5, 8)
    if m == -1:
		print("#test1 - ok")
    else:
        print("#test1 - fail")
    
    A2 = [-1, -2, -3, -4, -5]
    m = array_search(A2, 5, -3)
    if m == 2:
        print("#test2 - ok")
    else:
        print("#test2 - fail")
        
    A3 = [10, 20, 30, 10, 10]
    m = array_search(A3, 5, 10)
    if m == 0:
        print("#test3 - ok")
    else:
        print("#test3 - fail") 

test_array_search()

Result: 
#test1 - ok
#test2 - ok
#test3 - ok

Копирование массива в обратном порядке (задом-наперёд, накрест)

Реверс массива — копируем элементы в обратном порядке относительно исходного массива. Было [0, 1, 2, 3] -> [3, 2, 1, 0].

В Си копирование массива, реверс и циклический сдвиг

B[k] = A[N -1 - k]

def invert_array(a: list, n: int):
    """Обращение массива (поворот задом-наперёд)
        в рамках индексов от 0 до N-1
    """
    # n//2 важное условие, иначе работа будет идти
    # по кругу еще раз и результат будет прежний, 
    # т.е мы перевернем массив и еще раз перевернем,
    # и будет тот же результат
    
    for k in range(n // 2):
        a[k], a[n - 1 - k] = a[n - 1 - k], a[k]

def test_invert_array():
    a1 = [1, 2, 3, 4, 5]
    print(a1)
    invert_array(a1, 5)
    print(a1)
    if a1 == [5, 4, 3, 2, 1]:
        print("#test1 - ok")
    else:
        print("#test1 - fail")

    a2 = [0, 0, 0, 0, 0, 0, 0, 10]
    print(a2)
    invert_array(a2, 8)
    print(a2)
    if a2 == [10, 0, 0, 0, 0, 0, 0, 0]:
        print("#test2 - ok")
    else:
        print("#test2 - fail")

test_invert_array()

Result: 
[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]
#test1 - ok
[0, 0, 0, 0, 0, 0, 0, 10]
[10, 0, 0, 0, 0, 0, 0, 0]
#test2 - ok

Циклический сдвиг в массиве — операция преобразования элементов массива.

array[len(array)-1] — последний элемент массива

Влево

array = [0, 1, 2, 3, 4]
tmp = array[0]
for k in range(len(array)-1):
    array[k] = array[k + 1]
array[len(array)-1] = tmp
print(array)

Вправо

array = [0, 1, 2, 3, 4]
tmp = array[len(array)-1]
for k in range(len(array)-2, -1, -1):
    array[k + 1] = array[k]
array[0] = tmp
print(array)

Решето Эратосфена пример в Си

Алгоритм нахождения всех простых чисел до некоторого целого числа n. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются. Вики

Пример кода:

n = int(input())
a = [True] * n
a[0] = a[1] = False
for k in range(2, n):
    if a[k]:
        for m in range(2 * k, n, k):
            a[m] = False
            
for k in range(n):
    print(k, '-', "простое" if a[k] else "составное")

Result: 15
0 - составное
1 - составное
2 - простое
3 - простое
4 - составное
5 - простое
6 - составное
7 - простое
8 - составное
9 - составное
10 - составное
11 - простое
12 - составное
13 - простое
14 - составное

Реализации алгоритмов/Решето Эратосфена

К оглавлению

Лекция №6. Методы append(), pop() и функция len() для списка. Списковые включения. Cортировки.

У массива с фиксированным размером нам нужно самостоятельно отслеживать его уровень заполнения.
Для отслеживания заполнимости массива нам нужна переменная n для отслеживания хранящихся элементов.

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

>>> list('список')
['с', 'п', 'и', 'с', 'о', 'к']

>>> s = []  # Пустой список
>>> l = ['s', 'p', ['isok'], 2]
>>> s
[]
>>> l
['s', 'p', ['isok'], 2]

list.append(x) — Добавляет элемент(или список) в конец списка

Если вам нужно добавить элементы списка в другой список (а не в сам список), используйте метод extend().

len() возвращает длину (количество элементов) в объекте. Уровень заполненности.

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

Необязательный аргумент — индекс i по умолчанию равен -1. Так что по умолчанию эта операция производит действие с последним элементом последовательности.

sequence.pop() метод вызывает IndexError, когда значение индекса i находится за пределами длины последовательностями len(sequence).

Методами sequence.pop() и sequence.append() изменяемых последовательностей, можно организовать алгоритм стека.

И еще один способ создать список — это Генераторы списков или List Comprehension. Способ построить новый список, применяя выражение к каждому элементу последовательности. Генераторы списков очень похожи на цикл for. Сам for в языке является списочного характера.

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

>>> a = []
>>> for i in range(1,15):
...     a.append(i)

>>> a
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

>>> a = [i for i in range(1,15)]
>>> a
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

fruits = ["apple", "banana", "cherry", "kiwi", "mango"]
newlist = []

for x in fruits:
  if "a" in x:
    newlist.append(x)
print(newlist) # ['apple', 'banana', 'mango']

#or
fruits = ["apple", "banana", "cherry", "kiwi", "mango"]
newlist = [x for x in fruits if "a" in x]
print(newlist) #['apple', 'banana', 'mango']

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
B = []
B = [x ** 2 for x in A if x % 2 == 0]
# or тернарный оператор if замениним выражение x ** 2 на конструкцию в скобках
# B = [(0 if x < 0 else x ** 2) for x in A if x % 2 == 0]

print(B) # [4, 16, 36, 64, 100]

Квадратичные сортировки
Количество операций требующихся на выполнение операции обработки массива это n в квадрате, где n это длина массива. O(n^2)

(По неизвестной причине github не подгружает gif, смотри в папке images)

Вставками (insert sort)

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

Выбором (choise/selection sort)
Алгоритм пробегает по всем ещё не упорядоченным элементам, ищет среди них минимальный (сохраняя его значение и индекс) и переставляет в конец выстриваемого списка.

Пузырька (bubble sort)
Соседние элементы сравниваются и при необходимости меняются местами, в результате «лёгкие» элементы перемещаются к началу списка, а «тяжёлые» — к концу. Операция циклически выполняется для оставшихся элементов.

def insert_sort(A):
    """ сортировка списка А вставками """
    N = len(A)
    for top in range(N):
        k = top
        while k > 0 and A[k-1] > A[k]:
            A[k], A[k-1] = A[k-1], A[k]
            k -= 1
            
def choice_sort(A):
    """сортировка списка А выбором """
    N = len(A)
    for pos in range(0, N-1):
        for k in range(pos+1, N):
            if A[k] < A[pos]:
                A[k], A[pos] = A[pos], A[k]

def bubble_sort (A) :
    """сортировкм списка А методом пузырька, начинается с конца"""
    N = len(A)
    for bypass in range(1, N):
        for k in range(0, N-bypass):
            if A[k] > A[k+1]:
                A[k], A[k+1] = A[k+1], A[k]

def test_sort(sort_algorithm):
    print("Тестируем:", sort_algorithm.__doc__)
    print("test case #1: ", end="")
    A = [4, 2, 5, 1, 3]
    A_sorted = [1, 2, 3, 4, 5]
    sort_algorithm(A)
    print("Ok" if A == A_sorted else "Fail")
    
    print("test case #2: ", end="")
    A = list(range(10, 20)) + list(range (0, 10))
    A_sorted = list(range(20))
    sort_algorithm (A)
    print("Ok" if A == A_sorted else "Fail")

    print("test case #3: ", end="")
    A = [4, 2, 4, 2, 1]
    A_sorted = [1, 2, 2, 4, 4]
    sort_algorithm(A)
    print("Ok" if A == A_sorted else "Fail")
    
if __name__ == "__main__":
    test_sort(insert_sort)
    test_sort(choice_sort)
    test_sort(bubble_sort)

Result: 
Тестируем:  сортировка списка А вставками 
test case #1: Ok
test case #2: Ok
test case #3: Ok
Тестируем: сор�ировка списка А выбором 
test case #1: Ok
test case #2: Ok
test case #3: Ok
Тестируем: сортировкм списка А методом пузырька
test case #1: Ok
test case #2: Ok
test case #3: Ok

Сортировка подсчетом (count sort)
Однопроходный алгоритм. Проходимся по массиву и подсчитываем количество вхождений каждого элемента. После проходим по массиву значений и выводим каждое число столько раз, сколько нужно.
Применение сортировки подсчётом целесообразно лишь тогда, когда массив состоит из целочисленных, положительных чисел. O(n). O(m), где m это количество различных элементов.

(По неизвестной причине github не подгружает gif, смотри в папке images)

# основа
N = ....
F = [0] * 10
for i in range(N):
	x = int(input())
	F[x] += 1

Counting Sort in Python

def countingSort(inputArray):
    # Find the maximum element in the inputArray
    maxElement= max(inputArray)

    countArrayLength = maxElement+1

    # Initialize the countArray with (max+1) zeros
    countArray = [0] * countArrayLength

    # Step 1 -> Traverse the inputArray and increase 
    # the corresponding count for every element by 1
    for el in inputArray: 
        countArray[el] += 1

    # Step 2 -> For each element in the countArray, 
    # sum up its value with the value of the previous 
    # element, and then store that value 
    # as the value of the current element
    for i in range(1, countArrayLength):
        countArray[i] += countArray[i-1] 

    # Step 3 -> Calculate element position
    # based on the countArray values
    outputArray = [0] * len(inputArray)
    i = len(inputArray) - 1
    while i >= 0:
        currentEl = inputArray[i]
        countArray[currentEl] -= 1
        newPosition = countArray[currentEl]
        outputArray[newPosition] = currentEl
        i -= 1

    return outputArray

inputArray = [2,2,0,6,1,9,9,7]
print("Input array = ", inputArray)

sortedArray = countingSort(inputArray)
print("Counting sort result = ", sortedArray)

Result: 
Input array =  [2, 2, 0, 6, 1, 9, 9, 7]
Counting sort result =  [0, 1, 2, 2, 6, 7, 9, 9]

К оглавлению

Лекция №7. Рекурсия. Прямой и обратный ход рекурсии. Факториал. Алгоритм Евклида. Ханойские башни.

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

При создании рекурсии мы:

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

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

Глубина рекурсии — количество вызовов, самовызывов функции, включая первый вызов, который произошел из вне. Репка вызвала деда, мастеру кто-то заказал 5 матрешек.

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

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

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

Аналогия простая, один мастер вызывает другого, чтобы он сделал ему нужную матрешку меньшего размера, до тех пор пока конечный мастер не сделает самую маленькую (мастеров много). Глубина вложенности 7 уровней.

Функция может вызвать себя же, это не мешает стеку хранить адрес туда куда надо, т.е код один, НО локальные параметры хранящиеся на стеке разные, на разных уровнях рекурсии n равно разному значению.

Каждый рекурентный виток (мастер который делает матрешку) помнят свои n в обратном ходе рекурсии. У каждого вызова одной и тоже функции свой набор имен, у вызова функции свое пространство имен, при каждом ее рекурентном вызове.

Функция может быть мертвой, лежит в файле exe на жестком диске. А есть вызов функции — это вычислительный процесс который запущен.

Поэтому пока функция выполняется, и объекты в ней живые, сборщик мусора их не съест, до окончания и return.

def matryoshka(n) :
    if n == 1:
        print("Матрёшечка")
    else:
        print("Верх матрёшки n=", n)
        matryoshka (n-1)
        print("Низ матрёшки n=", n)
        
matryoshka(5)

Result: 
Верх матрёшки n= 5
Верх матрёшки n= 4
Верх матрёшки n= 3
Верх матрёшки n= 2
Матрёшечка
Низ мaтрёшки n= 2
Низ матрёшки n= 3
Низ матрёшки n= 4
Низ матрёшки n= 5

В языке есть конструкция разворачивания кортежа, списка параметров и тп, в аргумент функции, например у нас есть заготовленный кортеж с значениями A = (1, 2, 3, 4, 5) и тп, я могу написать их все, но чтобы сделать это кратко я могу их все размернуть в нужное место используя *A.

оператор распаковки (*)

def foo(v1,v2,v3): 
pass

foo(t[0],t[1],t[2])

foo(*t)
# Обратите внимание, что это работает, если t является list, tuple или даже генератором

#Существует аналогичный способ передать аргументы функциям с ключевыми словами, используя оператор ** для сопоставления объектов (обычно словарей):

def foo(key=None,foo=None):
    pass #...

foo(**{key:1,foo:2})

Факториал

Это функция, определённая на множестве неотрицательных целых чисел. Факториал натурального числа n определяется как произведение всех натуральных чисел от 1 до n включительно
5! = 1 * 2 * 3 * 4 * 5 = 120

n! = (n - 1)! * n

assert — оператор проверки, проверяет логическое утверждение, и если находит false, то прерывает выполнение программы, генерует ошибки если вызовут функцию с неправильным параметром, используется для отладки кода. Это своего рода проверка, которая исследует функциональность вашего кода.

Работает как логическое выражение, проверяя, является ли заданное условие истинным или ложным. Если условие истинно, то ничего не происходит и выполняется следующая строка кода. Если же условие ложно, оператор assert останавливает выполнение программы и выдает ошибку.

Этот оператор принимает условие и необязательное сообщение, которое выводится, если условие assert ложно. В этом случае инструкция assert выводит AssertionError.

При выполнении операции деления следует учитывать, что на ноль делить нельзя. Если делитель будет равен нулю, программа вызовет ошибку ZeroDivisionError. Чтобы проверить, не равен ли делитель нулю, можно вставить оператор assert.

num1 = 10
num2 = 0
assert num2 != 0, "The divisor is zero"

В assert мы указали условие, что num2 (делитель) не должен быть равен нулю. Данное условие не выполняется, потому что значение num2 равно нулю. Интерпретатор Python выдает ошибку AssertionError вместе с добавленным нами сообщением «The divisor is zero» («Делитель равен нулю»).

def factorial (n:int):
    assert n > 0, "Факториал неопределенный"
    if n == 1:
        return 1
    return factorial(n-1) * n
    
print(factorial(5)) # 120

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

def fac(n):
    f = 1
    x = 2
    while x <= n:
         f *= x
         x += 1

    return f
print(fac(5))

Отличие этих двух программ кроется в подходе к их построению. Первая написана в декларативном стиле, то есть для вычисления факториала используются его свойства, а именно n! = n*(n-1)! и 0!=1. Второй же подход использует императивный стиль: мы явно описываем, что представляет из себя факториал: n! = 1*2*…*n. В большинстве случаев один и тот же алгорит может быть легко записан, как в рекурсивной форме, так и в нерекурсивной, но существует ряд задач, для которых построение нерекурсивного алгоритма представляется весьма трудозатратным.

Примеры рекурсивных алгоритмов

Алгоритм Евклида — эффективный метод вычисления наибольшего общего делителя (НОД).

НОД(a, b) — наибольший общий делитель чисел пишется «greatest common divisor»

Существует несколько вариантов алгоритма, ниже записанный в псевдокоде рекурсивный вариант:

функция нод(a, b)
    если b = 0
       возврат a
    иначе
       возврат нод(b, a mod b)

Иллюстрация выполнения алгоритма Евклида для вычисления НОД чисел 1599 и 650:

Шаг 1. 1599 = 650*2 + 299

Шаг 2. 650 = 299*2 + 52

Шаг 3. 299 = 52*5 + 39

Шаг 4. 52 = 39*1 + 13

Шаг 5. 39 = 13*3 + 0

gif в папке images

def gcd (a:int, b:int):
    if a == b:
        return a
    elif a > b:
        return gcd(a-b, b)
    elif a < b:
        return gcd(a, b-a)
    
print(gcd(7,14)) # 7
print(gcd(7,13)) # 1

or

def gcd (a:int, b:int):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

or

def gcd (a:int, b:int):
    return a if b == 0 else gcd(b, a%b)

Быстрое возведение в степень

Рассматриваем только для целых положительных чисел, a не равно нулю, и n отрицательное.

def pow(a:float, n:int):
    if n == 0:
        return 1
    return pow(a, n-1) * a
    
print(pow(5, 4)) # 625

def pow(a:float, n:int):
    if n == 0:
        return 1
        
    # для нечетной степени
    elif n%2 == 1:
        return pow(a, n-1) * a
    
    # для четной степени
    return pow(a**2, n//2)
    
print(pow(5, 10)) # 9765625

Ханойские башни

n — высота, i — столбец с которого нужно переложить k — столбец на который нужно переложить, tmp — временное хранище, запасной столбец

def hanoi(n, i, k):
    if (n == 1):
        print("Move disk 1 from pin", i, "to", k);
    else:
        tmp = 6 - i - k;
        hanoi(n-1, i, tmp);
        print("Move disk", n, "from pin", i, "to", k);
        hanoi(n-1, tmp, k);
        
print(hanoi(3, 1, 2))

Result:
Move disk 1 from pin 1 to 2
Move disk 2 from pin 1 to 3
Move disk 1 from pin 2 to 3
Move disk 3 from pin 1 to 2
Move disk 1 from pin 3 to 1
Move disk 2 from pin 3 to 2
Move disk 1 from pin 1 to 2

К оглавлению

Лекция №8. Генерация комбинаторных объектов. Рекурсивная генерация всех чисел длины M. Генерация всех перестановок (рекурсивная). Быстрые или Рекуррентные сортировки: Тони Хоара и слиянием (без реализации).

Генерация комбинаторных объектов. Рекурсивная генерация всех чисел длины

Логика перебора чисел, рекурентно.

Простой пример, логики программы, для двоичной системы счисления:

def gen_bin(M, prefix=""):
    if M == 0:
        print(prefix)
        return
    gen_bin(M-1, prefix+"0")
    gen_bin(M-1, prefix+"1")
    
    # или в цикле
    # for digit in "0", "1":
    #     gen_bin(M-1, prefix+digit)
    
gen_bin(3)

Result:
000
001
010
011
100
101
110
111

Для произвольной системы счисления:

def generate_number(N:int, M:int, prefix=None):
    """ Генерирует все числа (с лидирующими незначащими нулями)
        в N-ричной системе счисления (N <= 10) длины М
    """
    prefix = prefix or []
    if M == 0:
        print(prefix)
        return
    for digit in range(N):
        prefix.append(digit)
        generate_number(N, M-1, prefix)
        prefix.pop()
        
# для двоичных чисел длины 3
generate_number(2, 3)

# для троичных чисел длины 3
# generate_number(3, 3)

Result:
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

Генерация всех перестановок

def find(number, A):
    """ ищет number в А и возвращает True, если такой есть
        False, если такого нет
    """
    flag = False
    for x in A:
        if number == x:
            flag = True
            break
    return flag

def generate_permutations(N:int, M:int=-1, prefix=None):
    """ Generating all permutations of N numbers in M positions,
        with prefix prefix
    """
    if M == -1:
        M = N  # по умолчанию, N чисел в N позициях
        
    prefix = prefix or []
    if M == 0:
        print(prefix)
        # можно использовать оператор * , чтобы встроить
        # все параметры
        # print(*prefix)
        return
    for number in range(1, N+1):
        if find(number, prefix): #FIXME
            continue
        prefix.append(number)
        generate_permutations(N, M-1, prefix)
        prefix.pop()

generate_permutations(3)

Result:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

При использовании оператора `*` , чтобы встроить
все параметры в `print(*prefix)`
Result:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Быстрые или Рекуррентные сортировки: Тони Хоара и слиянием (без реализации).

Сортировка Тони Хоара на неторорых выборках массивов сортирует плохо. Сортировка слияние сортирует всегда хорошо, в остальном они чаще всего одинаковые по скорости.

Фрактал (лат. fractus — дроблёный, сломанный, разбитый) — множество, обладающее свойством самоподобия (объект, в точности или приближённо совпадающий с частью себя самого, то есть целое имеет ту же форму, что и одна или более частей).

Хорошим примером для иллюстрации рекурсивных алгоритмов являются задачи рисования фракталов. Фрактальные кривые, обладающие бесконечным самоподобием, не являются спрямляемыми: хоть их и можно изобразить на плоскости конечной площади, эти кривые имeют бесконечную длину.

Длина кривой (или длина дуги кривой) — числовая характеристика протяжённости этой кривой. Исторически вычисление длины кривой называлось спрямлением кривой (от лат. rectificatio, спрямление).

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

Пример программы, использующей рекурсивные вызовы функции, чтобы нарисовать ветку:

import turtle

def draw(l, n):
    if n == 0:
        turtle.left(180)
        return

    x = l / (n + 1)
    for i in range(n):
        turtle.forward(x)
        turtle.left(45)
        draw(0.5 * x * (n - i - 1), n - i - 1)
        turtle.left(90)
        draw(0.5 * x * (n - i - 1), n - i - 1)
        turtle.right(135)

    turtle.forward(x)
    turtle.left(180)
    turtle.forward(l)

draw(400, 5)

Кривая Коха — фрактальная кривая, описанная в 1904 году шведским математиком Хельге фон Кохом.

Кривую Коха. Процесс её построения выглядит следующим образом: берём единичный отрезок, разделяем на три равные части и заменяем средний интервал равносторонним треугольником без этого сегмента. В результате образуется ломаная, состоящая из четырёх звеньев длины 1/3. На следующем шаге повторяем операцию для каждого из четырёх получившихся звеньев и т. д… Предельная кривая и есть кривая Коха.

Пример работы алгоритма при разной глубине рекурсии:

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

Пример работы алгоритма при разной глубине рекурсии:

Кривая Минковского нулевого порядка — горизонтальный отрезок. Затем на каждом шаге каждый из отрезков заменяется на ломанную, состоящую из 8 звеньев.

Пример работы алгоритма при разной глубине рекурсии:

from turtle import *

def start(x: float):
    """This function clears window and make turtle go to start"""
    clear()
    penup()
    x = x if x < 0 else -x
    goto(x, 0)
    pendown()
 
def curve_minkowski(length: float, iterations: int):
    """This function draw Minkowski's curve"""
 
    if iterations == 0:
        forward(length * 4)
    else:
        curve_minkowski(length/4, iterations - 1)
        left(90)
        curve_minkowski(length/4, iterations - 1)
        right(90)
        curve_minkowski(length/4, iterations - 1)
        right(90)
        curve_minkowski(length/4, iterations - 1)
        curve_minkowski(length/4, iterations - 1)
        left(90)
        curve_minkowski(length/4, iterations - 1)
        left(90)
        curve_minkowski(length/4, iterations - 1)
        right(90)
        curve_minkowski(length/4, iterations - 1)
LENGTH = 100       # длина линии
ITERATION = 3      # номер итерации
start(LENGTH * 2)
curve_minkowski(LENGTH, ITERATION)
exitonclick()    # функция чтобы программа не завершалась сразу

Кривая Леви. Она получается, если взять половину квадрата вида /, а затем каждую сторону заменить таким же фрагментом и так далее.

Пример работы алгоритма при разной глубине рекурсии:

import turtle

turtle.hideturtle()
turtle.tracer(0)
turtle.penup()
turtle.setposition(-100, 0)
turtle.pendown()

axiom, tempAx, logic, iterations = 'F', '', {'F': '-F++F-'}, 15

for i in range(iterations):
    for j in axiom:
        tempAx += logic[j] if j in logic else j
    axiom, tempAx = tempAx, ''

for k in axiom:
    if k == '+':
        turtle.right(45)
    elif k == '-':
        turtle.left(45)
    else:
        turtle.forward(1)

turtle.update()
turtle.mainloop()

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

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

Канторово множество нулевого порядка — горизонтальный отрезок. Удалив среднюю треть получим множество первого порядка. Повторяя данную процедуру получим остальные множества.

К оглавлению

Лекция №9. Быстрая сортировка Тони Хоара и Сортировка слиянием (реализация). Слияние двух упорядоченных массивов. Устойчивость сортировок. Проверка упорядоченности массива за O(N).

Сортировка слиянием (реализация)

Алгоритм слияние отсортированных массивов в один.

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

Более простая и понятная реализация с 2 массивами на вход для сливания.

def merge (A:list, B:list):
    C = [0] * (len(A) + len(B))
    i = k = n = 0
    while i < len(A) and k < len(B):
        if A[i] <= B[k]:
            C[n] = A[i]
            i += 1
            n += 1
        else:
            C[n] = B[k]
            k += 1
            n += 1
    while i < len(A):
        C[n] = A[i]
        i += 1
        n += 1
    while k < len(B):
        C[n] = B[k]
        k += 1
        n += 1
    return C

A = [1, 3, 5, 4, 10]
B = [3, 2, 9, 2, 9]
print(merge(A, B))

Result:
[1, 3, 3, 2, 5, 4, 9, 2, 9, 10]

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

Сама реализация рекурентной сортировки слиянием

def merge описана выше

def merge_sort(A):
    if len(A) <= 1:
        return
    middle = len(A)//2
    left_part = [A[i] for i in range(0, middle)]
    right_part = [A[i] for i in range(middle, len(A))]
    merge_sort(left_part)
    merge_sort(right_part)
    C = merge(left_part, right_part)
    for i in range(len(A)):
        A[i] = C[i]
    return A 
    
D = [1, 3, 2, 14, 5, 10, 9, 13, 4, 6]
print(merge_sort(D))

Result:
[1, 2, 3, 4, 5, 6, 9, 10, 13, 14]

Сортировка Тони Хоара (быстрая сортировка/quick sort)

Новые объекты в Питоне появляются единственным способом, это вычислением самого оlбъекта. Помним об ссылочной модели в языке.

def hoar_sort(A):
    if len(A) <= 1:
        return
    
    # барьерный элемент, допускаем что это число случайное
    # и на его основе будет делать массив на три части
    barrier = A[0]
    left = []
    middle = []
    right = []
    
    for x in A:
        if x < barrier:
            left.append(x)
        elif x == barrier:
            middle.append(x)
        else:
            right.append(x)
            
    hoar_sort(left)
    hoar_sort(right)
    
    k = 0
    for x in left + middle + right:
        A[k] = x
        k += 1
    return A
        
D = [1, 3, 2, 14, 5, 10, 9, 13, 4, 6]
print(hoar_sort(D))

Result:
[1, 2, 3, 4, 5, 6, 9, 10, 13, 14]

Проверка упорядоченности массива за O(N)

ascending — возрастание

def check_sorted(A, ascending = True):
    """ Проверка отсортированности массива за O(len(A) """
    flag = True
    s = 2 * int(ascending) - 1
    
    for i in range(0, len(A) - 1):
        if s * A[i] > s * A[i + 1]:
            flag = False
            break
    return flag
    
D = [1, 3, 2, 14, 5 ]
F = [1, 2, 3, 4 , 5 ]
print(check_sorted(D)) # false
print(check_sorted(F)) # true

Бинарный поиск в массиве

[1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 7, 7, 7]
left_bound and right_bound

middle = (left_bound + right_bound) // 2

# аналогия с порванным телефонным справочников в курсе CS50

Реализиция бинарного поиска в массиве

Скорость работы очень быстрая. O(log2 N)
Разбор в начале 10 лекции. Массив должен быть отсортирован.

def left_bound(A, key):
    left = -1
    right = len(A)
    while right - left > 1:
        middle = (right + left) // 2
        if A[middle] < key:
            left = middle
        else:
            right = middle
    return left

def right_bound(A, key):
    left = -1
    right = len(A)
    while right - left > 1:
        middle = (right + left) // 2
        if A[middle] <= key:
            left = middle
        else:
            right = middle
    return right

D = [1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 7, 7, 7]
print(left_bound(D, 3))
print(right_bound(D, 2))

К оглавлению

Лекция №10. Вычисление чисел Фибоначчи и проблема перевычислений. Одномерное динамическое программирование на примере чисел Фибоначчи. Задачи о кузнечике (количество траекторий, траектория наименьшей стоимости). Двумерные массивы (списки списков). Оператор is.

Динамическое программирование

Числа Фибоначчи — элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел

«Как раз это и называется динамическим программированием — рекурсия вывернутая наоборот»

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
print(fib(10)) # 55

C помощью цикла for без рекурсии

def fib(n):
    fib = [0, 1] + [0] * (n-1)
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]
    
print(fib(5)) # 5 

Задача о кузнечике (количество траекторий)

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

Обозначим количество маршрутов кузнечика, ведущих в точку с координатой n, как K[n]. Прежде всего заметим, что существует ровно один маршрут из точки 1 в точку 1 — он не содержит ни одного прыжка. В точку 2 можно прыгнуть единственным способом — из точки 1.

Как вычислить K[n]? В точку кузнечик может попасть двумя способами — из точки при помощи прыжка длиной 2 и из точки прыжком длины 1. То есть число способов попасть в точку n равно сумме числа способов попасть в точку (n-1) и (n-2), что позволяет выписать рекуррентное соотношение: K[n] = K[n-1] + K[n-2].

Можно заметить, что данная задача по сути свелась к числам Фибоначчи

def traj_num(N):
    K = [0, 1] + [0] * N
    for i in range(2, N+1):
        K[i] = K[i-2] + K[i-1]
    return K[N]

С запрещенными клеткам для прыжка

def count_trajectories(N, allowed:list):
    K = [0, 1, int(allowed[2])] + [0] * (N-3)
    for i in range(3, N+1):
        if allowed[i]:
            K[i] = K[i-1] + K[i-2] + K[i -3]
    return K[N]

Траектория наименьшей стоимости

Пусть кузнечик прыгает на одну или две точки вперед, а за прыжок в каждую точку необходимо заплатить определенную стоимость, различную для различных точек. Стоимость прыжка в точку i задается значением price[i] списка price. Необходимо найти минимальную стоимость маршрута кузнечика из точки 0 в точку n.

На этот раз нам необходимо модифицировать определение целевой функции. Пусть C[n] — минимальная стоимость пути из 1 в n.

Выведем рекуррентное соотношение для этой функции.Чтобы попасть в точку n мы должны попасть в неё последним прыжком из (n-1) или (n-2). Минимальные стоимости этих маршрутов будут равны С[n-1] и С[n-2] соответственно, к ним придется добавить значение price[n] за прыжок в клетку n. Но из двух клеток мы можем выбрать любую.

Нужно выбрать тот маршрут, который имеет наименьшую стоимость: C[n] = min(C[n-1], C[n-2]) + price[n]

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

def count_min_cost(N, price:list):
    C = [float("-inf"), price[1], price[1] + price[2]] + [0] * (N-2)
    for i in range(3, N+1):
        C[i] = price[i] + min(C[i-1], C[i-2])
    return C[N]

Восстановление наиболее выгодной траектории

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

Но помимо нахождения наименьшей стоимости маршрута, разумеется, хотелось бы найти и сам маршрут минимальной стоимости. Такая задача называется задачей «восстановления ответа».

Для восстановления ответа будем для каждой точки запоминать номер точки prev[i], из которой кузнечик попал в точку i, если он будет передвигаться по пути минимальной стоимости. То есть prev[i] — это точка, предшествующая точке с номером i на пути минимальной стоимости (также говорят, что Prev — это массив предшественников). Как определить prev[i]? Если C[i-1] < C[i-2], то кузнечик попал в точку i из точки (i-1), поэтому prev[i] = i - 1, иначе prev[i] = i - 2.

Для восстановления пути необходимо начать с точки n и переходить от каждой точки к ее предшественнику, пока путь не дойдет до начальной точки с номером 0. Номера всех вершин будем добавлять в список path. В конце в список path добавляется начальная вершина номер 1, которая не была обработана в основном цикле, а затем весь список path разворачивается в обратном порядке (т. к. вершины добавляются в обратном порядке, от конечной к начальной).

Двумерные массивы (списки списков).

• Линеаризация массива

• Список списков

A = [[0] * M for i in range(N)]

Двумерное динамическое программирование

Игра с ферзём.
Рассмотрим игру «Ферзя в угол» для двух игроков. В левом верхнем углу доски размером N*M находится ферзь, который может двигаться только вправо-вниз. Игроки по очереди двигают ферзя, то есть за один ход игрок может переместить ферзя либо по вертикали вниз, либо по горизонтали вправо, либо во диагонали вправо-вниз. Выигрывает игрок, который поставит ферзя в правый нижний угол. Необходимо определить, какой из игроков может выиграть в этой игре независимо от ходов другого игрока (имеет выигрышную стратегию).

Будем заполнять доску знаками «+» и «-». Знак «+» будет означать, что данная клетка является выигрышной для ходящего с неё игрока (то есть если ферзь стоит в этой клетке, то игрок, который делает ход, может всегда выиграть), а знак «-» означает, что он проигрывает. Клетки последней строки, последнего столбца и диагонали, ведущей из правого нижнего угла необходимо отметить, как «+», так как если ферзь стоит в этой клетке, то ходящий игрок может выиграть одним ходом.

Но в правом нижнем углу необходимо поставить знак «-» — если ферзь стоит в углу, то тот игрок, которых должен делать ход, уже проиграл.

Теперь рассмотрим две клетки, из которых можно пойти только в те клетки, в которых записан знак «+». В этих клетках нужно записать знак «-» — если ферзь стоит в этих клетках, то какой бы ход не сделал ходящий игрок, ферзь окажется в клетке, в которой стоит знак «+», то есть выигрывает ходящий игрок. Значит, тот, кто сейчас ходит — всегда проигрывает.

Но теперь в те клетки, из которых можно попасть в клетку, в которой стоит знак «-» за один ход, необходимо записать знак «+» — если ферзь стоит в этой клетке, то игрок, который делает ход, может выиграть, если передвинет ферзя в клетку, в которой стоит знак «-»:

Дальше таблица заполняется аналогично. В клетке ставиться знак «+», если есть ход, который ведет в клетку, в которой стоит знак «—». В клетке ставится знак «-», если все ходы из этой клетки ведут в клетки, в которых записан знак «+».

Продолжая таким образом, можно определить выигрывающего игрока для любой начальной клетки.

Оператор is используется, чтобы определить равны ли объекты/имена в ссылочной модели.

Оператор is сравнивает идентичность двух объектов, в то время как оператор == сравнивает значения двух объектов. Существует разница в значении между равными и идентичными.

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

Оператор is оценивает значение true, если переменные с обеих сторон оператора указывают на один и тот же объект и false в противном случае.

Рассмотрим следующий пример:

list_1 = ['a', 'b', 'c']
list_2 = list_1
list_3 = list(list_1)
print(list_1) # ['a', 'b', 'c']
print(list_2) # ['a', 'b', 'c']
print(list_3) # ['a', 'b', 'c']
 
print(list_1 == list_2) # True
print(list_1 == list_3) # True

print(list_1 is list_2) # True
print(list_1 is list_3) # False

Здесь вы можете видеть (list_1 is list_3) False, потому что list_1 и list_3 указывают на два разных объекта, хотя их содержимое может быть одинаковым. Итак, is вернет True, если две переменные указывают на один и тот же объект и ==, если объекты, на которые ссылаются переменные, равны.

К оглавлению

Лекция №11. Двумерное динамическое программирование. Наибольшая общая подпоследовательность. Наибольшая возрастающая подпоследовательность.

Динамическое программирование — решение сложной задачи разбиением её на более простые подзадачи, при этом каждая подзадача решается только один раз.

Динамическое программирование очень похоже на рекурсию, при этом:

• динамическое программирование сверху — это по сути рекурсия с кешированием;

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

Одномерное динамическое программирование

Классическая задача — числа Фибоначчи

Последовательность Фибоначчи Fn задается формулами: F1 = 1, F2 = 1, Fn = Fn – 1 + Fn – 2 при n > 1. Необходимо найти Fn по номеру n.

Один из способов решения, который может показаться логичным и эффективным, — решение с помощью рекурсии:

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

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

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования (кеширование):

F = [-1]*MAX_POSSIBLE_N

def fib(n):
    if n <= 1:
        return n
    if F[n] == -1:
       F[n] = fib(n-1) + fib(n-2)
    return F[n]

Приведенное решение корректно и эффективно. Но можно поступить ещё проще:

def fib(n):
    F = [-1]*(n+1)
    F[0] = 0
    F[1] = 1
    for i in range(2, n+1):
        F[i] = F[i - 1] + F[i - 2]
    return F[n]

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

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F[i] для i < n), затем, зная решения подзадач, нашли ответ.

Задача про шахматного короля

Двумерный массив, это массив массивов, список строк, и в нем по факту нет столбцов, поэтому используем терминалогию: 1) номер строки (N), 2) положение элемента в строке (M)

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

Числа на шахматной доске, треугольник Паскаля перевернутый на 45 градусов

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

Параллейное программирование нужно для быстрого
вычисления огромных промышленных размеров данных.

Наибольшая общая подпоследовательность

Подпоследовательность — некий список С, который содержит элементы А в исходном порядке, но возможно не все.

F — длина наибольшей возможной подпоследовательности, частей А и В

A[0:i] — часть A, первые i элементы

B[0:j] — часть B, первые j элементы

def lcs(A,B):
    F = [[0] * (len(B) + 1) for i in range (len(A) + 1)]
    for i in range(1, len(A) + 1):
        for j in range(1, len(B) + 1):
            if A[i-1] == B[j-1]:
                F[i][j] = 1 + F[i-1][j-1]
            else:
                F[i][j] = max(F[i-1][j], F[i][j-1])
    return F[-1][-1]

Наибольшая возрастающая подпоследовательность (НВП)

Ищем длину НВП

def gis(A):
    F = [0] * (len(A) + 1)
    for i in range(1, len(A) + 1):
        max = 0
        for j in range(0, i):
            if A[i] > A[j] and F[j] > max:
                max = F[j]
        F[i] = max + 1
    return F[len(A)]

or

Возможная опечатка в алгоритме выше. В случае если, как под видео поменять индексы (индексы A(i), A(j) должны быть A(i-1) и A(j-1)) — алгоритм отработает, но A[j] будет идет с конца (первая инициализация A[-1]). Целевую функцию можно переопределись следующим образом

def gis(a):
    f = [0]*(len(a))
    f[0] = 1
    for i in range(1, len(a)):
        maximum = 0
        for k in range(i):
            if a[i] > a[k] and f[k] > maximum:
                maximum = f[k]
        f[i] = maximum + 1
    return f[-1]

К оглавлению

Лекция №12. Расстояние Левенштейна. Проверка равенства строк. Наивный поиск подстроки в строке. Z-функция. Алгоритм Кнута-Морриса-Пратта

Редакционное расстояние между строками (Левенштейна)

Используем динамическое программирование

А i будет по вертикали с N

В j будет по горизонтали с M

+1 так как нужны нулевые элементы

Асимптотика алгоритма O (M * N)

def levenstein(A,B):
    # создаем строки, и крайние случаи
    # проходить будем слева направо строка за строкой
    F = [[(i + j) if i*j == 0 else 0 for j in range(len(B) + 1)] for i in range(len(A) + 1) ]
    
    for i in range(1, len(A) + 1):
        for j in range(1, len(B) + 1):
            if A[i-1] == B[j-1]:
                F[i][j] = F[i-1][j-1]
            else:
                F[i][j] = 1 + min(F[i-1][j], F[i][j-1], F[i-1][j-1])
    return F[len(A)][len(B)]

A = "колокол"
B = "молоко"
print(levenstein(A,B)) # 2

D = "кол"
C = "кот"
print(levenstein(D,C)) # 1

Проверка равенства строк

Простой подход -> если длины строк не равны, значит и сами строки разные. Далее поэлементное сравнение. Асимптотика O(N)

def equal(A,B):
    if len(A) != len(B):
        return False
    for i in range(len(A)):
        if A[i] != B[i]:
            return False
    return True

D = "кол"
C = "кол"
print(equal(D,C)) # true

I = "кол"
F = "кот"
print(equal(I,F)) # false

Наивный поиск подстроки в строке

Асимптотика O(N * M)

def equal(A,B):
    if len(A) != len(B):
        return False
    for i in range(len(A)):
        if A[i] != B[i]:
            return False
    return True

def search_substring(s, sub):
    for i in range(0, len(s) - len(sub)):
        if equal(s[i:i+len(sub)], sub):
            print("Подстрока начинается с позиции:", i)

s = "catdogcat"
sub = "dog"
search_substring(s, sub)

Result:
Подстрока начинается с позиции: 3

Префиксная функция П строки

Суффикс это окончание строки.

Собственный суффикс — это суффикс, который не совпадает со всей строкой. Суффикс не равный строке.

Подробнее о Префикс-функция

Z-функция

Здесь и далее строки индексируются с нуля, т.е. первый символ строки имеет номер 0. Также, здесь и далее s[i…j] обозначает подстроку строки s от i-го символа до j-го включительно.

Пусть дана строка s длины n. Тогда Z(s) — это массив длины n, i-ый элемент которого равен наибольшему числу символов, начиная с позиции i, совпадающих с первыми символами строки s.

Иными словами, z[i] — это длина наибольшего общего префикса строки s и её i-го суффикса.

Первый элемент Z-функции, z[0], обычно считают неопределённым. В данной статье мы будем считать, что он равен нулю (хотя ни в алгоритме, ни в приведённой реализации это ничего не меняет).

Далее будет привиден алгоритм вычисления Z-функции за время O(n), а также различные применения этого алгоритма.

Приведём для примера подсчитанную Z-функцию для нескольких строк:

«aaaaa»:

z[0] = 0,
z[1] = 4,
z[2] = 3,
z[3] = 2,
z[4] = 1.

«aaabaab»:

z[0] = 0,
z[1] = 2,
z[2] = 1,
z[3] = 0,
z[4] = 2,
z[5] = 1,
z[6] = 0.

«abacaba»:

z[0] = 0,
z[1] = 0,
z[2] = 1,
z[3] = 0,
z[4] = 3,
z[5] = 0,
z[6] = 1.

Тривиальный алгоритм

Формальное определение можно представить в виде следующей элементарной реализации за O(n^2):

def z_func(s, n):
    z = [0] * n
    for i in range(1, n - 1):
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
    return z

Мы просто для каждой позиции i перебираем ответ для неё z[i], начиная с нуля, и до тех пор, пока мы не обнаружим несовпадение или не дойдём до конца строки.

Разумеется, эта реализация слишком неэффективна, перейдём теперь к построению эффективного алгоритма.

Эффективный алгоритм вычисления Z-функции

Чтобы получить эффективный алгоритм, будем вычислять значения z[i] по очереди — от i=1 до n−1, и при этом постараемся при вычислении очередного значения z[i] максимально использовать уже вычисленные значения.

Назовём для краткости подстроку, совпадающую с префиксом строки s, отрезком совпадения. Например, значение искомой Z-функции z[i] — это длина длиннейшего отрезок совпадения, начинающийся в позиции i (и заканчиваться он будет в позиции i+z[i]−1).

Для этого будем поддерживать координаты [l;r] самого правого отрезка совпадения, т.е. из всех обнаруженных отрезков будем хранить тот, который оканчивается правее всего. В некотором смысле, индекс r — это такая граница, до которой наша строка уже была просканирована алгоритмом, а всё остальное — пока ещё не известно.

Тогда если текущий индекс, для которого мы хотим посчитать очередное значение Z-функции, — это i, мы имеем один из двух вариантов:

• i>r т.е. текущая позиция лежит за пределами того, что мы уже успели обработать.

Тогда будем искать z[i] тривиальным алгоритмом, т.е. просто пробуя значения z[i]=0, z[i]=1, и т.д. Заметим, что в итоге, если z[i] окажется >0, то мы будем обязаны обновить координаты самого правого отрезка [l;r] — т.к. i+z[i]−1 гарантированно окажется больше r.

• i≤r — т.е. текущая позиция лежит внутри отрезка совпадения [l;r].

Тогда мы можем использовать уже подсчитанные предыдущие значения Z-функции, чтобы проинициализировать значение z[i] не нулём, а каким-то возможно бoльшим числом.

Для этого заметим, что подстроки s[l…r] и s[0…r−l] совпадают. Это означает, что в качестве начального приближения для z[i] можно взять соответствующее ему значение из отрезка s[0…r−l], а именно, значение z[i−l].

Однако значение z[i−l] могло оказаться слишком большим: таким, что при применении его к позиции i оно «вылезет» за пределы границы r. Этого допустить нельзя, т.к. про символы правее r мы ничего не знаем, и они могут отличаться от требуемых.

Приведём пример такой ситуации, на примере строки «aaaabaa».

Когда мы дойдём до последней позиции (i=6), текущим самым правым отрезком будет [5;6]. Позиции 6 с учётом этого отрезка будет соответствовать позиция 6−5=1, ответ в которой равен z[1]=3. Очевидно, что таким значением инициализировать z[6] нельзя, оно совершенно некорректно. Максимум, каким значением мы могли проинициализировать — это 1, поскольку это наибольшее значение, которое не вылезает за пределы отрезка [l;r].

Таким образом, в качестве начального приближения для z[i] безопасно брать только такое выражение:

z0[i]=min(r−i+1,z[i−l]).

Проинициализировав z[i] таким значением z0[i], мы снова дальше действуем тривиальным алгоритмом — потому что после границы r, вообще говоря, могло обнаружиться продолжение отрезка совпадение, предугадать которое одними лишь предыдущими значениями Z-функции мы не можем.

Таким образом, весь алгоритм представляет из себя два случая, которые фактически различаются только начальным значением z[i]: в первом случае оно полагается равным нулю, а во втором — определяется по предыдущим значениям по указанной формуле. После этого обе ветки алгоритма сводятся к выполнению тривиального алгоритма, стартующего сразу с указанного начального значения.

Алгоритм получился весьма простым. Несмотря на то, что при каждом i в нём так или иначе выполняется тривиальный алгоритм — мы достигли существенного прогресса, получив алгоритм, работающий за линейное время (действительно, на каждый символ мы «посмотрим», т.е. сравним его с каким-либо предыдущим всего один раз).

def z_func(s):
  z = [0] * len(s)
  left, right = 0, 0
  for i in range(1, len(s)):
    z[i] = max(0, min(z[i - left], right - i))
    while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
      z[i] += 1
    if i + z[i] > right:
      left, right = i, i + z[i]
  return z

print(z_func("abcdabscabcdabiad"))

# иная реализация
def zfun(s):
    out = []
    if not s: return out
    i, slen = 1, len(s)
    out.append(slen)
    while i < slen:
        left, right = 0, i
        while right < slen and s[left] == s[right]:
            left += 1
            right += 1
        out.append(left)
        i += 1
    return out
print(zfun("abcdabscabcdabiad"))

Result:
[0, 0, 0, 0, 2, 0, 0, 0, 6, 0, 0, 0, 2, 0, 0, 1, 0]
[17, 0, 0, 0, 2, 0, 0, 0, 6, 0, 0, 0, 2, 0, 0, 1, 0]

Префикс-функция. Алгоритм Кнута-Морриса-Пратта (КМП)

Материал позаимствован с сайта

Префикс-функция. Определение

Пусть дана строка s длины n. Тогда π(s) — это массив длины n, i-ый элемент которого (π[i]) определяется следующим образом: это длина наибольшего собственного суффикса подстроки s[0…i], совпадающего с её префиксом (собственный суффикс — значит не совпадающий со всей строкой). В частности, значение π[0] полагается равным нулю.

Примечение: вообще говоря, в теории множеств собственным считается не пустое подмножество, не совпaдающее с самим множеством. В данной статье, для простоты суффикс и префикс нулевой длины также считаются собственными.

Математически определение префикс-функции можно записать следующим образом:

Например, для строки «abcabcd» префикс-функция равна: [0,0,0,1,2,3,0], что означает:

у строки "a" нет нетривиального префикса, совпадающего с суффиксом;
у строки "ab" нет нетривиального префикса, совпадающего с суффиксом;
у строки "abc" нет нетривиального префикса, совпадающего с суффиксом;
у строки "abca" префикс длины 1 совпадает с суффиксом;
у строки "abcab" префикс длины 2 совпадает с суффиксом;
у строки "abcabc" префикс длины 3 совпадает с суффиксом;
у строки "abcabcd" нет нетривиального префикса, совпадающего с суффиксом.

Другой пример — для строки «aabaaab» она равна: [0,1,0,1,2,2,3].

Тривиальный алгоритм

Непосредственно следуя определению, можно написать такой алгоритм вычисления префикс-функции:

def prefix_func(s, n):
    pi = [0] * n
    for i in range(n - 1):
        for k in range(1, i + 1):
            equal = True
            for j in range(k):
                if s[j] != s[i - k  + 1 + j]:
                    equal = False
                    break
            if equal:
                pi[i] = k
    return pi

Как нетрудно заметить, работать он будет за O(n^3), что слишком медленно.

Эффективный алгоритм

Поиск подстроки в строке. Алгоритм Кнута-Морриса-Пратта

Эта задача является классическим применением префикс-функции (и, собственно, она и была открыта в связи с этим).

Дан текст t и строка s, требуется найти и вывести позиции всех вхождений строки s в текст t.

Обозначим для удобства через n длину строки s, а через m — длину текста t.

Образуем строку s + # + t, где символ # — это разделитель, который не должен нигде более встречаться. Посчитаем для этой строки префикс-функцию. Теперь рассмотрим её значения, кроме первых n+1 (которые, как видно, относятся к строке s и разделителю). По определению, значение π[i] показывает наидлиннейшую длину подстроки, оканчивающейся в позиции i и совпадающего с префиксом. Но в нашем случае это π[i] — фактически длина наибольшего блока совпадения со строкой s и оканчивающегося в позиции i. Больше, чем n, эта длина быть не может, за счёт разделителя. А вот равенство π[i]=n (там, где оно достигается), означает, что в позиции i оканчивается искомое вхождение строки s (только не надо забывать, что все позиции отсчитываются в склеенной строке s + # + t).

Таким образом, если в какой-то позиции i оказалось π[i]=n, то в позиции i−(n+1)−n+1=i−2n строки t начинается очередное вхождение строки s в строку t.

Как уже упоминалось при описании алгоритма вычисления префикс-функции, если известно, что значения префикс-функции не будут превышать некоторой величины, то достаточно хранить не всю строку и префикс-функцию, а только её начало. В нашем случае это означает, что нужно хранить в памяти лишь строку s + # и значение префикс-функции на ней, а потом уже считывать по одному символу строку t и пересчитывать текущее значение префикс-функции.

Итак, алгоритм Кнута-Морриса-Пратта решает эту задачу за O(n+m) времени и O(n) памяти.

К оглавлению

Лекция №13. Стек. Автоматическое тестирование функций модуля (библиотека doctest). Проверка корректности скобочной последовательности. Обратная и прямая Польская нотация. Стековый калькулятор. Алгоритм сортировочной станции Дейкстры

Стек или очередь LIFO

last in, first out, «последним пришёл — первым ушёл»

Модуль описывающий структуру данных — стек

"""
Модуль, описывающий структуру данных - стек
>>> clear()
>>> is_empty()
True
>>> push(1)
>>> push(2)
>>> push(3)
>>> is_empty()
False
>>> pop()
3
>>> pop()
2
>>> pop()
1
>>> is_empty()
True
"""

_stack = []

def push(x):
    """
    Добавляет элемент х в конец стека
    >>> size = len(_stack)
    >>> push(5)
    >>> len(_stack) - size
    1
    >>> _stack[-1]
    5
    """
    _stack.append(x)
    
def pop():
    x = _stack.pop()
    return x
    
def clear():
    _stack.clear()
    
def is_empty():
    return len(_stack) == 0
    
# запускает описанную выше реализацию в ковычках
# встроенное тестирование в языке
# благодаря verbose=True мы включаем отображение всех тестов
# иначе молчаливое, т.е отображает только когда есть ошибки
if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=True)

Result:
Trying:
    clear()
Expecting nothing
ok
Trying:
    is_empty()
Expecting:
    True
ok
Trying:
    push(1)
Expecting nothing
ok
Trying:
    push(2)
Expecting nothing
ok
Trying:
    push(3)
Expecting nothing
ok
Trying:
    is_empty()
Expecting:
    False
ok
Trying:
    pop()
Expecting:
    3
ok
Trying:
    pop()
Expecting:
    2
ok
Trying:
    pop()
Expecting:
    1
ok
Trying:
    is_empty()
Expecting:
    True
ok
Trying:
    size = len(_stack)
Expecting nothing
ok
Trying:
    push(5)
Expecting nothing
ok
Trying:
    len(_stack) - size
Expecting:
    1
ok
Trying:
    _stack[-1]
Expecting:
    5
ok
3 items had no tests:
    __main__.clear
    __main__.is_empty
    __main__.pop
2 items passed all tests:
  10 tests in __main__
   4 tests in __main__.push
14 tests in 5 items.
14 passed and 0 failed.
Test passed.

Проверка корректности скобочной последовательности.

A_stack = []

def is_braces_sequence_correct(s:str):
    """
    Проверяет корректность скобочной последовательности
    из круглых и квадратных скобок () []
    
    >>> is_braces_sequence_correct("(([()]))")
    True
    >>> is_braces_sequence_correct("([)]")
    False
    >>> is_braces_sequence_correct("(")
    False
    >>> is_braces_sequence_correct("]")
    False
    """
    for brace in s:
        if brace not in "()[]":
            continue
        if brace in "([":
            A_stack.push(brace)
        else:
            assert brace in ")]", "Ожидалась закрывающая скобка: " + str(brace)
            if A_stack.is_empty():
                return False
            left = A_stack.pop()
            assert left in "([", "Ожидалась открывающая скобка: " + str(brace)
            if left == "(":
                right = ")"
            elif left == "[":
                right = "]"
            if right != brace:
                return False
    
    return A_stack.is_empty()

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=True)

Обратная и прямая Польская нотация(ОПН)

Арифметические выражения. Инфиксная, постфиксная и префиксная нотации

Рассмотрим арифметическое выражение

(2−3)∗(12−10)+4/2

Его значение легко вычисляется и это 0. Это привычная для нас форма записи арифметических выражений, в которой если операция бинарная (т.е. требует 2 аргументов, например, сложение, деление), то один аргумент пишется перед знаком операции, а другой — после неё. Такая форма записи называется инфиксной.

Нотация (способ записи), в которой операнды пишутся перед знаком операции — называется постфиксной или обратной польской.

Нотация в которой операнды пишутся после знака операции — прямой польской или префиксной.

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

23−1210−∗42/+

После пары 2 и 3 стоит знак вычитания. После пары 12 и 10 — тоже. Далее стоит знак перемножения, потому что результаты этих двух операций надо умножить. Далее стоят 4 и 2 и после них знак деления. А после — знак сложения, показывающий, что результат предыдущего нужно сложить с результатом деления 4 на 2.

а в прямой польской как

+∗−23−1210/42

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

Его конечные вершины, листья (из которых стрелки никуда не идут) — это операнды, а промежуточные (из которых идут стрелки)- операции. Прямая польская запись (префиксная) получается, если читать это дерево сверху вниз. Обратная (постфиксная) — если читать снизу вверх.

import math
import operator

ops = {'+': operator.add,
       '-': operator.sub,
       '*': operator.mul,
       '/': operator.truediv,
       '^': operator.pow,
       'sin': math.sin,
       'tan': math.tan,
       'cos': math.cos,
       'pi': math.pi}

def is_number(s):
    try:
        float(s)
        return True
    except ValueError:
        pass

def calculate(equation):
    stack = []
    result = 0
    for token in equation:
        if is_number(token):
            stack.insert(0, token)
        else:
            if len(stack) < 2:
                print('Error: insufficient values in expression')
                break
            else:
                print('stack: %s' % stack)
                if len(token) == 1:
                    n1 = float(stack.pop(1))
                    n2 = float(stack.pop(0))
                    result = ops[token](n1, n2)
                    stack.insert(0, str(result))
                else:
                    n1 = float(stack.pop(0))
                    result = ops[token](math.radians(n1))
                    stack.insert(0, str(result))
    return result

def main():
    running = True
    while running:
        equation = input('enter the equation: ').split(' ')
        answer = calculate(equation)
        print('RESULT: %f' % answer)
        again = input('nEnter another? ')[0].upper()
        if again != 'Y':
            running = False

if __name__ == '__main__':
    main()

Result:
enter the equation: 2 3 +
stack: ['3', '2']
RESULT: 5.000000

Enter another? Y
enter the equation: 2 5 7 * +
stack: ['7', '5', '2']
stack: ['35.0', '2']
RESULT: 37.000000

Enter another? 

Стековый калькулятор — это устройство (реальное или виртуальное), которрое вычисляет значения арифметических выражений , записанный в постфиксной форме. Стековым он называется по понятным причинам: если нам встречается число — мы должны поместить его в стек; если знак операции — мы должны достать из стека столько чиссел, сколько необходимо для выполнения данной операции. Именно так и работает т.н. математический сопроцессор (например, в INtel8086+AMD64) — часть ЦП, отвечающая за операции над числами с плавающей запятой.

Сортировочная станция Дейкстры

Как нетрудно видеть: выражения в обратной польской записи удобны для чтения компьютером , но неудобны для чтения и составления людьми. Поэтому хотелось бы доверить труд составления постфиксной формы выражений по их привычной инфиксной форме компьютеру. Это можно сделать с помощью так называемого алгоритма сортировочной станции, «Shunting Yard algorithm», придуман Э. Дейкстрой в 1961 году, для трансляторов языка Algol60.

Алгоритм сортировочной станции — способ разбора математических выражений, представленных в инфиксной нотации. Может быть использован для получения вывода в виде обратной польской нотации или в виде абстрактного синтаксического дерева. Алгоритм предложен Эдсгером Дейкстрой и назван им «алгоритм сортировочной станции», поскольку напоминает действие железнодорожной сортировочной станции.

Так же, как и вычисление значений выражений в обратной польской записи, алгоритм работает при помощи стека. Инфиксная запись математических выражений чаще всего используется людьми, её примеры: 2+4 и 3+6*(3-2). Для преобразования в обратную польскую нотацию используется 2 строки: входная и выходная, и стек для хранения операторов, еще не добавленных в выходную очередь. При преобразовании алгоритм считывает 1 символ и производит действия, зависящие от данного символа.

В следующем примере, разбирается преобразование выражения

a+b∗c−d

Есть сортировочная станция с 3 путями: 2 подъездных и 1 тупик. С правого подъездного пути едут выражения: в каждом «вагоне» или операнд или знак операции. Операнды свободно проезжают в левый путь (образуя очередь), а операторы заезжают в тупик.

Если приоритет входящего оператора ниже приоритета того, что навершине стека (на входе в тупик), то из стека достаётся оператор с большим приоритетом (на шаге g это умножение). То же самое происходит, если приооритет приходящего оператора равен приоритету такового на вершине стека, но тот, что на вершине — ассоциативен. В данном случае после отъезда умножения остаётся сложение, приоритет которого равен приоритету вычитания, но сложение в отличие от вычитания ассоциативно:

(a+b)+с=a+(b+c)(a−b)−c!=a−(b−c)=a−b+c

Эдсгер Вибе Дейкстра

Алгоритм сортировочной станции or eng version

Реализации

Текстовый вариант алгоритма

-Пока не все токены обработаны:
	*Прочитать токен.
	*Если токен — число, то добавить его в очередь вывода.
	*Если токен — функция, то поместить его в стек.
	*Если токен — разделитель аргументов функции (например запятая):
		*Пока токен на вершине стека не открывающая скобка: 
			*Переложить оператор из стека в выходную очередь.
			*Если стек закончился до того, как был встречен токен открывающая скобка,
			то в выражении пропущен разделитель аргументов функции (запятая), 
			либо пропущена открывающая скобка.
	*Если токен — оператор op1, то:
		*Пока присутствует на вершине стека токен оператор op2, чей приоритет выше 
		или равен приоритету op1, и при равенстве
		приоритетов op1 является левоассоциативным:
			*Переложить op2 из стека в выходную очередь;
		*Положить op1 в стек.
	*Если токен — открывающая скобка, то положить его в стек.
	*Если токен — закрывающая скобка:
		*Пока токен на вершине стека не открывающая скобка
			*Переложить оператор из стека в выходную очередь.
			*Если стек закончился до того, как был встречен токен
			открывающая скобка, то в выражении пропущена скобка.
		*Выкинуть открывающую скобку из стека, но не добавлять в очередь вывода.
		*Если токен на вершине стека — функция, переложить её в выходную очередь.
-Если больше не осталось токенов на входе:
	*Пока есть токены операторы в стеке:
		*Если токен оператор на вершине стека — открывающая скобка,
		то в выражении пропущена скобка.
		*Переложить оператор из стека в выходную очередь.
-Конец.

Каждый токен-число, функция или оператор выводится только один раз, а также каждый токен-функция, оператор или круглая скобка будет добавлен и удален из стека по одному разу. Постоянное количество операций на токен, линейная сложность алгоритма O(n).

К оглавлению

Лекция №14. Тип list. Изменяемость списка. Тип кортежа tuple как замороженный список. Насколько не изменяем кортеж?. Список кортежей и цикл for с двумя переменными. Тип строк str. Неизменяемость строки. Методы строки find, count, replace. Срезы строк и списков. Присваивание в срез списка. Стандартные функции len, max, min, sum. Методы split и join. Структура данных Куча/Пирамида (Heap)

Тип list

Список — это список ссылок на произвольные (неоднотипные) объекты. Изменяемый.

Как таковых переменных нет в Питоне, есть объекты и имена. Объекты живут до тех пор, пока где-нибудь на них хранится еще ссылка. Например в каком-нибудь имени. Как только ссылка на объект пропадает, сборщик мусора съедает объект. Ссылка на объект может хранить в списке еще.

Тип кортежа tuple как замороженный список. Насколько не изменяем кортеж?. Список кортежей и цикл for с двумя переменными.

Кортеж — это замороженный список, тоже может хранить разнотипные объекты. Не изменяемый тип.

Объект не может изменить свой тип, в процессе своей жизни. В Питоне все является объектом. Все типы в Питоне это классы, даже функция это объект класса.

Лучше кортежи погружать в списки.
Можно кортежем переменных бежать по списку при переборе в цикле for. Даже без скобок у кортежа подразумевается сам кортеж, так как объекты через запятую.

Тип строк str

Можно закомментировать код с помощью # и двойных кавычек 3 шт «»»…»»». Но так делать не есть хорошо.

Можно разделять большие числа знаком _, к примеру номер банковской карты.

Символ экранирования

Строка является неизменяемым типом. Созданная единожды такой и является. Строку изменить нельзя. Нельзя присваивать в строчку новые значения. Питон кодирует строку в UTF-8 и символы в строке могут занимать разное количество байт (китайские или корейские слова и тп).

Срезы строк и списков.

Символ — это строка состоящая из одного символа, и у него строковый тип.

Срез так же как и функция range имеет s = [start (начало): stop(не достигаемый индекс, невключаемый): step(шаг)]

Срез строки это строка.

Присваивание в срез списка.

срезы для строк, прекрасно работают и для списков
s = [:] можно создать новый список на основе существующего списка

При взятии среза сам список не меняется.

Срез списка это новый список.

Питон умеет посимвольно сравнивать списки и строки на оператор == , >, <(лексикогрофически, и по длине)

У среза с 2 параметрами ошибок не будет, даже если он не попадает в диапозон и там нет чисел, получим просто пустой срез.

Куча/Пирамида (Heap)

К оглавлению

Лекция №16. Асимптотика алгоритмов (потребление ресурсов) . Индуктивные функции. Однопроходные алгоритмы. NP — полные задачи. Тест простоты Ферма. Числа Кармайкла. Алгоритм шифрования RSA

Классификация алгоритмов, входные данные, значение на выходе

Индуктивные функции. Однопроходные алгоритмы

Индуктивное умозаключение — это процесс логического вывода на основе перехода от частного положения к общему.

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

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

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

F — большая и будет индуктивной функцией, она обеспечивает индукцию, т.е мы вычисляем маленькую последовательность и на ее основе (индуктивной функции) уже вычисляем другую последовательность. Среднеарифметическое нельзя вычислить по старому + новое зачение, таким образом, но есть другие варианты применения.

Асимптотика алгоритма -> потребление алгоритмом ресурсов

1 Вопрос: вычислима ли функция?

2 Вопрос. Сколько потребляет ресурсов алгоритм?

Количество операций N пропорционально T времени работы.
Время работы = время выполнения 1 операции * на кол-во операций

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

N по графику это масштаб задачи, Nоп — кол-во операции (для сортировок это количество входных чисел).

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

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

O(n) — линейная сложность
Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) — логарифмическая сложность
Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n^2) — квадратичная сложность
Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n, т. е. n^2.

О асимптотике нагляднo

Асимптотический анализ

Когда мы говорим об измерении сложности алгоритмов, мы подразумеваем анализ времени, которое потребуется для обработки очень большого набора данных. Такой анализ называют асимптотическим. Сколько времени потребуется на обработку массива из десяти элементов? Тысячи? Десяти миллионов? Если алгоритм обрабатывает тысячу элементов за пять миллисекунд, что случится, если мы передадим в него миллион? Будет ли он выполняться пять минут или пять лет?

Порядок роста описывает то, как сложность алгоритма растет с увеличением размера входных данных. Чаще всего он представлен в виде O-нотации (от нем. «Ordnung» — порядок) : O(f(x)), где f(x) — формула, выражающая сложность алгоритма. В формуле может присутствовать переменная n, представляющая размер входных данных. Ниже приводится список наиболее часто встречающихся порядков роста, но он ни в коем случае не полный.

Константный — O(1)

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

public int GetCount(int[] items)
{
    return items.Length;
}

Линейный — O(n)

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

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

public long GetSum(int[] items)
{
    long sum = 0;
    foreach (int i in items)
    {
        sum += i;
    }

    return sum;
}

Логарифмический — O( log n)
Порядок роста O( log n) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. (анализе алгоритмов по умолчанию используется логарифм по основанию 2). Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность. Метод Contains бинарного дерева поиска (binary search tree) также имеет порядок роста O(log n).

Линеарифметический — O(n·log n)
Линеарифметический (или линейно-логарифмический) алгоритм имеет порядок роста O(n·log n). Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию, + сортировка слиянием и быстрая сортировка.

Квадратичный — O(n^2)
Время работы алгоритма с порядком роста O(n^2) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность — повод пересмотреть используемые алгоритмы или структуры данных. Проблема в том, что они плохо масштабируются. Например, если массив из тысячи элементов потребует 1 000 000 операций, массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, квадратичный алгоритм будет обрабатывать миллион элементов 32 года. Даже если он будет в сто раз быстрее, работа займет 84 дня.

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

Наилучший, средний и наихудший случаи
Что мы имеем в виду, когда говорим, что порядок роста сложности алгоритма — O(n)

Обычно имеется в виду наихудший случай, за исключением тех случаев, когда наихудший и средний сильно отличаются. К примеру, мы увидим примеры алгоритмов, которые в среднем имеют порядок роста O(1), но периодически могут становиться O(n) (например, ArrayList.add). В этом случае мы будем указывать, что алгоритм работает в среднем за константное время, и объяснять случаи, когда сложность возрастает.

Самое важное здесь то, что O(n) означает, что алгоритм потребует не более n шагов.

Что мы измеряем?
При измерении сложности алгоритмов и структур данных мы обычно говорим о двух вещах: количество операций, требуемых для завершения работы (вычислительная сложность), и объем ресурсов, в частности, памяти, который необходим алгоритму (пространственная сложность).

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

Операции, количество которых мы будем измерять, включают в себя:

• сравнения («больше», «меньше», «равно»);
• присваивания;
• выделение памяти.

То, какие операции мы учитываем, обычно ясно из контекста.

К примеру, при описании алгоритма поиска элемента в структуре данных мы почти наверняка имеем в виду операции сравнения. Поиск — это преимущественно процесс чтения, так что нет смысла делать присваивания или выделение памяти.

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

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

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

Пространственная сложность — зависимость количества занимаемой памяти от размера входных данных.
Пример: «почистить ковёр пылесосом»

Классы сложности

Класс P — вмещает все те проблемы, решение которых считается «быстрым», то есть время решения которых полиномиально зависит от размера входа. Сюда относится сортировка, поиск в массиве, выяснение связности графов и многие другие.

Класс NP — содержит задачи, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество шагов от размера входных данных.

NP — полные задачи, не имеющие решения.

Оценка сложности алгоритмов

• O(n) — линейная сложность (алгоритм поиска наибольшего элемента в не отсортированном массиве
• O(log n) — логарифмическая сложность (бинарный поиск)
• O(n^2) — квадратичная сложность (алгоритм сортировки вставками)

Сложность алгоритмов

Списки (lists)

O(1) - класс сложности имеют операции, которые выполняются за константное время, например, создание переменной или сложение небольших чисел.

Получение элемента: l[i]

Сохранение элемента l[i] = 0

Размер списка len(l)

Добавление элемента в конец списка l.append(5)

Удаление последнего элемента (pop) l.pop()

Очищение списка l.clear() O(1)

O(b-a), где a и b - границы среза.

Получение среза l[a:b]

O(len(...))

Расширение l.extend(...)

Создание list(...)

O(N)

Сравнение списков (==, !=) l_1 == l_2

Вставка l[a:b] = ...

Удаление элемента (del) del l[i]

Проверка наличия x in/not in l

Копирование l.copy()

Удаление значения (remove) l.remove(...)

Удаление элемента (pop) l.pop(i)

Получение минимального/максимального значения min(l)/max(l)

Разворачивание списка l.reverse()

Перебор for v in l:

O(N Log N)

Сортировка l.sort()

Множества (sets)

O(1) - класс сложности имеют операции, которые выполняются за константное время, например, создание переменной или сложение небольших чисел.

Размер множества len(s)

Добавление элемента s.add(5)

Проверка наличия значения x in/not in s

Удаление значения (remove) s.remove(..)

Удаление значения (discard) s.discard(..)

Удаление значения (pop) s.pop()

Очищение множества s.clear()

O(len(...))

Создание set(...)

Сравнение множеств (==, !=) s != t O(len(s))

Сравнение множеств (<=/<) s <= t O(len(s))

Сравнение множеств (>=/>) s >= t O(len(t))

O(len(s)+len(t))

Объединение (union) s | t

Пересечение (intersection) s & t

Разность (difference) s – t

Симметричная разность s ^ 

O(N)

Перебор множества for v in s:

Копирование s.copy()

Словари (dict и defaultdict)

O(1)

Получение элемента d[k]

Сохранение элемента d[k] = v

Размер словаря len(d)

Удаление элемента (del) del d[k]

get/setdefault d.get(k)

Удаление (pop) d.pop(k)

Удаление (popitem) d.popitem()

Очищение словаря d.clear()

Получение ключей d.keys()

O(len(...))

Создание словаря dict(...)

O(N)

Перебор элементов for k in d:

Тест простоты Ферма

Для любого простого числа P и для любого натурального числа a, при этом P не является делителем a, a не кратно P т.е не содержит P среди своих делителей. a в степени P-1 равно 1 по модулю mod P.

число (a в степени P-1) % P (взятие остатка) = 1

Чтобы опеределить простое ли число (огромные числа в тысячи знаков), проверяем тестом Ферма, если подтверждается, то доказываем разбором на множители этого числа (так как вероятность высока, что число простое, но не 100%)

Числа Кармайкла — последовательность чисел, которые не являются простыми, они составные, НО удовлетворяют теореме простоты числа Ферма.

Алгоритм шифрования RSA — основан на этой теореме, как и вся цифровая безопасность сейчас. Разложение на множители огромных чисел в тысячи знаков.

Список (list). Вспомним операции работы со списками.

У разработчиков типа данных list Python было много вариантов каким сделать его во время реализации. Каждый выбор повлиял на то, как быстро список мог выполнять операции. Одно из решений было сделать список оптимальным для частых операций.

Индексирование и присваивание

Две частые операции — индексирование и присваивание на позицию индекса. В списках Python значения присваиваются и извлекаются из определенных известных мест памяти. Независимо от того, насколько велик список, индексный поиск и присвоение занимают постоянное количество времени и, таким образом их трудоемкость O(1).

Pop, Shift, Delete

Извлечение элемента (pop) из списка Python по умолчанию выполняется с конца, но, передавая индекс, вы можете получить элемент из определенной позиции. Когда pop вызывается с конца, операция имеет сложность O(1) , а вызов pop из любого места — O(n). Откуда такая разница?

Когда элемент берется из середины списка Python, все остальные элементы в списке сдвигаются на одну позицию ближе к началу. Это суровая плата за возможность брать индекс за O(1), что является более частой операцией.

По тем же причинам вставка в индекс — O(N); каждый последующий элемент должен быть сдвинут на одну позицию ближе к концу, чтобы разместить новый элемент. Неудивительно, что удаление ведет себя таким же образом.

Итерирование

Итерирование выполняется за O(N), потому что для итерации по N элементам требуется N шагов. Это также объясняет, почему оператор in, max, min в Python является O(N) : чтобы определить, находится ли элемент в списке, мы должны перебирать каждый элемент.

Срезы

Чтобы получить доступ к фрагменту [a: b] списка, мы должны перебрать каждый элемент между индексами a и b. Таким образом, доступ к срезу — O(k), где k — размер среза. Удаление среза O(N) по той же причине, что удаление одного элемента — O(N): N последующих элементов должны быть смещены в сторону начала списка.

Умножение на int

Чтобы понять умножение списка на целое k, вспомним, что конкатенация выполняется за O(M), где M — длина добавленного списка. Из этого следует, что умножение списка равно O(N k), так как умножение k-размера списка N раз потребует времени k (N-1).

Разворот списка — это O(N), так как мы должны переместить каждый элемент.

Множество (set)

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

Действия, которые можно выполнять с множеством:

• добавлять и удалять элементы,
• проверять принадлежность элемента множеству,
• перебирать его элементы,
• выполнять операции над множествами (объединение, пересечение, разность).

Операция “проверить принадлежность элемента” выполняется в множестве намного быстрее, чем в списке.

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

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

Задание множеств

Множество задается перечислением в фигурных скобках. Например:

Исключением явлеется пустое множество:

A = set()       # A -- множество
D = {}          # D -- не пустое множество, а пустой словарь!

Если функции set передать в качестве параметра список, строку или кортеж, то она вернет множество, составленное из элементов списка, строки, кортежа. Например:

>>> A = set('qwerty')
>>> print(A)
{'e', 'q', 'r', 't', 'w', 'y'}

Каждый элемент может входить в множество только один раз.

>>> A = {1, 2, 3}
>>> B = {3, 2, 3, 1}
>>> print(A == B) # A и B — равные множества.
True
>>> set('Hello')
{'H', 'e', 'l', 'o'}

Работа с элементами множеств

Как мы видим, по времени стандартные оперцаии с одним элементом множества выполняются за O(1).

Поведение discard и remove различается тогда, когда удаляемый элемент отсутствует в множестве: discard не делает ничего, а метод remove генерирует исключение KeyError. Метод pop также генерирует исключение KeyError, если множество пусто.

При помощи цикла for можно перебрать все элементы множества:

Primes = {2, 3, 5, 7, 11}
for num im Primes:
    print(num)

Из множества можно сделать список при помощи функции list:

>>> A = {1, 2, 3, 4, 5}
>>> B = list(A)
[1, 2, 3, 4, 5]