Язык программирования Python 3

Язык Python часто позволяет создавать более короткие и красивые решения. Например, при написании решении задач на языке Python не требуется самостоятельно реализовывать "длинную" арифметику.

Цель этого урока - дать вам начальные данные о языке Python в достаточной мере для решения на нём задач (создания консольных приложений с вводом-выводом при помощи текстовых файлов).

Преимущества и недостатки языка Python

Преимущества:

  1. Встроенная поддержка "длинной арифметики", комплексных чисел, списков, словарей, стеков, очередей и т.д.
  2. Кроссплатформенность (программы можно писать и выполнять в Windows / Linux / MasOS / Android и т.д.)
  3. Поддержка всех кодировок (например utf-8)
  4. Большое количество библиотек на все случаи (HTTP и FTP протоколы, работа с сетью, работа с изображениями и т.д.)
  5. Интерпретируемый язык (можно менять код "на" лету). Удобно писать служебные скрипты.
  6. Сборщик мусора позволяет не беспокоиться об освобождении памяти.
  7. Python сравнительно прост в изучении и позволяет выражать алгоритмы кратко и просто.

Недостатки:

  1. Низкая скорость выполнения (причины: интерпретация, динамическая типизация) по сравнению с Delphi, C/C++, C#, Java.
  2. Отсутствие библиотек для создания "родных" интерфейсов для Windows (для олмпиадных задач интерфейсы и не нужны).

Установка интерпретатора Python

Официальный сайт: http://www.python.org

Установка под Linux: обычно Python входит в дистрибутив и устанавливается при установке Linux. Установить в любой момент можно командой: sudo apt-get install python

Установка под Windows:

  1. Скачать на странице http://www.python.org/download/ версию для своей операционной системы
  2. Запустить PythonXXX.msi и пройти процесс установки (по умолчанию используется каталог C:\PythonXXX). XXX - Номер версии Python, например 27 или 34.

Запуск в режиме калькулятора

Запуск Питона

Запуск из меню кнопки "Пуск"

Можно запустить из командной строки набрав, например: C:\Python34\python.exe (для версии 3.4)

Питон как калькулятор

Работа с Python в режиме калькулятора

Из приведённого на картинке примера видно что:

Среда разработки для Python

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

IDLE (Integrated DeveLopment Environment) - IDE, которая устаналивается сразу вместе с Python:

IDLE

Запуск программы на выполнение - F5.

Среда разработки от компании JetBrains: PyCharm  http://www.jetbrains.com/pycharm/

pycharm

Редактор Notepad++

Для работы с текстом программы можно использовать любой текстовый редактор. Удобнее, если в редакторе есть подсветка синтаксиса. Notepad++ позиционируется как замена стандатному Блокноту (Notepad) в Windows с большими возможностями (прежде всего подсветкой синтаксиса для различных языков программирования).

Загрузить можно с сайта: http://notepad-plus-plus.org/download

Notepad++

Первая программа на Python

Решение задачи "A+B" с вводом из файла sum.in и выводом в файл sum.out.

sum.py

Типы данных в языке Python

sys.stdin = open("a.in","r")    # Входной файл
sys.stdout = open("a.out","w")  # Выходной файл
print("a=",a)

Демонстрация работы различных типов данных:

Понятие переменной, объекта, ссылки, семантика (значение) оператора присваивания

# -*- coding: utf-8 -*-

# Отличия переменной, объекта и ссылки
# Переменная приваивается "по значению"
a = 3
b = a
b = 4
print ("a =", a, ' b =', b)  # a = 3  b = 4, переменная a не изменилась после изменения b

# Экземпляры классов присваиваются "по ссылке"
class MyClass: field = 1 # Создали класс MyClass с одним полем field
a = MyClass()
a.field = 3
b = MyClass()
b = a #  Теперь b и a ссылаются на один и тот же объект
b.field = 4
print ("a.field =", a.field, ' b.field =', b.field)  # a.field = 4  b.field = 4
print(u'2. Операторы управления потоком вычислений')
# if - условный оператор
if (3 > 2) or (1==2) and (3==1+2): # Условие
  print("3 > 2") # При выполнении условия
else: # Необязательный else
  print("xxx") # Если условие не выполняется

# while - цикл с предусловием
i = 23  # Задаём значение переменной
while i > 0: # Пока больше 0
  print(i, end=' ') # Печатаем в строку
  i //= 2  # Деление нацело
print() # Переводим на новую строку. Получилось: 23 11 5 2 1

# for - обработка множества значений
for str in ['first string', 'second', 'third']:
  print(str)
for i in range(1999,2010):
  print(i, end=' ') # Получилось: 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009
print()

print(u'3. Функции, определение и вызов функций, формальные и актуальные параметры, рекурсия')
# Определение рекурсивной функции вычисления факториала
def Factorial(n): 
  # Барьерное условие. Ограничивает область применимости функции
  # "Мёртвые программы не лгут!"
  assert n > 0
  if n == 1:
    return 1
  else:
    return n * Factorial(n - 1)

# print Factorial(-1) # При вызове будет ошибка с выводом всей
# последовательность  

# Факториал при помощи тернарного оператора в Python
def Factorial2(n): return 1 if n == 1 else n * Factorial(n - 1)
#   (Что-то) если (условие) иначе (что-то другое)
#  В С/C++: (условие) ? (что-то) : (что-то другое)

# Пример вызова обеих функций
print("3! =", Factorial(3), ' ', Factorial2(3))

# Генератор
# 1 1 2 3 5 8 13
def fibonacci(max): # генератор (а не функция, т.к. оператор return заменён на yield)
  a, b = 0, 1
  while a < max:
    yield a         # return a, + запоминаем место рестарта для следующего вызова
    a, b = b, a + b # параллельное присваивание, которое выполняется одновременно и параллельно

for n in fibonacci(100):   # используем генератор fibonacci() как итератор
  print(n, end=' ') # печатаем все числа Фибоначчи меньшие 100 через пробел
print()

# Вычисление наименьшего общего делителя, % - деление по модулю (mod)
def GCD(a, b): return a if b == 0 else GCD(b, a % b)

print("GCD(30,45) =", GCD(30, 45))  # Результат: GCD(30,45) = 15

print(u"4. Представление чисел в языке Python, операции над числами")

from cmath import sin, sqrt
from math import * # Подключаем функции библиотеки math

print(2 ** 100) # возведение 2 в степень 100
print(sin(pi * 0.5))  # вычисление синуса от половины пи
print(3.23e10) # Экспоненциальная форма записи чисел
print(u"Python работает с комплексными числами")
x = 1 + 2j # целое число и мнимое число
print(x * 2)
print(u"Решим квадратное уравнение x*x+1=0 с комплексными корнями")
a,b,c = 1,0,1
D = b*b-4*a*c
dd = ((-sqrt(D), sqrt(D)) if D > 0 else (-1j * sqrt(-D), 1j * sqrt(-D)))
x = [(-b+d)/2*a for d in dd]
print(x)

i = 1
for c in u"Привет!":
  print(i, c)
  i += 1

print(u"Привет!")
print(u"5. представление строк в языке Python, простые и Unicode-строки, основные операции")
str = "String " + '2'
print(str, ' ', str.upper(), ' ', str.lower(), ' ', str.center(20))
print(str.count('t')) # Количество букв t в строке
unicodeStr = u'Привет'
print(unicodeStr, ' ', type(unicodeStr))
myString = "Не юникод-строка".encode("utf-8")
print(u"Переводим её в Unicode и печатаем: ", myString.decode("utf-8")) #
print(unicodeStr.encode("utf-8"))

# кодировка текста, Unicode (основные концепции, классы символов, уникальность представления);
s1 = "Тест"
s2 = u"Тест"
print(s1, ' ', s2)
#assert s1 == s2

# Основные структуры данных языка Python:
# списки (lists), тюплы (tuples), словари (dictionaries, dicts).
a = [1, 2, "a"]              # список
b = (1, 2, "a")              # кортеж, тюплы (tuples)
c = {'a': 1, 'b': 'B'}       # словарь
l = ['A', 'B', 'C', 'D', 'E'] # Исходный список
print(u"срез от нулевого до второго промежутка ", l[0:2]) # ['A', 'B']
print(u"срез от второго до второго с конца элемента", l[1:-2]) # ['B', 'C']
print(u"каждый второй элемент начиная с первого", l[1::2]) # ['B', 'D']
print(u"все элементы в обратном порядке", l[::-1])  # ['E', 'D', 'C', 'B', 'A']

tuple = (1, 3, 2, "a")  # кортеж, тюпл (tuple)
print(type(tuple), ' ', tuple)  # <class 'tuple'>   (1, 3, 2, 'a')
for i in tuple: print(i, end=' ')  # 1 3 2 a
print()
t = 12345, 54321, 'hello!' # tuple packing
print(t) # (12345, 54321, 'hello!')

Вычисление Наибольшего Общего Делителя (НОД) и Наименьшего Общего Кратного (НОК)

# Наибольший общий делитель (НОД)  - Greatest Common Divisor
def GCD(x,y): 
  return x if y == 0 else GCD(y,x%y)

# Наименьшее общее кратное (НОК) НОК(x,y) = x*y/НОД(x,y)  - Least Common Multiple
def LCM(x,y):
  return x*y // GCD(x,y)

print(GCD(10,15))
print(LCM(10,15))
print(LCM(10,0))
print(LCM(0,30))
print(LCM(60,144))

Найти минимум и максимум в массиве:

A = [100, 34, 678]
print("Количество элементов в массиве:",len(A))
print("Минимум:",min(A))
print("Максимум:",max(A))

Различные реализации вставки элемента в отсортированный массив так чтобы он остался отсортированным:

# -*- coding: utf-8 -*-

# Вставка элемента в отсортированный массив
# так чтобы он оставался отсортированным

# 1. Через insert/append
def Insert1(b, value): # В функцию передаётся исходный массив b и значение value
  c = list(b) # Делаем копию списка
  for i, x in enumerate(b): # Пробегаем по исходному списку
    if x > value: # Если нашли элемент больше заданного
      c.insert(i, value) # Добавляем перед ним заданный
      return c # Возвращаем изменённый список
  c.append(value) # Если мы так и не нашли заданный элемент, добавляем значение в конец
  return c # возвращаем новый массив

# 2. Используя срезы
def Insert2(b, value):
  for i, x in enumerate(b): # i - индекс в массиве, x - значение
    if x > value:
      return b[:i] + [value] + b[i:] # Слияние 3-х массивов
  return b + [value]

# 3. Двоичный поиск (последнего числа меньшего value)
def Insert3(b, value):
  min, max = 0, len(b)
  while max - min > 0:
    m = (min + max) // 2 # Делим отрезок пополам
    if b[m] > value:
      max = m
    else:
      min = m + 1
  return b[:max] + [value] + b[max:]

# 4. Используя библиотеку bisect - двоичный поиск и вставка
def Insert4(b, value):
  from _bisect import insort
  l = list(b)
  insort(l, value)
  return l

# 5. Добавление путем создания нового списка (поэлементно)
def Insert5(b, value):
  p = []
  inserted = False
  for x in b:
    if x > value and not inserted:
      p.append(value)
      inserted = True
    p.append(x)
  if not inserted:
    p.append(value)
  return p

# Проверка, что все функции работают как надо (простейший модульный тест)
assert Insert3([11], 10) == [10, 11]
assert Insert3([], 10) == [10]
assert Insert3([3], 10) == [3, 10]
assert Insert3([3, 13], 10) == [3, 10, 13]
assert Insert3([2, 6, 8], 10) == [2, 6, 8, 10]
assert Insert3([2, 6, 8], 7) == [2, 6, 7, 8]
assert Insert3([2, 6, 8], 5) == [2, 5, 6, 8]
assert Insert3([2, 6, 8], 3) == [2, 3, 6, 8]
assert Insert3([2, 6, 8], 1) == [1, 2, 6, 8]
b = [2, 6, 8, 14, 15, 20]
assert Insert3(b, 10) == [2, 6, 8, 10, 14, 15, 20]
assert Insert3(b, 7) == [2, 6, 7, 8, 14, 15, 20]
assert Insert3(b, 5) == [2, 5, 6, 8, 14, 15, 20]
assert Insert3(b, 1) == [1, 2, 6, 8, 14, 15, 20]

assert Insert1([11], 10) == [10, 11]
assert Insert1([], 10) == [10]
assert Insert1([3], 10) == [3, 10]
assert Insert1([3, 13], 10) == [3, 10, 13]
assert Insert1([2, 6, 8], 10) == [2, 6, 8, 10]
assert Insert1([2, 6, 8], 7) == [2, 6, 7, 8]
assert Insert1([2, 6, 8], 5) == [2, 5, 6, 8]
assert Insert1([2, 6, 8], 3) == [2, 3, 6, 8]
assert Insert1([2, 6, 8], 1) == [1, 2, 6, 8]

assert Insert2([11], 10) == [10, 11]
assert Insert2([], 10) == [10]
assert Insert2([3], 10) == [3, 10]
assert Insert2([3, 13], 10) == [3, 10, 13]
assert Insert2([2, 6, 8], 10) == [2, 6, 8, 10]
assert Insert2([2, 6, 8], 7) == [2, 6, 7, 8]
assert Insert2([2, 6, 8], 5) == [2, 5, 6, 8]
assert Insert2([2, 6, 8], 3) == [2, 3, 6, 8]
assert Insert2([2, 6, 8], 1) == [1, 2, 6, 8]

assert Insert5([11], 10) == [10, 11]
assert Insert5([], 10) == [10]
assert Insert5([3], 10) == [3, 10]
assert Insert5([3, 13], 10) == [3, 10, 13]
assert Insert5([2, 6, 8], 10) == [2, 6, 8, 10]
assert Insert5([2, 6, 8], 7) == [2, 6, 7, 8]
assert Insert5([2, 6, 8], 5) == [2, 5, 6, 8]
assert Insert5([2, 6, 8], 3) == [2, 3, 6, 8]
assert Insert5([2, 6, 8], 1) == [1, 2, 6, 8]

print(b)
# Дан массив с различными элементами. Найти количество положительных элементов, расположенных между минимальным и максимальным элементами.
b = [12, 6, -2, 8, -5, 13, -34, 1, -4]
max = b[0]
min = b[0]
for x in b:
  if x > max:
    max = x
  if x < min:
    min = x

Замена отрицательных элементов массива нулями при помощи генератора:

# Замена отрицательные элементы массива нулями
b = [12, 6, -2, 8, -5, 13, -34, 1, -4]
p = [0 if x < 0 else x for x in b]
print(p)

Даны массивы А и В. Вычислить суммы соответствующих (по индексу) элементов массивов.

A = [28, 15, 4, -5, 6]
B = [3, 10, 1, -4, -8]
for k, v in enumerate(A): # k - индекс в массиве, v - значение в массиве A
  print(A[k]+B[k], end=' ')
print()

Дано произвольное значение b и произвольный массив G. Найти сумму элементов массива G, меньших заданного b.

b = 6
G = [5,6,71,3,1,3]
print(sum(x for x in G if x < b))

Работа со списками (list)

# -*- coding: utf-8 -*-

# Пример со списками и словарями
l = [2,3,36,4]
# Добавление элемента в конец списка
l.append(56)
# Вставка элемента в середину списка
l.insert(3,999) # Вставить элемент 999 после 3-его элемента списка
print(l)
# l[6] = 10  # Шестого элемента нет => Будет ошибка

Работа со словарями (dict)

# Создаём словарь
d = {}
d[23] = 67
print(d)  # {23: 67}
d[5] = 231
print(d)  # {23: 67, 5: 231}
# Переписываем 23-ий элемент
d[23] = 554
d[23462356] = (2,3)
d[234656] = "sdfsgd"
for k in sorted(d.keys()):
  print("d[%s] = %s" % (k, d[k]))
print(d)

b = [3,2,4]
c = list(b)
b.append(55)
print('b =',b)
print('c =',c)

class Test:
  value = 1

a = Test()
a.value = 2
b = a
b.value = 3
print('a =',a.value)
print('b =',b.value)

Чтение и запись файлов в Python

Пример 1. Читаем размер массива, сам массив, сортируем и выводим.

sort.py

Пример входного файла sort.in:

13
4 3 8 9 1 32 4 3 2 2 65 4 3 

Пример выходного файла sort.out:

1 2 2 3 3 3 4 4 4 8 9 32 65

Пример 2. Другой способ чтения:

gcd.py

Стандартные алгоритмы в Python

Стандартная библиотека Python содержит готовые реализации часто используемых алгоритмов и структур данных. Их не нужно писать самостоятельно: достаточно выбрать подходящую функцию или класс и знать, какова их сложность. Ниже рассмотрены сортировка с параметром key и модули bisect, heapq, itertools и collections. Все примеры написаны для Python 3, используют только стандартную библиотеку и проверены запуском.

Сортировка с ключом: sorted() и list.sort()

Функция sorted(данные) возвращает новый отсортированный список, а метод данные.sort() сортирует сам список и ничего не возвращает. Параметр key задаёт функцию, по значению которой сравниваются элементы; параметр reverse=True задаёт порядок по убыванию. Сортировка устойчивая: элементы с равными ключами сохраняют исходный порядок, в том числе при reverse=True. Время работы — O(n log n) в худшем случае; если данные уже отсортированы или упорядочены по убыванию, достаточно O(n) сравнений (сложность операций, руководство по сортировке).

Реализация на Python

words = ["banana", "kiwi", "apple", "fig", "cherry"]
print(sorted(words))                       # ['apple', 'banana', 'cherry', 'fig', 'kiwi']
print(sorted(words, key=len))              # ['fig', 'kiwi', 'apple', 'banana', 'cherry']

students = [("Анна", 4), ("Борис", 5), ("Вера", 4), ("Глеб", 5)]
# По убыванию балла; при равных баллах исходный порядок сохраняется
print(sorted(students, key=lambda s: s[1], reverse=True))

# list.sort сортирует список на месте: по баллу, а при равных баллах по имени
students.sort(key=lambda s: (s[1], s[0]))
print(students)

Поиск в отсортированном списке: модуль bisect

Модуль bisect работает с отсортированным списком и находит позицию для элемента двоичным поиском. Функция bisect_left(a, x) возвращает позицию, на которую можно вставить x с сохранением порядка, — перед всеми равными элементами. Функция bisect_right(a, x) возвращает позицию после всех равных элементов. Поиск занимает O(log n) сравнений. Функция insort(a, x) вставляет x на нужное место, но все элементы правее этого места сдвигаются на одну позицию, поэтому insort работает за O(n) (документация модуля bisect).

Реализация на Python

from bisect import bisect_left, bisect_right, insort

def count_in_range(sorted_list, low, high):
    """Количество элементов x, для которых low <= x <= high; при low > high равно 0."""
    return max(0, bisect_right(sorted_list, high) - bisect_left(sorted_list, low))

numbers = [1, 3, 3, 5, 8, 8, 8, 13]
print(bisect_left(numbers, 3), bisect_right(numbers, 3))   # 1 3
print(bisect_left(numbers, 8), bisect_right(numbers, 8))   # 4 7
print(count_in_range(numbers, 3, 8))                       # 6
insort(numbers, 6)                                         # вставка за O(n): сдвигаются элементы справа
print(numbers)                                             # [1, 3, 3, 5, 6, 8, 8, 8, 13]

Куча и очередь с приоритетом: модуль heapq

Модуль heapq хранит кучу в обычном списке: наименьший элемент всегда находится в позиции h[0]. Функции heappush(h, x) и heappop(h) добавляют элемент и извлекают наименьший; каждая из них занимает O(log n), так как высота кучи из n элементов имеет порядок log n. Функция heapify(h) превращает произвольный список в кучу за линейное время O(n). Функция heapq.nsmallest(k, данные) при малом k работает быстрее, чем sorted(): она использует кучу из k элементов и занимает O(n log k) (документация модуля heapq). В примере сортировка кучей состоит из одного вызова heapify и n извлечений наименьшего элемента, поэтому занимает O(n log n).

Реализация на Python

import heapq

def heap_sort(values):
    heap = list(values)                    # копия: исходный список не меняется
    heapq.heapify(heap)                    # превращаем в кучу за O(n)
    count = len(heap)
    return [heapq.heappop(heap) for _ in range(count)]   # count извлечений по O(log n)

data = [5, 1, 9, 3, 7, 2]
print(heap_sort(data))                     # [1, 2, 3, 5, 7, 9]
print(heapq.nsmallest(2, data))            # [1, 2]

heap = []
for x in [5, 1, 9, 3]:
    heapq.heappush(heap, x)                # каждая вставка за O(log n)
print(heap[0])                             # 1: наименьший элемент лежит в позиции 0
print(heapq.heappop(heap))                 # 1

Итераторы: модуль itertools

Модуль itertools содержит итераторы: они выдают элементы по одному и не хранят весь результат в памяти. Функция accumulate(данные) выдаёт частичные суммы за O(n), то есть за один проход по данным. Функция combinations(данные, r) выдаёт все сочетания по r элементов; их количество равно n!/(r! (n-r)!), поэтому время работы растёт вместе с этим числом. Функция groupby(данные) выделяет группы подряд идущих равных элементов за O(n); чтобы собрать в одну группу все одинаковые элементы, данные сначала нужно отсортировать (документация модуля itertools).

Реализация на Python

from itertools import accumulate, combinations, groupby

values = [3, 1, 4, 1, 5]
print(list(accumulate(values)))            # [3, 4, 8, 9, 14]: частичные суммы
print(list(combinations("abcd", 2)))       # шесть пар: 4!/(2!*2!) = 6
text = "aaabccdddd"
runs = [(char, len(list(group))) for char, group in groupby(text)]
print(runs)                                # [('a', 3), ('b', 1), ('c', 2), ('d', 4)]

Специальные контейнеры: модуль collections

Класс Counter подсчитывает количество одинаковых элементов за один проход по данным. Метод most_common(k) возвращает k самых частых элементов; элементы с одинаковым количеством выводятся в порядке первого появления. Класс deque — двусторонняя очередь: добавление и удаление элементов с обоих концов занимают O(1). В модуле есть также defaultdict, который создаёт значение по умолчанию для нового ключа, и namedtuple (документация модуля collections).

Реализация на Python

from collections import Counter

words = "в лесу темно и в лесу тихо".split()
print(Counter(words).most_common(2))       # [('в', 2), ('лесу', 2)]

Пример с deque: скользящий максимум. Для каждого окна из width подряд идущих элементов находится наибольший элемент. Весь массив обрабатывается за O(n), потому что каждый индекс добавляется в очередь и удаляется из неё не более одного раза.

Реализация на Python

from collections import deque

def sliding_max(values, width):
    """Максимум в каждом окне из width (width >= 1) подряд идущих элементов за O(n)."""
    window = deque()                       # индексы элементов; их значения строго убывают
    result = []
    for i, value in enumerate(values):
        while window and values[window[-1]] <= value:
            window.pop()                   # такие элементы уже не могут быть максимумом
        window.append(i)
        if window[0] <= i - width:
            window.popleft()               # индекс вышел за левую границу окна
        if i >= width - 1:
            result.append(values[window[0]])
    return result

print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))   # [3, 3, 5, 5, 6, 7]

Сводка сложности операций:

Ссылки

 

 

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

Среды, кучек массива, подстрока

a = ['a', 'b', 'c', 'd', 'e', 'f'] # Массив
#     0    1    2    3    4    5   < Индексы
# Хочу получить подмассив начиная с элемента с индексом 1 
a[1:5] # Элементы с 1-ого до 5-ого. 
# l[a,b]  - срез [a,b) - не включая элемент с индексом b
a[-1] # последний элемент массива
a[0:-1] # Массив со всеми элементами кроме последнего
# Удаление элементов
del a[-1] # Удаление последнего элемента
del a[5:7]  # Удаление элементов с 5-ого (включительно) до 7-ого

a.append(e) # Добавление элемента в конец
a.insert(2,e) # Добавление элемента в произвольное место