Практикум по алгоритмизации и программированию на Python

Практикум по алгоритмизации и программированию
на Python

2-е издание, исправленное

Хахаев И.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Практикум по алгоритмизации и программированию на Python/ И.А. Хахаев - М.: Национальный
Открытый Университет “ИНТУИТ”, 2016

Курс предназначен для начального знакомства с основными алгоритмами и с программированием на
языке Python в интегрированных средах разработки (IDE) Geany и Eric.
В курсе рассматриваются типовые задачи в рамках базового курса информатики для средней школы
(с учётом требований ЕГЭ), алгоритмы их решения и реализация этих алгоритмов на языке Python, и
методических указаний для учителей, где описываются особенности IDE Geany и IDE Eric, а также
причины и особенности обучения программированию на Python. Кроме того, курс дополняется
примерами программ по каждому разделу учебного пособия (32 файла с примерами вариантов
разобранных задач.). Дополнительно в курсе описываются основы моделирования и
программирования графики в Python с использованием модуля turtle и кросс-платформенной
библиотеки Tkinter.

(c) ООО “ИНТУИТ.РУ”, 2015-2016
(c) Хахаев И.А., 2015-2016

3

Язык Python и его особенности

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

1.1 Общие сведения о языке

В основном Python используется как интерпретатор, хотя существуют средства
компиляции Python-программ.

Интерпретатор Python позволяет выполнять команды и операции средствами
интерактивной оболочки Python (см. далее).

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

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

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

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

import имя_модуля

А отдельные функции — с помощью команды:

from имя_модуля import функция1, … функцияN

Присваивание в Python обозначается знаком “=“, а равенство — знаком “==“.

В Python разрешены “цепочки” присваиваний и сравнений, однако присваивания и
сравнения нельзя смешивать. Выражения a=b=c=4 и a<b<5 допустимы, а выражение

a<b=4 — недопустимо. Однако допустимо выражение a<b==4.

В Python отсутствуют “операторные скобки” типа begin … end или DO … LOOP. Вместо
них в составных операторах (ветвления, циклы, определения функций) используются
отступы от начала строки (пробелы).

И наконец, элементы структуры данных могут иметь отрицательные номера.

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

4

“Литература”) и справка Python.

1.2 Типы и структуры данных

1.2.1 Типы данных

1.2.1.1 Числа

Числа в Python могут быть обычными целыми (тип int), длинными целыми (тип long),
вещественными (тип float) и комплексными (они не будут рассматриваться и
использоваться). Для всех задач в пределах школьного курса используются только
целые и вещественные числа.

Для преобразования чисел из вещественных в целые и наоборот в Python определены
функции int() и float(). Например, int(12.6) даст в результате 12, а float(12) даёт
в результате 12.0 (десятичный разделитель — точка). Основные операции с числами
приведены в табл. 1.1.

Таблица 1.1. Операции с числами

Операция
Описание

x + y
Сложение (сумма x и y)

x - y
Вычитание (разность x и y)

x * y
Умножение (произведение x и y)

x/y
Деление x на y (частное). Внимание! Если x и y целые, то результат всегда
будет целым числом! Для получения вещественного результата хотя бы
одно из чисел должно быть вещественным. Пример:

100/8 → 12,

а вот

100/8.0 → 12.5

x//y
Целочисленное деление (результат — целое число). Если оба числа в
операции вещественные, получается вещественное число с дробной частью,
равной нулю. Пример:

100//8 → 12
101.8//12.5 → 8.0

(для сравнения

101.8/12.5 → 8.1440000000000001)

x%y
Остаток от целочисленного деления x на y Пример:

10%4 → 2

5

x**y
Возведение в степень (x в степени y). Работает и для вещественных чисел.
Примеры:

2**3 → 8
2.3**(-3.5) → 0.05419417057580235

-x
Смена знака числа

Кроме того, в Python для операций с числами используются функции abs()
(вычисление абсолютного значения — модуля, abs(-3)→ 3), pow() (возведение в
степень, pow(2,3) → 8), divmod() (вычисление результата целочисленного деления и
остатка, divmod(17,5)→ (3,2)) и round() (округление, round(100.0/6) → 17.0). Эти
функции являются “встроенными”, что означает, что для их использования нет
необходимости подключать дополнительные модули. Все прочие функции для работы
с числами (математические), такие как вычисление квадратного корня, синуса и пр.
требуют подключения модуля math.

1.2.1.2 Логические значения

Логические значения в Python представлены двумя величинами — логическими
константами True (Истина) и False (Ложь).

Логические значения получаются в результате логических операций и вычисления
логических выражений.

Таблица 1.2. Основные логические операции и выражения

Операция или

выражение
Описание

>
Условие “больше” (например, проверяем, что a > b)

<
Условие “меньше” (например,проверяем, что a < b)

==
Условие равенства (проверяем, что a равно b)

!=
Условие неравенства (проверяем, что a не равно b)

not x
Отрицание (условие x не выполняется)

x and y
Логическое “И” (умножение). Чтобы выполнилось условие x and y,
необходимо, чтобы одновременно выполнялись условия x и y.

x or y
Логическое “ИЛИ” (сложение). Чтобы выполнилось условие x or y,
необходимо, чтобы выполнилось одно из условий.

x in A
Проверка принадлежности элемента x множеству (структуре) A (см.
“Структуры данных”).

a < x < b
Эквивалентно (x > a) and (x < b)

1.2.2 Структуры данных

В Python определены такие структуры данных (составные типы) как

6

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

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

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

1.2.2.1 Неизменяемые последовательности — строки

Строки (последовательности символов — букв и других значков, которые можно найти
на клавиатуре компьютера) могут состоять из символов английского и любого другого
алфавита. Для простоты и определённости в строковых значениях переменных в
дальнейшем будем использовать только символы английского алфавита. В Python
строки и символы нужно заключать в кавычки (одиночные или двойные). Элементы
(символы) в строке нумеруются, начиная с нуля. Одиночный символ — буква —
является “с точки зрения Python” строкой, состоящей из одного элемента.

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

Числа могут быть преобразованы в строки с помощью функции str(). Например,

str(123) даст строку ‘123’. Если строка является последовательностью знаков-цифр,
то она может быть преобразована в целое число в помощью функции int()

(int(‘123’) даст в результате число 123), а в вещественное — с помощью функции

float() (float(‘12.34’) даст в результате число 12.34). Для любого символа можно
узнать его номер (код символа) с помощью функции ord() (например, ord(‘s’) даст
результат 115). И наоборот, получить символ по числовому коду можно с помощью
функции chr() (например chr(100) даст результат ‘d’).

Таблица 1.3. Основные операции со строками

Функция

или

операция

Описание и результат

len(s)
Вычисляется длина строки s как число символов

s1 + s2
Конкатенация. К концу строки s1 присоединяется строка s2, в результате
получается новая строка, например, ‘вы’ + ‘года’ → ‘выгода’

7

s * n
(или n *
s)

n-кратное повторение строки s, в результате получается новая строка,
например ‘кан’*2 → ‘канкан’

s[i]
Выбор из s элемента с номером i, нумерация начинается с 0 (первый
элемент имеет номер 0). Результатом является символ. Если 
, отсчёт

идёт с конца (первый символ строки имеет номер 0, последний имеет номер
-1). Пример:

s='дерево'
s[2] → 'р'
s[-2] → 'в'

s[i : j
:k]
Срез — подстрока, содержащая символы строки s с номерами от  до  с
шагом  (элемент с номером  входит в итоговую подстроку, а элемент с
номером  уже не входит). Если  не указан (использован вариант s[i :
j]), то символы идут подряд (равносильно s[i : j :1]). Примеры:

s='derevo'
s[3:5] → 'ev'
s[1:5:2] → 'ee'

min(s)
Определяет и выводит (возвращает) символ с наименьшим значением (кодом
– номером в кодовой таблице) Пример:

s='derevo'
min(s) → 'd'

max(s)
Возвращает символ с наибольшим значением (кодом) Пример:

s='derevo'
max(s) → 'v'

Строки, как объекты Python, обладают методами (т.е. функциями, которые выполняют
сами объекты). Основные методы перечислены в следующей таблице. Пусть строка, к
которой применяются эти методы, называется s1.

Таблица 1.4. Методы строк

Метод
Описание и результат

s1.center(n)
Возвращается строка s1, дополненная пробелами справа и слева
до ширины в  символов. Исходная строка не изменяется. Если 

, пробелы не добавляются. Пример:

s1='Zoom-Zoom'
s1.center(15) → '   Zoom_Zoom   '

s1.ljust(n)
Строка s1 выравнивается по левому краю (дополняется
пробелами справа) в пространстве шириной  символов. Если 

, пробелы не добавляются. Пример:

8

s1='Zoom_Zoom'
s1.ljust(15) → 'Zoom-Zoom      '

s1.rjust(n)
Строка s1 выравнивается по правому краю (дополняется
пробелами слева) в пространстве шириной  символов. Если n <
len(s1), пробелы не добавляются. Пример:

s1='Zoom_Zoom'
s1.rjust(15) → '      Zoom-Zoom'

s1.count(s[, i,
j])
Определяется количество вхождений подстроки s в строку s1.
Результатом является число. Можно указать позицию начала
поиска  и окончания поиска  (по тем же правилам, что и
начало и конец среза). Примеры:

s1='abrakadabra'
s1.count('ab') → 2
s1.count('ab',1) → 1
s1.count('ab',1,-3) → 0, потому что
s1[1:-3] → 'brakada'

s1.find(s[, i, j]) Определяется позиция первого (считая слева) вхождения

подстроки s в строку s1. Результатом является число.
Необязательные аргументы  и  определяют начало и конец
области поиска (как в предыдущем случае). Пример:

s1='abrakadabra'
s1.find('br') → 1

s1.rfind(s[, i,
j])
Определяется позиция последнего (считая слева) вхождения
подстроки s в строку s1. Результатом является число.
Необязательные аргументы  и  определяют начало и конец
области поиска (как в предыдущем случае). Пример:

s1='abrakadabra'
s1.rfind('br') → 8

s1.strip()
Создаётся копия строки, в которой удалены пробелы в начале и в
конце (если они есть или образовались в результате каких-то
операций). Пример:

s1=' breKeKeKeKs '
s2=s1.strip()
s2 → 'breKeKeKeKs'

s1.lstrip()
Создаётся копия строки, в которой удалены пробелы в начале
(если они есть или образовались в результате каких-то операций).
Пример:

s1=' breKeKeKeKs '

9

s2=s1.lstrip()
s2 → 'breKeKeKeKs '

s1.rstrip()
Создаётся копия строки, в которой удалены пробелы в конце
(если они есть или образовались в результате каких-то операций).
Пример:

s1=' breKeKeKeKs '
s2=s1.rstrip()
s2 → ' breKeKeKeKs'

s1.replace(s2,s3[,
n])
Создаётся новая строка, в которой фрагмент (подстрока) s2
исходной строки заменяется на фрагмент s3. Необязательный
аргумент n указывает количество замен (если требуется заменить
не все фрагменты). Пример:

s1='breKeKeKeKs'
ss=s1.replace('Ke','XoXo',2)
ss → 'breXoXoXoXoKeKs'

s1.capitalize()
Создаётся новая строка, в которой первая буква исходной строки
становится заглавной (прописной), а все остальные становятся
маленькими (строчными). Пример:

s1='breKeKeKeKs'
s2=s1.capitalize()
s2 → 'Brekekekeks'

s1.swapcase()
Создаётся новая строка, в которой прописные буквы исходной
строки заменяются на строчные и наоборот. Пример:

s1='breKeKeKeKs'
s2=s1.swapcase()
s2 → 'BREkEkEkEkS'

s1.upper()
Создаётся новая строка, в которой все буквы исходной строки
становятся заглавными (прописными). Пример:

s1='breKeKeKeKs'
s2=s1.upper()
s2 → 'BREKEKEKEKS'

s1.lower()
Создаётся новая строка, в которой все буквы исходной строки
становятся маленькими (строчными). Пример:

s1='breKeKeKeKs'
s2=s1.lower()
s2 → 'brekekekeks'

10