Скачивать python будем с официального сайта. Кстати, не рекомендую скачивать интерпретатор python с других сайтов или через торрент, в них могут быть вирусы. Программа бесплатная. Заходим на https://python.org/downloads/windows/, выбираем "latest python release" и python 3.



На момент написания статьи это python 3.5.1.



Появляется страница с описанием данной версии Python (на английском). Если интересно - можете почитать. Затем крутим в самый низ страницы, а затем открываем "download page".



Вы увидите список файлов, которые можно загрузить. Нам нужен Windows x86 MSI installer (если система 32-х битная), или Windows x86-64 MSI installer (если система 64-х битная). Больше из файлов нам ничего не нужно.



Ждём, пока python загрузится. Затем открываем загрузившийся файл. Файл подписан Python Software Foundation, значит, все в порядке. Пользуясь случаем, напоминаю, что не стоит открывать незнакомые exe файлы.



Устанавливаем для всех пользователей или только для одного (на ваше усмотрение).



Выбираем папку для установки. Я оставляю папку по умолчанию. Вы можете выбрать любую папку на своем диске.



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



Ждем установки python...

Finish. Поздравляю, вы установили Python! Также в установщик python для windows встроена среда разработки IDLE. Прямо сейчас вы можете написать свою первую программу!



Откройте консоль (обычно ctrl+alt+t). Введите в консоли:



Скорее всего, вас любезно поприветствует python 3:



Если это так, то можно вас поздравить: у вас уже стоит python 3. В противном случае нужно установить пакет *python3*:



Либо через mintinstaller / synaptic / центр приложений ubuntu / что вам больше нравится.

В python для linux нет предустановленной среды IDLE. Если хотите, её можно установить отдельно. Пакет называется *python3-idle*.

Однако, её установка не является обязательной. Вы можете писать в своём любимом текстовом редакторе (gedit, vim, emacs...) и запускать программы через консоль:



Теперь вы можете написать первую программу (хотите, пишите в IDLE, хотите - в своём любимом текстовом редакторе).

Python 3 — это современный язык, на котором просто и приятно писать программы.

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


Для ввода данных в программу мы используем функцию input(). Она считывает одну строку.

Вот программа, которая считывает имя пользователя и приветствует его:


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

Попробуем написать программу, которая считывает два числа и выводит их сумму. Для этого считаем два числа и сохраним их в переменные a и b, пользуясь оператором присваивания =. Слева от оператора присваивания в программах на Питоне ставится имя переменной — например, строка из латинских букв. Справа от оператора присваивания ставится любое выражение. Имя станет указывать на результат вычисления выражения. Проиграйте эту программу и посмотрите на результаты её работы:


Мы видим, что программа выводит 57, хотя в реальной жизни 5 + 7 будет 12. Это произошло потому, что Питон в третьей строчке «сложил» две строки, а не два числа. В Питоне две строки складываются так: к первой строке приписывается вторая.

Обратите внимание, что в визуализаторе содержимое переменных a и b заключено в кавычки. Это означает, что в a и b лежат строки, а не числа.

В Питоне все данные называются объектами. Число 2 представляется объектом «число 2», строка 'hello' – это объект «строка 'hello'».

Каждый объект относится к какому-то типу. Строки хранятся в объектах типа str, целые числа хранятся в объектах типа int, дробные числа (вещественные числа) — в объектах типа float. Тип объекта определяет, какие действия можно делать с объектами этого типа. Например, если в переменных first и second лежат объекты типа int, то их можно перемножить, а если в них лежат объекты типа str, то их перемножить нельзя:


Чтобы преобразовать строку из цифр в целое число, воспользуемся функцией int(). Например, int('23') вернет число 23.

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

1. Синтаксис условной инструкции
Все ранее рассматриваемые программы имели линейную структуру: все инструкции выполнялись последовательно одна за одной, каждая записанная инструкция обязательно выполняется.

Допустим мы хотим по данному числу x определить его абсолютную величину (модуль). Программа должна напечатать значение переменной x, если x>0 или же величину -x в противном случае. Линейная структура программы нарушается: в зависимости от справедливости условия x>0 должна быть выведена одна или другая величина. Соответствующий фрагмент программы на Питоне имеет вид:


В этой программе используется условная инструкция if (если). После слова if указывается проверяемое условие (x > 0), завершающееся двоеточием. После этого идет блок (последовательность) инструкций, который будет выполнен, если условие истинно, в нашем примере это вывод на экран величины x. Затем идет слово else (иначе), также завершающееся двоеточием, и блок инструкций, который будет выполнен, если проверяемое условие неверно, в данном случае будет выведено значение -x.

Итак, условная инструкция в Питоне имеет следующий синтаксис:


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

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


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

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

Это одно из существенных отличий синтаксиса Питона от синтаксиса большинства языков, в которых блоки выделяются специальными словами, например, нц... кц в Кумире, begin... end в Паскале или фигурными скобками в Си.

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


В этом примере мы использовали комментарии – текст, который интерпретатор игнорирует. Комментариями в Питоне является символ # и весь текст после этого символа до конца строки.

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

<
Меньше — условие верно, если первый операнд меньше второго.
>
Больше — условие верно, если первый операнд больше второго.
<=
Меньше или равно.
>=
Больше или равно.
==
Равенство. Условие верно, если два операнда равны.
!=
Неравенство. Условие верно, если два операнда неравны.
Например, условие (x * x < 1000) означает “значение x * x меньше 1000”, а условие (2 * x != y) означает “удвоенное значение переменной x не равно значению переменной y”.

Операторы сравнения в Питоне можно объединять в цепочки (в отличии от большинства других языков программирования, где для этого нужно использовать логические связки), например, a == b == c или 1 <= x <= 10.

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

4.1. Логические операторы
Иногда нужно проверить одновременно не одно, а несколько условий. Например, проверить, является ли данное число четным можно при помощи условия (n % 2 == 0) (остаток от деления n на 2 равен 0), а если необходимо проверить, что два данных целых числа n и m являются четными, необходимо проверить справедливость обоих условий: n % 2 == 0 и m % 2 == 0, для чего их необходимо объединить при помощи оператора and (логическое И): n % 2 == 0 and m % 2 == 0.

В Питоне существуют стандартные логические операторы: логическое И, логическое ИЛИ, логическое отрицание.

Логическое И является бинарным оператором (то есть оператором с двумя операндами: левым и правым) и имеет вид and. Оператор and возвращает True тогда и только тогда, когда оба его операнда имеют значение True.

Логическое ИЛИ является бинарным оператором и возвращает True тогда и только тогда, когда хотя бы один операнд равен True. Оператор “логическое ИЛИ” имеет вид or.

Логическое НЕ (отрицание) является унарным (то есть с одним операндом) оператором и имеет вид not, за которым следует единственный операнд. Логическое НЕ возвращает True, если операнд равен False и наоборот.

Пример. Проверим, что хотя бы одно из чисел a или b оканчивается на 0:


Проверим, что число a — положительное, а b — неотрицательное:


Или можно вместо not (b < 0) записать (b >= 0).

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


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

1. Целочисленная арифметика
Для целых чисел определены операции +, -, * и **. Операция деления / для целых чисел возвращает вещественное число (значение типа float). Также функция возведения в степень возвращает значение типа float, если показатель степени — отрицательное число.

Но есть и специальная операция целочисленного деления, выполняющегося с отбрасыванием дробной части, которая обозначается // (она соответствует операции div в Паскале). Она возвращает целое число: целую часть частного. Другая близкая ей операция − это операция взятия остатка от деления, обозначаемая % (она соответствует операции mod в Паскале). Например:


2. Действительные числа
В этом разделе речь пойдет о действительных числах, имеющих тип float.

Обратите внимание, что если вы хотите считать с клавиатуры действительное число, то результат, возращаемый функцией input() необходимо преобразовывать к типу float:


Действительные (вещественные) числа представляются в виде чисел с десятичной точкой (а не запятой, как принято при записи десятичных дробей в русский текстах). Для записи очень больших или очень маленьких по модулю чисел используется так называемая запись «с плавающей точкой» (также называемая «научная» запись). В этом случае число представляется в виде некоторой десятичной дроби, называемой мантиссой, умноженной на целочисленную степень десяти (порядок). Например, расстояние от Земли до Солнца равно 1.496·1011, а масса молекулы воды 2.99·10-23.

Числа с плавающей точкой в программах на языке Питон, а также при вводе и выводе записываются так: сначала пишется мантисса, затем пишется буква e, затем пишется порядок. Пробелы внутри этой записи не ставятся. Например, указанные выше константы можно записать в виде 1.496e11 и 2.99e-23. Перед самим числом также может стоять знак минус.

Напомним, что результатом операции деления / всегда является действительное число (float), в то время как результатом операции // является целое число (int).

Преобразование действительных чисел к целому производится с округлением в сторону нуля, то есть int(1.7) == 1, int(-1.7) == -1.

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

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


Например, пусть мы хотим округлять вещественные числа до ближайшего целого числа вверх. Соответствующая функция ceil от одного аргумента вызывается, например, так: math.ceil(x) (то есть явно указывается, что из модуля math используется функция ceil). Вместо числа x может быть любое число, переменная или выражение. Функция возращает значение, которое можно вывести на экран, присвоить другой переменной или использовать в выражении:


Другой способ использовать функции из библиотеки math, при котором не нужно будет при каждом использовании функции из модуля math указывать название этого модуля, выглядит так:


или так:


Ниже приведен список основных функций модуля math. Более подробное описание этих функций можно найти на сайте с документацией языка Питон.

Некоторые из перечисленных функций (int, round, abs) являются стандартными и не требуют подключения модуля math для использования.

1. Цикл for
Цикл for, также называемый циклом с параметром, в языке Питон богат возможностями. В цикле for указывается переменная и множество значений, по которому будет пробегать переменная. Множество значений может быть задано списком, кортежем, строкой или диапазоном.

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


В этом примере переменная color последовательно принимает значения 'red', 'orange' и т.д. В теле цикла выводится сообщение, которое содержит название цвета, то есть значение переменной color, а также номер итерации цикла число, которое сначала равно 1, а потом увеличивается на один (инструкцией i += 1 с каждым проходом цикла. Инструкция i += 1 эквивалентна конструкции i = i + 1 (это просто сокращенная запись).

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


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

2. Функция range
Как правило, циклы for используются либо для повторения какой-либо последовательности действий заданное число раз, либо для изменения значения переменной в цикле от некоторого начального значения до некоторого конечного.

Для повторения цикла некоторое заданное число раз n можно использовать цикл for вместе с функцией range:


В качестве n может использоваться числовая константа, переменная или произвольное арифметическое выражение (например, 2 ** 10). Если значение n равно нулю или отрицательное, то тело цикла не выполнится ни разу.

Функция range может также принимать не один, а два параметра. Вызов range(a, b) означает, что индексная переменная будеть принимать значения от a до b - 1, то есть первый параметр функции range, вызываемой с двумя параметрами, задает начальное значение индексной переменной, а второй параметр — первое значение, которое индексная переменная принимать не будет. Если же a≥b, то цикл не будет выполнен ни разу. Например, для того, чтобы просуммировать значения чисел от 1 до n можно воспользоваться следующей программой:


В этом примере переменная i принимает значения 1, 2, ..., n, и значение переменной sum последовательно увеличивается на указанные значения.

Наконец, чтобы организовать цикл, в котором индексная переменная будет уменьшаться, необходимо использовать функцию range с тремя параметрами. Первый параметр задает начальное значение индексной переменной, второй параметр — значение, до которого будет изменяться индексная переменная (не включая его!), а третий параметр — величину изменения индексной переменной. Например, сделать цикл по всем нечетным числам от 1 до 99 можно при помощи функции range(1, 100, 2), а сделать цикл по всем числам от 100 до 1 можно при помощи range(100, 0, -1).

Более формально, цикл for i in range(a, b, d) при d > 0 задает значения индексной переменной i = a, i = a + d, i = a + 2 * d и так для всех значений, для которых i < b. Если же d < 0, то переменная цикла принимает все значения i > b.

3. Настройка функции print()
По умолчанию функция print() принимает несколько аргументов, выводит их через пробел, после чего ставит перевод строки. Это поведение можно изменить, используя именованные параметры sep (разделитель) и end (окончание).

1. Строки
Строка считывается со стандартного ввода функцией input(). Напомним, что для двух строк определена операция сложения (конкатенации), также определена операция умножения строки на число.

Строка состоит из последовательности символов. Узнать количество символов (длину строки) можно при помощи функции len.

Любой другой объект в Питоне можно перевести к строке, которая ему соответствуюет. Для этого нужно вызвать функцию str(), передав ей в качестве параметра объект, переводимый в строку.

На самом деле каждая строка, с точки зрения Питона, — это объект класса str. Чтобы получить по объекту другой объект другого класса, как-то ему соответствующий, можно использовать функцию приведения. Имя этой функции совпадает с именем класса, к которому мы приводим объект. (Для знатоков: эта функция — это конструктор объектов данного класса.) Пример: int — класс для целых чисел. Перевод строки в число осуществляется функцией int().


2. Срезы (slices)
Срез (slice) — извлечение из данной строки одного символа или некоторого фрагмента подстроки или подпоследовательности.

Есть три формы срезов. Самая простая форма среза: взятие одного символа строки, а именно, S — это срез, состоящий из одного символа, который имеет номер i. При этом считается, что нумерация начинается с числа 0. То есть если S = 'Hello', то S[0] == 'H', S[1] == 'e', S[2] == 'l', S[3] == 'l', S[4] == 'o'.

Заметим, что в Питоне нет отдельного типа для символов строки. Каждый объект, который получается в результате среза S — это тоже строка типа str.
Номера символов в строке (а также в других структурах данных: списках, кортежах) называются индексом.

Если указать отрицательное значение индекса, то номер будет отсчитываться с конца, начиная с номера -1. То есть S[-1] == 'o', S[-2] == 'l', S[-3] == 'l', S[-4] == 'e', S[-5] == 'H'.

Или в виде таблицы:


Если же номер символа в срезе строки S больше либо равен len(S), или меньше, чем -len(S), то при обращении к этому символу строки произойдет ошибка IndexError: string index out of range.

Срез с двумя параметрами: S[a:b] возвращает подстроку из b - a символов, начиная с символа c индексом a, то есть до символа с индексом b, не включая его. Например, S[1:4] == 'ell', то же самое получится если написать S[-4:-1]. Можно использовать как положительные, так и отрицательные индексы в одном срезе, например, S[1:-1] — это строка без первого и последнего символа (срез начинается с символа с индексом 1 и заканчиватеся индексом -1, не включая его).

При использовании такой формы среза ошибки IndexError никогда не возникает. Например, срез S[1:5] вернет строку 'ello', таким же будет результат, если сделать второй индекс очень большим, например, S[1:100] (если в строке не более 100 символов).

Если опустить второй параметр (но поставить двоеточие), то срез берется до конца строки. Например, чтобы удалить из строки первый символ (его индекс равен 0), можно взять срез S[1:]. Аналогично если опустить первый параметр, то можно взять срез от начала строки. То есть удалить из строки последний символ можно при помощи среза S[:-1]. Срез S[:] совпадает с самой строкой S.

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

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

Если задать срез с тремя параметрами S[a:b:d], то третий параметр задает шаг, как в случае с функцией range, то есть будут взяты символы с индексами a, a + d, a + 2 * d и т. д. При задании значения третьего параметра, равному 2, в срез попадет кажый второй символ, а если взять значение среза, равное -1, то символы будут идти в обратном порядке. Например, можно перевернуть строку срезом S[::-1].


Обратите внимание на то, как похож третий параметр среза на третий параметр функции range():


3. Методы
Метод — это функция, применяемая к объекту, в данном случае — к строке. Метод вызывается в виде Имя_объекта.Имя_метода(параметры). Например, S.find("e") — это применение к строке S метода find с одним параметром "e".

3.1. Методы find и rfind
Метод find находит в данной строке (к которой применяется метод) данную подстроку (которая передается в качестве параметра). Функция возвращает индекс первого вхождения искомой подстроки. Если же подстрока не найдена, то метод возвращает значение -1.


Аналогично, метод rfind возвращает индекс последнего вхождения данной строки (“поиск справа”).


Если вызвать метод find с тремя параметрами S.find(T, a, b), то поиск будет осуществляться в срезе S[a:b]. Если указать только два параметра S.find(T, a), то поиск будет осуществляться в срезе S[a:], то есть начиная с символа с индексом a и до конца строки. Метод S.find(T, a, b) возращает индекс в строке S, а не индекс относительно среза.

3.2. Метод replace
Метод replace заменяет все вхождения одной строки на другую. Формат: S.replace(old, new) — заменить в строке S все вхождения подстроки old на подстроку new. Пример:


Если методу replace задать еще один параметр: S.replace(old, new, count), то заменены будут не все вхождения, а только не больше, чем первые count из них.


3.3. Метод count
Подсчитывает количество вхождений одной строки в другую строку. Простейшая форма вызова S.count(T) возвращает число вхождений строки T внутри строки S. При этом подсчитываются только непересекающиеся вхождения, например:


При указании трех параметров S.count(T, a, b), будет выполнен подсчет числа вхождений строки T в срезе S[a:b].

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

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


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

Например, следующий фрагмент программы напечатает на экран квадраты всех целых чисел от 1 до 10. Видно, что цикл while может заменять цикл for ... in range(...):


В этом примере переменная i внутри цикла изменяется от 1 до 10. Такая переменная, значение которой меняется с каждым новым проходом цикла, называется счетчиком. Заметим, что после выполнения этого фрагмента значение переменной i будет равно 11, поскольку именно при i == 11 условие i <= 10 впервые перестанет выполняться.

Вот еще один пример использования цикла while для определения количества цифр натурального числа n:


В этом цикле мы отбрасываем по одной цифре числа, начиная с конца, что эквивалентно целочисленному делению на 10 (n //= 10), при этом считаем в переменной length, сколько раз это было сделано.

В языке Питон есть и другой способ решения этой задачи: length = len(str(i)).

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


Казалось бы, никакого смысла в этом нет, ведь эту же инструкцию можно просто написать после окончания цикла. Смысл появляется только вместе с инструкцией break. Если во время выполнения Питон встречает инструкцию break внутри цикла, то он сразу же прекращает выполнение этого цикла и выходит из него. При этом ветка else исполняться не будет. Разумеется, инструкцию break осмыленно вызывать только внутри инструкции if, то есть она должна выполняться только при выполнении какого-то особенного условия.

Приведем пример программы, которая считывает числа до тех пор, пока не встретит отрицательное число. При появлении отрицательного числа программа завершается. В первом варианте последовательность чисел завершается числом 0 (при считывании которого надо остановиться).


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


Другая инструкция управления циклом — continue (продолжение цикла). Если эта инструкция встречается где-то посередине цикла, то пропускаются все оставшиеся инструкции до конца цикла, и исполнение цикла продолжается со следующей итерации.

Если инструкции break и continue содержатся внутри нескольких вложенных циклов, то они влияют лишь на исполнение самого внутреннего цикла. Вот не самый интеллектуальный пример, который это демонстрирует:


Увлечение инструкциями break и continue не поощряется, если можно обойтись без их использования. Вот типичный пример плохого использования инструкции break (данный код считает количество знаков в числе).


Гораздо лучше переписать этот цикл так:


Впрочем, на Питоне можно предложить и более изящное решение:


3. Множественное присваивание
В Питоне можно за одну инструкцию присваивания изменять значение сразу нескольких переменных. Делается это так:


Этот код можно записать и так:


Отличие двух способов состоит в том, что множественное присваивание в первом способе меняет значение двух переменных одновременно.
Если слева от знака «=» в множественном присваивании должны стоять через запятую имена переменных, то справа могут стоять произвольные выражения, разделённые запятыми. Главное, чтобы слева и справа от знака присваивания было одинаковое число элементов.

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


В Питоне то же действие записывается в одну строчку:

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

Раньше мы сталкивались с задачей обработки элементов последовательности, например, вычисляя наибольший элемент последовательности. Но при этом мы не сохраняли всю последовательность в памяти компьютера. Однако, во многих задачах нужно именно сохранять всю последовательность, например, если бы нам требовалось вывести все элементы последовательности в возрастающем порядке (“отсортировать последовательность”).

Для хранения таких данных можно использовать структуру данных, называемую в Питоне список (в большинстве же языков программирования используется другой термин “массив”). Список представляет собой последовательность элементов, пронумерованных от 0, как символы в строке. Список можно задать перечислением элементов списка в квадратных скобках, например, список можно задать так:


В списке Primes — 6 элементов, а именно: Primes[0] == 2, Primes[1] == 3, Primes[2] == 5, Primes[3] == 7, Primes[4] == 11, Primes[5] == 13. Список Rainbow состоит из 7 элементов, каждый из которых является строкой.

Также как и символы в строке, элементы списка можно индексировать отрицательными числами с конца, например, Primes[-1] == 13, Primes[-6] == 2.

Длину списка, то есть количество элементов в нем, можно узнать при помощи функции len, например, len(Primes) == 6.

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


Рассмотрим несколько способов создания и считывания списков. Прежде всего, можно создать пустой список (не содержащий элементов, длины 0), а в конец списка можно добавлять элементы при помощи метода append. Например, пусть программа получает на вход количество элементов в списке n, а потом n элементов списка по одному в отдельной строке. Вот пример входных данных в таком формате:


В этом случае организовать считывание списка можно так:


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


Для списков целиком определены следующие операции: конкатенация списков (сложение списков, т. е. приписывание к одному списку другого) и повторение списков (умножение списка на число). Например:


В результате список c будет равен [1, 2, 3, 4, 5], а список d будет равен [4, 5, 4, 5, 4, 5]. Это позволяет по-другому организовать процесс считывания списков: сначала считать размер списка и создать список из нужного числа элементов, затем организовать цикл по переменной i начиная с числа 0 и внутри цикла считывается i-й элемент списка:


Вывести элементы списка a можно одной инструкцией print(a), при этом будут выведены квадратные скобки вокруг элементов списка и запятые между элементами списка. Такой вывод неудобен, чаще требуется просто вывести все элементы списка в одну строку или по одному элементу в строке. Приведем два примера, также отличающиеся организацией цикла:


Здесь в цикле меняется индекс элемента i, затем выводится элемент списка с индексом i.


В этом примере элементы списка выводятся в одну строку, разделенные пробелом, при этом в цикле меняется не индекс элемента списка, а само значение переменной (например, в цикле for elem in ['red', 'green', 'blue'] переменная elem будет последовательно принимать значения 'red', 'green', 'blue'.

Обратите особое внимание на последний пример! Очень важная часть идеологии Питона — это цикл for, который предоставляет удобный способ перебрать все элементы некоторой последовательности. В этом отличие Питона от Паскаля, где вам обязательно надо перебирать именно индексы элементов, а не сами элементы.
Последовательностями в Питоне являются строки, списки, значения функции range() (это не списки), и ещё кое-какие другие объекты.

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


2. Методы split и join
Элементы списка могут вводиться по одному в строке, в этом случае строку целиком можно считать функцией input(). После этого можно использовать метод строки split(), возвращающий список строк, которые получатся, если исходную строку разрезать на части по пробелам. Пример:


Если при запуске этой программы ввести строку 1 2 3, то список a будет равен ['1', '2', '3']. Обратите внимание, что список будет состоять из строк, а не из чисел. Если хочется получить список именно из чисел, то можно затем элементы списка по одному преобразовать в числа:


Используя специальную магию Питона — генераторы — то же самое можно сделать в одну строку:


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

У метода split() есть необязательный параметр, который определяет, какая строка будет использоваться в качестве разделителя между элементами списка. Например, вызов метода split('.') вернет список, полученный разрезанием исходной строки по символам '.':


В Питоне можно вывести список строк при помощи однострочной команды. Для этого используется метод строки join. У этого метода один параметр: список строк. В результате возвращается строка, полученная соединением элементов переданного списка в одну строку, при этом между элементами списка вставляется разделитель, равный той строке, к которой применяется метод. Мы знаем, что вы не поняли предыдущее предложение с первого раза. Поэтому смотрите примеры:


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


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

3. Генераторы списков
Для создания списка, заполненного одинаковыми элементами, можно использовать оператор повторения списка, например:


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


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

Вот несколько примеров использования генераторов.

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


Создать список, заполненный квадратами целых чисел можно так:


Если нужно заполнить список квадратами чисел от 1 до n, то можно изменить параметры функции range на range(1, n + 1):


Вот так можно получить список, заполненный случайными числами от 1 до 9 (используя функцию randrange из модуля random):


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

1. Функции
Напомним, что в математике факториал числа n определяется как n! = 1 ⋅ 2 ⋅ ... ⋅ n. Например, 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120. Ясно, что факториал можно легко посчитать, воспользовавшись циклом for. Представим, что нам нужно в нашей программе вычислять факториал разных чисел несколько раз (или в разных местах кода). Конечно, можно написать вычисление факториала один раз, а затем используя Copy-Paste вставить его везде, где это будет нужно.


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

Функции — это такие участки кода, которые изолированы от остальный программы и выполняются только тогда, когда вызываются. Вы уже встречались с функциями sqrt(), len() и print(). Они все обладают общим свойством: они могут принимать параметры (ноль, один или несколько), и они могут возвращать значение (хотя могут и не возвращать). Например, функция sqrt() принимает один параметр и возвращает значение (корень числа). Функция print() принимает переменное число параметров и ничего не возвращает.

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


Дадим несколько объяснений. Во-первых, код функции должен размещаться в начале программы, вернее, до того места, где мы захотим воспользоваться функцией factorial(). Первая строчка этого примера является описанием нашей функции. factorial — идентификатор, то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров, которые получает наша функция. Список состоит из перечисленных через запятую идентификаторов параметров. В нашем случае список состоит из одной величины n. В конце строки ставится двоеточие.

Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной res. Функция завершается инструкцией return res, которая завершает работу функции и возвращает значение переменной res.

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

Приведём ещё один пример. Напишем функцию max(), которая принимает два числа и возвращает максимальное из них (на самом деле, такая функция уже встроена в Питон).


Теперь можно написать функцию max3(), которая принимает три числа и возвращает максимальное их них.


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


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

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


Здесь переменной a присваивается значение 1, и функция f() печатает это значение, несмотря на то, что до объявления функции f эта переменная не инициализируется. В момент вызова функции f() переменной a уже присвоено значение, поэтому функция f() может вывести его на экран.

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

Но если инициализировать какую-то переменную внутри функции, использовать эту переменную вне функции не удастся. Например:


Получим ошибку NameError: name 'a' is not defined. Такие переменные, объявленные внутри функции, называются локальными. Эти переменные становятся недоступными после выхода из функции.

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


Будут выведены числа 1 и 0. Несмотря на то, что значение переменной a изменилось внутри функции, вне функции оно осталось прежним! Это сделано в целях “защиты” глобальных переменных от случайного изменения из функции. Например, если функция будет вызвана из цикла по переменной i, а в этой функции будет использована переменная i также для организации цикла, то эти переменные должны быть различными. Если вы не поняли последнее предложение, то посмотрите на следующий код и подумайте, как бы он работал, если бы внутри функции изменялась переменная i.


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


Итак, если внутри функции модифицируется значение некоторой переменной, то переменная с таким именем становится локальной переменной, и ее модификация не приведет к изменению глобальной переменной с таким же именем.
Более формально: интерпретатор Питон считает переменную локальной для данной функции, если в её коде есть хотя бы одна инструкция, модифицирующая значение переменной, то эта переменная считается локальной и не может быть использована до инициализации. Инструкция, модифицирующая значение переменной — это операторы =, +=, а также использование переменной в качестве параметра цикла for. При этом даже если инструкция, модицифицирующая переменную никогда не будет выполнена, интерпретатор это проверить не может, и переменная все равно считается локальной. Пример:


Возникает ошибка: UnboundLocalError: local variable 'a' referenced before assignment. А именно, в функции f() идентификатор a становится локальной переменной, т.к. в функции есть команда, модифицирующая переменную a, пусть даже никогда и не выполняющийся (но интерпретатор не может это отследить). Поэтому вывод переменной a приводит к обращению к неинициализированной локальной переменной.

Чтобы функция могла изменить значение глобальной переменной, необходимо объявить эту переменную внутри функции, как глобальную, при помощи ключевого слова global:


В этом примере на экран будет выведено 1 1, так как переменная a объявлена, как глобальная, и ее изменение внутри функции приводит к тому, что и вне функции переменная будет доступна.

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

Например, пусть ваша программа должна посчитать факториал вводимого числа, который вы потом захотите сохранить в переменной f. Вот как это не стоит делать:


Этот код написан плохо, потому что его трудно использовать ещё один раз. Если вам завтра понадобится в другой программе использовать функцию «факториал», то вы не сможете просто скопировать эту функцию отсюда и вставить в вашу новую программу. Вам придётся поменять то, как она возвращает посчитанное значение.

Гораздо лучше переписать этот пример так:


Если нужно, чтобы функция вернула не одно значение, а два или более, то для этого функция может вернуть список из двух или нескольких значений:


Тогда результат вызова функции можно будет использовать во множественном присваивании:


3. Рекурсия


Как мы видели выше, функция может вызывать другую функцию. Но функция также может вызывать и саму себя! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что 0!=1, 1!=1. А как вычислить величину n! для большого n? Если бы мы могли вычислить величину (n-1)!, то тогда мы легко вычислим n!, поскольку n!=n⋅(n-1)!. Но как вычислить (n-1)!? Если бы мы вычислили (n-2)!, то мы сможем вычисли и (n-1)!=(n-1)⋅(n-2)!. А как вычислить (n-2)!? Если бы... В конце концов, мы дойдем до величины 0!, которая равна 1. Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на Питоне:


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

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

1. Неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала забудем поставить проверку if n == 0, то factorial(0) вызовет factorial(-1), тот вызовет factorial(-2) и т. д.
2. Рекурсивный вызов с неправильными параметрами. Например, если функция factorial(n) будет вызывать factorial(n), то также получится бесконечная цепочка.

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

1. Графы: первые определения
Графы — это специальная математическая абстракция, которая позволяет обсуждать и анализировать широкий круг вещей в реальном мире. Это такая же абстракция, как, например, числа. Числа естественно возникают при подсчёте яблок у Пети, массы сахара в чайной ложке и температуре воздуха за окном. Изучая числа, вы сталкиваетесь с новыми определениями: вам объясняют, что называется квадратным корнем числа, что такое делители числа. Далее, про числа вам рассказывают в школе разные теоремы: например, формулу квадрата суммы двух чисел, теорему о единственности разложения числа на простые множители. Наконец, на программировании вы изучаете алгоритмы, связанные с числами: алгоритм Евклида нахождения НОД, алгоритм проверки числа на простоту. Всё это ждёт нас и при изучении графов.
Начнём с выяснения, зачем же нам нужны графы, какие вещи в реальном мире они позволяют изучать. Посмотрим на карту метрополитена города Киева:


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


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


На этой картинке имеется ряд языков, на которых говорили или говорят некоторые народы Европы. Учёные-лингвисты давали на такой схеме общего предка нескольким языкам, если они считали, что эти несколько языков родственны, т.е. когда-то в прошлом были одним языком, а потом накопили достаточно различий и стали отдельными языками.
Наконец, посмотрим на пример цепи питания в биологии.


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

Итак, графом называется набор вершин и набор рёбер. Каждое ребро соединяет две вершины.

Степенью вершины называется количество рёбер, концом которых она является. Например, в графе метрополитенов большинство станций имеют степень 2, а конечные станции имеют степень 1. В графе славянской языковой группы вершина «западнославянский язык» имеет степень 4.


На рисунке выше вершина A имеет степень 3, вершина B имеет степень 4. Вершина H имеет степень 0 и называется изолированной вершиной.
2. Виды графов и пути в графах
Для представления разных объектов и связей между ними используются разные виды графов. Например, графы бывают ориентированные и неориентированные. Ориентированные графы — это графы, в котором у каждого ребра есть начало и конец. Такие рёбра рисуют стрелками. В наших примерах граф цепи питания ориентированный, а граф метрополитена — неориентированные.
Подумаем, нужно ли считать граф дорог ориентированным. Пусть мы пишем программу, которая по графу дорог находит автомобильный маршрут между двумя точками в городе. Поскольку в городе бывают улицы с односторонним движением, то наша программа должна это учитывать. Значит, на каждом ребре нужно хранить направление — возможное направление проезда по ребру. Если по дороге можно проехать в обе стороны, то рисуют два ребра со стрелками в разные стороны.

Путём в графе называется любая последовательность вершин, в которой каждые две соседние вершины соединены ребром. На рисунке выше A → C → B → G — это путь из вершины A в вершину G. Есть и более короткий путь из A в G: путь A → B → G. Длиной пути называется количество рёбер в нём. Таким образом, кратчайший путь из A в G имеет длину 2.

Циклом в графе называют путь, у которого начальная и конечная вершина совпадают. На рисунке выше путь A → C → B → D → A является циклом.

Если вы внимательно посмотрите на определение пути и цикла, то увидите, что путём так же можно считать последовательность A → D → B → D → B, а последовательность F → E → F удовлетворяет определению цикла. Чтобы исключить такие патологические ситуации из рассмотрения, обычно вводят понятия простого пути и простого цикла. Простой путь — это путь, в котором нет повторяющихся рёбер. Простой цикл это цикл, который является простым путём.
(Осторожно, сейчас мы введём очень сложное понятие.) Компонентой связности неориентированного графа называется любой набор его вершин, который удовлетворяет следующим двум свойствам:

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

Всякий неориентированный граф разбивается на свои компоненты связности. На рисунке выше имеются три компоненты связности: {A, B, C, D, G}, {E, F} и {H}. Граф, у которого только одна компонента связности, называется связным. Граф, у которого более одной компоненты связности, называется несвязным. На рисунке выше изображён несвязный граф.
В ориентированном графе путём называется любая последовательность вершин, в которой соседние вершины соединены ребром, и это ребро идёт «слева направо» (в нужную сторону). Например, на рисунке ниже A → B → C → D является путём, а A → D → C → B — не является (потому что в графе нет рёбер A → D и C → B).


В ориентированном графе некоторые понятия, которые мы ввели для неориентированных графов, имеют свои аналоги. Например, наряду с понятием «степень вершины», в ориентированных графах используются понятия полустепень захода (количество рёбер, входящих в вершину) и полустепень исхода (количество рёбер, исходящих из вершины). На рисунке выше вершина D имеет полустепень захода 1 и полустепень исхода 3.

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


Между вершинами A и B, а также между вершинами C и D проведены кратные рёбра. Заметим, что между вершинами E и F кратных рёбер нет, поскольку ориентированные рёбра считаются кратными, только если у них совпадают начала и концы с учётом ориентации. Рёбра, исходящие из вершин G и H, называются петлями. Про некоторые графы специально говорят «графы без петель и кратных рёбер», чтобы подчеркнуть, что в них не встречаются ситуации, аналогичные изображённым выше.
3. Деревья
На практике часто встречаются графы, которые обладают какими-нибудь особенностями строения. Один из часто встречающихся видов графов — это деревья. Дерево — это связный неориентированный граф без петель и кратных рёбер, в котором нет циклов. Типичный пример дерева изображён на рисунке ниже.


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

Ещё одно удивительное свойство деревьев — это связь между количеством вершин и количеством рёбер. Договоримся обозначать буквой V количество вершин (от англ. vertex «вершина»), а буквой E — количество рёбер (от англ. edge «ребро»). Например, у дерева на рисунке выше V = 11, E = 10. Мы видим, что для графа на рисунке E = V − 1.

Чтобы понять, всегда ли это будет верно, рассмотрим висячие вершины. Висячей вершиной называется вершина степени 1. На рисунке выше висячими являются вершины A, C, F, G, H, J и K. Заметим, что в дереве, в котором есть хотя бы две вершины, всегда есть хотя бы одна висячая вершина. Действительно, выберем произвольную вершину дерева и пойдём из неё гулять по рёбрам дерева в произвольном направлении, не возвращаясь назад. Поскольку циклов в дереве нет, то с каждым шагом мы будем посещать всё новые и новые вершины и в какой-то момент придём в вершину, из которой никуда пойти нельзя. Эта вершина и будет висячей.

Правда ли, что если в дереве есть хотя бы две вершины, то в нём есть хотя бы две висячие вершины? А правда ли, что если в дереве есть хотя бы три вершины, то в нём есть хотя бы три висячие вершины?

Теорема. В любом дереве E = V − 1.

Доказательство. Как мы выяснили, если в дереве хотя бы две вершины, то в нём есть хотя бы одна висячая вершина. Выберем её и удалим из графа её и ребро, за которое она присоединена к графу. При этом количество вершин и рёбер уменьшится на единицу. С новым графом проделаем ту же операцию. В конце концов, когда мы удалим всё, что можно, мы получим граф из одной вершины. Для него V = 1, E = 0, т.е. E = V − 1. Значит, и в исходном дереве выполнялось E = V − 1. ▮

4. Как хранить граф в программах
Для представления графов в памяти компьютера используется несколько способов. Пусть вершины графов, которые мы рассматриваем, занумерованы, начиная с нуля. Рассмотрим следующий граф:


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


Заметим, что мы должны хранить в какой-нибудь переменной общее количество вершин в графе. Это нужно делать, поскольку информация об изолированных вершинах в списке рёбер отсутствует.
Второй способ, которым можно хранить этот граф, — это структура данных «матрица смежности». Матрица смежности — это квадратная таблица, в которой на пересечении строки i и столбца j стоит 1, если в графе есть ребро из вершины i в вершину j, и стоит 0, если такого ребра нет.


Заметим, что матрица смежности неориентированного графа всегда симметрична относительно главной диагонали. Главная диагональ в матрице идёт из левого верхнего угла в правый нижний.
Наконец, третий способ, который часто используют для представления графов, — это структура данных «списки смежности». В списках смежности для каждой вершины хранится список всех её соседей.


Для хранения ориентированных графов применяются те же структуры данных, с разумными поправками:

в списке рёбер ребро хранится в виде [начало, конец];

в матрице смежности ребро из i в j означает adjacency_matrix[i][j] == 1, и если обратного ребра в графе нет, то будет верным равенство adjacency_matrix[j][i] == 0;

в списках смежности для каждой вершины хранится, в какие вершины из неё исходят рёбра.

1. Количество вершин в данной компоненте связности
В прошлом занятии мы обсудили способы хранения графов. В этом занятии мы начнём изучать алгоритмы на графах. Договоримся, что мы рассматриваем исключительно неориентированные графы без петель и кратных рёбер.

Поставим следующую задачу. Дан граф, в котором выделена вершина s. Требуется найти все вершины, лежащие в одной компоненте связности с ней. Иными словами, нужно понять, до каких вершин можно добраться из s. Будем считать, что граф задан списками смежности:


Наш алгоритм будет основан на рекурсии. Опишем его идею. Встанем в вершину s и посмотрим на всех её соседей. Посетим каждого такого соседа. Когда будем посещать соседа, посмотрим на его соседей, и так далее. Когда мы посещаем вершину, мы вызываем функцию dfs(v), передавая в качестве параметра v номер этой вершины. Эскиз кода таков:


Давайте подумаем, почему этот код не работает. Сначала вызовется функция dfs(0). Внутри функции переменная w примет значение 2, и вызовется функция dfs(2). При просмотре соседей вершины 2 мы увидим соседа 0 и опять вызовем dfs(0). Мы вошли в вечную рекурсию. Функции dfs(0) и dfs(2) будут продолжать вызывать друг друга, создавая новые фреймы в стеке вызовов функций, пока не будет превышен лимит интерпретатора на глубину рекурсии. *очень много страшных слов*

Как же исправить это недоразумение? Надо как-то помечать вершины, в которых мы были, и не ходить ещё раз в уже посещённые вершины.

Давайте заведём массив visited размера n, по ячейке на каждую вершину. В ячейке visited[v] будет лежать значение False, если вершина v пока не была посещена алгоритмом, и True, если вершина v была посещена. При первом заходе в вершину v мы меняем значение visited[v] с False на True.


Теперь наш код работает. Посмотрите в визуализаторе, в каком порядке dfs() посещает вершины. Обратите также внимание на стек вызовов функций. Заметьте, что значения локальных переменных v, которые лежат в стеке вызовов, в точности соответствуют вершинам пути, по которому мы пришли в текущую вершину из стартовой вершины s. Это замечание нам потом пригодится.

Вспомним же, наконец, какую задачу мы решали. Мы хотели посчитать количество вершин, которые достижимы из v. Но это ровно те вершины, которые были посещены функцией dfs(). А у них в массиве visited стоит метка True. Ответ получаем моментально:


Одна маленькая ремарка про стиль программирования. Строчка


выдает в нас начинающего программиста на Питоне. Тру-программист написал бы


Напомним, что not — это логический унарный оператор, который работает так:


Заметьте, что операция not позволяет писать код, который неплохо согласован с английским языком. «if not visited» пословно переводится как «если не посещена».

2. Подсчет количества компонент связности
Теперь поставим перед собой другую задачу: подсчитать количество компонент связности в графе. Эта задача оказывается довольно лёгкой. Действительно, запустим dfs() от вершины с номером 0. Если в результате весь граф будет обойдён, т. е. окажется, что в массиве visited все элементы равны True, то это будет значить, что в графе имеется только одна компонента связности.
Пусть, однако, это не так, и для некоторых вершин visited[v] == False. Выберем среди таких вершин произвольную и запустим dfs() уже от неё. Запущенный обход в глубину посетит все вершины второй компоненты связности.

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


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

Оценим суммарное время работы программы, которая подсчитывает количество компонент связности. Оценку произведём в обозначениях «О-большое». При этом буквой V мы обозначаем количество вершин в графе, а буквой E — количество рёбер.

Функция dfs() вызывается один раз от каждой вершины. Таким образом, только на её вызов и на константные по времени действия в ней (вроде изменения ячейки visited[v]) тратится O(V) действий. Далее, в цикле по переменной w каждый сосед каждой вершины будет просмотрен ровно один раз. Рассмотрим, например, ребро (0, 2). Его наличие означает, что внутри вызова dfs(0) в цикле по соседям вершины 0 переменная w в какой-то момент примет значение 2. Аналогично, при вызове dfs(2) переменная w ровно один раз примет значение 0. Таким образом, эти операции вносят суммарный вклад 2E = O(E) в общее время работы программы. Других действий в программе нет, так что суммарная сложность алгоритма получается O(V + E).

3. Проверка наличия пути между двумя вершинами
Пусть теперь мы хотим научиться быстро отвечать на запросы вида «лежат ли вершины v и w в одной компоненте связности?». Чтобы отвечать на эти запросы, неплохо бы для каждой вершины запомнить номер её компоненты связности. Давайте для начала заведём переменную, которая будет считать количество компомент связности:


Теперь можно завести массив component, в которой для каждой вершины мы запишем номер её компоненты. Как это можно сделать? Заметим, что пока мы посещаем вершины одной и той же компоненты связности, значение переменной num_components не меняется. А при переходе к рассмотрению новой компоненты связности значение этой переменной увеличивается. Значит, значение переменной num_components в тот момент, когда мы вызывали функцию dfs(v), логично считать номером компоненты связности для вершины v. Давайте запоминать это значение в массиве component. Приведём окончательный код.


Теперь представим, что нам дают номера двух вершин v и w, и спрашивают, есть ли путь между ними. Мы проверяем, равны ли значения component[v] и component[w]. Если они равны, то вершины v и w лежат в одной компоненте связности, и между ними существует путь. В противном случае такого пути нет.

В задаче, которую мы научились решать, есть две фазы: фаза подготовки (фаза предподсчёта) и фаза ответов на запросы (фаза ответов на запросы в коде не представлена). Сложность задач, которые состоят из этих двух фаз, принято оценивать отдельно по каждой фазе. В нашем случае время предподсчёта составляет O(V + E), а время ответа на запрос составляет O(1) (оно никак не зависит от размера графа).

4. Обход в глубину на неявных графах
До сих пор мы предполагали, что граф хранится в списке смежности, а вершины графа занумерованы числами 0, 1, 2 и т. д. На практике графы могут храниться по-другому, и у вершин могут быть не номера, а названия. Наконец, граф может не храниться вовсе. Рассмотрим лабиринт, нарисованный на клетчатой бумаге. Например, чёрные клетки могут означать наличие пространства в лабиринте, а белые — его отсутствие (стены).


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

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

Пусть мы стоим в клетке с координатами (x, y). Соседями данной клетки являются клетки (x - 1, y), (x, y - 1), (x, y + 1) и (x + 1, y), если только получившиеся координаты неотрицательны.


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


5. Вывод пути до вершины, поиск циклов
Мы уже умеем проверять, если ли путь между двумя вершинами. Пусть между вершинами s и t есть путь. Давайте научимся его выводить.
Запустим dfs() от вершины s. Заметим, что в тот момент, когда мы дойдём до вершины t, в стеке вызовов функций будут последовательно лежать вызовы функции dfs() от всех вершин интересующего нас пути. Наш путь уже лежит где-то в памяти программы, но он лежит там, откуда вытащить его непросто. А нам надо легко его получать. Значит, придётся нам хранить его самостоятельно.

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


Надеюсь, вы без труда допишете код, который будет выводить искомый путь в нужный момент.

6. Двудольные графы
Наконец, последнее, о чём хочется поговорить в этом занятии — это о двудольных графах. Граф называется двудольным, если все его вершины можно разбить на две группы, при этом все рёбра должны обязательно идти из одной группы в другую, и запрещены рёбра, соединяющие две вершины из одной группы. На примере внизу двумя группами являются группа b и группа g.


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


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

Теорема. Граф является двудольным тогда и только тогда, когда в нём нет циклов нечётной длины.

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

Я хочу дать лишь намёки на решение этой задачи. В решении стоит использовать обход в глубину, который будет ходить по вершинам и красить их. Вам понадобится глобальный массив color, в котором для каждой уже покрашенной вершины записывается её цвет. Наконец, стоит помнить текущий цвет, которым мы красим вершины. Лучше всего текущий цвет передавать в функцию dfs: тогда объявление функции будет выглядеть как dfs(v, curr_color). При вызове функции для соседа текущей вершины текущий цвет надо менять на противоположный.

7. Ограничение на глубину рекурсии в Питоне
В Питоне существует искуственное ограничение на количество вложенных рекурсивных вызовов, которое по умолчанию равно 1000 вызовам. Если ваша программа превысит это ограничение, то она будет остановлена с ошибкой выполнения. Чтобы изменить это ограничение, можно использовать функцию setrecursionlimit(max_depth) из модуля sys.


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

1. Ввод из файла
Пусть нужно считать файл input.txt. Будем считать, что файл input.txt лежит в той же папке, что и наша программа. Напишите в ней такой код:


После этого в списке a окажется список из строк файла. Например, если файл input.txt был


то команда print(a) выведет ['abcd\n', 'efgh\n']. Последний символ в каждой строке — '\n' — это один специальный символ конца строки. Обратите внимание: это не два символа, а один.
Можно удалить эти ненужные символы с помощью метода strip(). В этом случае считывание может выглядеть так:


2. Вывод в файл
Для вывода в файл нужно открыть его и связать объект файла с каким-нибудь именем.


После этого можно осуществлять вывод обычной командой print(), указывая при этом объект файла в качестве параметра file.


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


3. Ввод-вывод в ситуации, когда количество строк неизвестно
Пусть нужно считать входной файл, причём количество строк в нём заранее неизвестно. Выполните такой код:


После этого в списке a окажется список из строк входного файла. Например, если входной файл был


то команда print(a) выведет ['abcd\n', 'efgh\n']. Последний символ в каждой строке — '\n' — это один специальный символ конца строки. Обратите внимание: это не два символа, а один.
К сожалению, протестировать на правильность программы с таким вводом-вывом из среды Wing невозможно. Дело в том, что в консоли Винга нельзя сказать, что входной файл закончился. Нет возможности ввести символ конца файла. Соответственно, метод sys.stdin.readlines() никогда не завершится, поскольку будет ждать всё новые и новые строки из входа. Чтобы протестировать ваш код на системе Windows, проделайте следующие действия:

1. Откройте консоль: Пуск → Выполнить → cmd
2. С помощью команды cd дойдите до папки с вашей программой. При этом не стесняйтесь обильно нажимать клавишу Tab.
3. Введите имя вашей программы в консоли и нажмите Enter. При этом ваша программа запустится
4. Введите в консоль входные данные для программы.
5. Введите конец входного файла, нажав сочетание Ctrl+Z. Нажмите Enter.
6. Насладитесь выводом вашей программы.

1. Очередь
Вспомним карточную игру «Пьяница». Играют двое, у каждого исходно по половине колоды карт. За один ход двое вскрывают по верхней карте из своих стопок. Чья карта старше, тот забирает две вскрытые карты и кладёт под низ своей стопки.

Будем считать, что про любые две карты в колоде можно сказать, какая из них старше. Будем обозначать карты натуральными числами, и пусть большее число бьёт меньшее. Колоду будем представлять списком. Для простоты рассмотрим случай шести карт в колоде:


Тогда после первого хода стопки игроков станут такими:


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

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

Очередь должна поддерживать операцию push(x), которая принимает новый элемент и добавляет его в конец набора.

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

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

Код

queue = []  # список для хранения элементов

def push(x):
    queue.append(x)

def pop():
    return queue.pop(0)

push(3)
push(5)
print(pop())  # 3
print(pop())  # 5

У такой реализации очереди есть существенный недостаток: время работы операций. Стандартная реализация списков в Питоне гарантирует, что append() выполняется в среднем за O(1). Но вот операция pop(0) выполняется за O(n), где n — текущий размер очереди. Действительно, при её выполнении все элементы списка сдвинутся в памяти на одну ячейку влево, т. е. произойдёт n копирований адресов объектов.

Упражнение. Мысленно представьте, что будет, если добавлять элементы в начало списка, а удалять — из конца. Поймите, что при этом сложность операции push(x) станет O(n).

Тем не менее, можно предложить реализацию очереди, в которой обе операции будут выполняться за O(1). Для этого немного модифицируем исходное решение. Будем хранить индекс head первого элемента очереди. Изначально head = 0. При каждом удалении элемента из очереди мы будем просто смещать этот индекс на одну позицию вправо, не производя физического удаления элементов из очереди.

Код

queue = []  # список для хранения элементов
head = 0  # индекс первого реального элемента в очереди

def push(x):
    queue.append(x)

def pop():
    global head  
    # поскольку мы изменяем глобальную переменную,
    # мы должны явно написать, что она глобальная

    head += 1
    return queue[head - 1]

push(3)
push(5)
print(pop())  # 3
print(pop())  # 5

Убедитесь, что теперь операция pop() выполняется за O(1). Как можно узнать, сколько реальных элементов содержится в очереди на каком-то шаге?

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

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

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

Задание множеств
Множество задается перечислением всех его элементов в фигурных скобках. Исключением явлеется пустое множество, которое можно создать при помощи функции set(). Если функции set передать в качестве параметра список, строку или кортеж, то она вернёт множество, составленное из элементов списка, строки, кортежа. Например:


выведет {'e', 'q', 'r', 't', 'w', 'y'}.

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


выведет True, так как A и B — равные множества.

Каждый элемент может входить в множество только один раз. set('Hello') вернет множество из четырех элементов: {'H', 'e', 'l', 'o'}.

Работа с элементами множеств
Узнать число элементов в множестве можно при помощи функции len.

Перебрать все элементы множества (в неопределенном порядке!) можно при помощи цикла for:


Проверить, принадлежит ли элемент множеству можно при помощи операции in, возвращающей значение типа bool. Аналогично есть противоположная операция not in. Для добавления элемента в множество есть метод add:


Для удаления элемента x из множества есть два метода: discard и remove. Их поведение различается только в случае, когда удаляемый элемент отсутствует в множестве. В этом случае метод discard не делает ничего, а метод remove генерирует исключение KeyError.

Наконец, метод pop удаляет из множества один случайный элемент и возвращает его значение. Если же множество пусто, то генерируется исключение KeyError.

Из множества можно сделать список при помощи функции list.

Операции с множествами
С множествами в питоне можно выполнять обычные для математики операции над множествами.