17.03.20 Беляков А.Ю.

Алгоритмы и структуры данных

Содержание

№ Pattern coding ref

1 Эффективность алгоритмов тут
2 Рекурсия тут
3 Комбинаторика тут
4 Поиск в тексте тут
5 Область Парето-оптимальных решений тут
6 Алгоритмы сортировки тут
7 Сортировка объектов тут
8 Динамическое программирование тут
9 Алгоритмы на графах тут

№ Free coding ref

1 Алгоритмы анализа данных тут
2 Байки Солнечного города тут
3 Безумное чаепитие тут
4 Матрица тут

=> Примеры тестовых заданий тут

 1. ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ

Прежде всего - алгоритмы сравниваем по двум критериям:

– сложность – обычно определяется временем или количеством операций
(минимальное, максимальное, среднее), но необязательно реально отмерять время
работы или подсчитывать все арифметические и логические операции – обычно
подсчитывают обобщая, например, если алгоритм реализован с помощью
вложенных циклов - цикл по n в цикле по n, то говорят сложность n2;
– объем расходуемой памяти.

Сейчас рассмотрим только изменение сложности алгоритма при решении

однотипной задачи.
Далее, в других темах, например, в «динамике» рассмотрим объём
расходуемой памяти.

Итак, рассмотрим вопрос о количестве операций на примере поиска в

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

Рассмотрим несколько методов на конкретных примерах.

Как найти Фамилию в большом списке?

1 Линейный поиск
2 Бинарный поиск

Как найти точку на графике функции?

3 Тернарный поиск
4 Метод «Золотого сечения»

1 Линейный поиск
Будем работать с текстовым файлом, в каждой строке одно слово, за основу
можно взять список слов русского языка – скачать тут (преобразуйте в подходящую
для вашей системы кодировку): [Link] Содержимое
файла выглядит примерно так:

2
 Данные берём из текстового файла и организуем простой цикл:
word = input("Введите слово для поиска - ")

f = open("[Link]", 'r')
lines = [Link]().split('\n')
[Link]()

for i in range(len(lines)):
if lines[i] == word:
print(i, lines[i])
break
Когда решение найдено, досрочно выходим из цикла.
Оцените минимальное, максимальное и среднее количество шагов поиска
по данному алгоритму.

2 Бинарный поиск
Очевидно, что следует отказаться от последовательного перебора при
поиске. Ускорить алгоритм поиска можно, например, делением диапазона
пополам и определением в какой из половинок располагается искомое слово.
Таким образом на каждом шаге оставшаяся часть диапазона поиска сокращается в
2 раза. Можно дать оценку средней величине временных затрат как log2n, то есть с
ростом мощности исследуемого множества n, затраты на реализацию алгоритма
растут незначительно – логарифмически. Это заметно ниже чем квадратичный рост
(n2 - в простейших алгоритмах сортировки) или линейный рост (n - в линейном
поиске).
word = input("Введите слово для поиска - ")

f = open("[Link]", 'r')
lines = [Link]().split('\n')
[Link]()

mn = 0
mx = len(lines) - 1
pos = (mx + mn) // 2
i = 1
while word != lines[pos]:
if word < lines[pos]:
mx = pos - 1
if word > lines[pos]:
mn = pos + 1
pos = (mx + mn) // 2
3
 i += 1

print(i, lines[pos])

Тут переменная i используется для подсчёта количества шагов алгоритма до

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

3 Тернарный поиск (экстремума функции)

Сначала просто форматированный вывод данных для контроля возможных

значений:
from math import sin, pi

def func(x):
return sin(x)

def to_rad(g):
return g * pi / 180

mn = 0
mx = 180
st = 15
for g in range(mn, mx + 1, st):
# print(g, round(func(to_rad(g)), 3))
# print(g, str(func(to_rad(g)))[:5] )
print("{0:3} - {1:.3f}".format(g, func(to_rad(g))))

Результат работы:
0 - 0.000
15 - 0.259
30 - 0.500
45 - 0.707
60 - 0.866
75 - 0.966
90 - 1.000
105 - 0.966
120 - 0.866
135 - 0.707
150 - 0.500
165 - 0.259
180 - 0.000

Предположим стоит задача найти экстремум функции на интервале от 0 до

0,75 (это в радианах) или от 0 до 135 (это в градусах).
Функция взята очевидная (sin), чтобы заранее было понятно где будет
экстремум. Для однозначности ограничимся тут поиском максимума.

В методе тернарного поиска нужно делить весь диапазон поиска на три

равновеликих отрезка двумя точками и сравнением значений функции в этих
точках определять какой из трёх отрезков точно лишний (оставляя два отрезка для
дальнейшего анализа). Постепенно диапазон поиска сужается, пока не станет
равен или меньше, чем заданная точность поиска (тут это переменная q):
from math import sin, pi
4
def func(x):
return sin(x)

def to_rad(g):
return g * pi / 180

mn = 0
mx = 135
q = 0.01

l, r = mn, mx
while (r - l > q):
ml = l + (r - l) / 3
mr = r - (r - l) / 3
if (func(to_rad(ml)) < func(to_rad(mr))):
l = ml
else:
r = mr

result = (l + r) / 2
print("Оптимум функции тут - {0:.3f}".format(func(to_rad(result))))

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

точности (0,01), то мы бы сделали 9000 шагов до нахождения оптимума (90 / 0,01).

Задание 1.
Допишите программу так, чтобы подсчитать количество шагов до
нахождения оптимума в данном примере. Сравните эффективность
методов.

4 Метод «Золотого сечения»

Есть ещё несколько вариантов организации поиска, например, с

использованием случайных чисел (результат непредсказуем – от 1-го шага до
бесконечности) или метод «Золотого сечения». Данный метод похож на
тернарный поиск, так как на каждом шаге общий диапазон бьётся на три части двумя
точками, сравниваются значения функции в данных точках и отбрасывается тот из
трёх отрезков, в котором точно не будет оптимума. Но есть и отличия, которые
снижают количество вычислений.
Задание 2.
Попробуйте самостоятельно ознакомиться с алгоритмом «Золотого
сечения», написать программу, апробировать её на файле [Link],
сравнить с алгоритмами бинарного и тернарного поиска,
сформулировать – в чём именно состоит экономия в методе «Золотого
сечения» по сравнению с алгоритмом тернарного поиска.

Достаточно подробно метод описан в вики: [Link]

(наберите там в поиске - Метод золотого сечения).

5
 2. РЕКУРСИЯ

2.1. Факториал
2.2. Числа Фибоначчи
2.3. Ханойская башня

2.1. Факториал

Факториал от лат. factorialis — действующий, производящий, умножающий –

это такая функция, она определена на множестве неотрицательных целых чисел,
обозначается как n! и равна произведению всех натуральных чисел от 1 до n
включительно.
Очевидно, что, если в языке программирования есть оператор цикла (не везде
есть), то не составит труда такую функцию написать (сделайте это
самостоятельно):
def for_factorial(n):
...
return result

number = int(input())
print(for_factorial(number))

Но, для понимания и сравнения мы напишем функцию вычисления

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

Пошаговый алгоритм работы рекурсивной функции вычисления факториала числа 3:

1) чтобы найти факториал числа 3, нужно найти факториал числа 2 и умножить на 3;
2) чтобы найти факториал числа 2, нужно найти факториал числа 1 и умножить на 2;
3) если нужно найти факториал числа 1, то в качестве результата верни 1.

def for_factorial(n):
...
return result

def rec_factorial(n):
if n == 1:
return 1
else:
return rec_factorial(n - 1) * n

number = int(input())
print(for_factorial(number))
print(rec_factorial(number))

Точка останова – это условие, при котором рекурсивный перебор следует

остановить, например, чтобы найти факториал 1 не нужно делать рекурсивный

6
вызов, а можно сразу вернуть ответ - это 1.
Шаг рекурсии – эта та часть функции, где происходить её рекурсивный вызов
– функция вызывает сама себя. Если при рекурсивном вызове не будет меняться
значение аргумента функции, то она «зациклится» - будет стоять на месте до тех
пор, пока не переполнится стек вызовов функции (для Питона это 1000).
Как точек останова, так и шагов рекурсии может быть несколько. При
отсутствии точки останова, рекурсивная функция будет вызывать сама себя до тех
пор, пока не переполнится стек вызовов функции.

Задание 3.
Напишите рекурсивную функцию перевода из десятичного числа в
двоичное.

Задание 4.
Напишите рекурсивную функцию перевода из двоичного числа в
десятичное.

7
 2.2. Числа Фибоначчи

Здесь мы рассмотрим пример, в котором использование дополнительной

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

Итальянский купец Леонардо из Пизы (1180-1240), более известный под

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

Ясно, что, если считать первую пару

кроликов новорожденными, то на второй
месяц мы будем по-прежнему иметь одну
пару; на 3-й месяц - 1+1=2; на 4-й - 2+1=3
пары (ибо из двух имеющихся пар
потомство дает лишь одна пара); на 5-й
месяц - 3+2=5 пар (лишь 2 родившиеся на
3-й месяц пары дадут потомство на 5-й
месяц); на 6-й месяц - 5+3=8 пар (ибо
потомство дадут только те пары, которые Рис.1. Схема размножения кроликов.
родились на 4-м месяце) и т. д.
Таким образом, если обозначить число пар кроликов, имеющихся на n-м
месяце через Fk, то F1=1, F2=1, F3=2, F4=3, F5=5, F6=8, F7=13, F8=21 и т.д., причем
поток этих чисел регулируется общим законом:
Fn = Fn-1 + Fn-2
при всех n>2, ведь число пар кроликов на n-м месяце равно числу Fn-1 пар кроликов
на предшествующем месяце плюс число вновь родившихся пар, которое совпадает
с числом Fn-2 пар кроликов, родившихся на (n-2)-ом месяце (ибо лишь эти пары
кроликов дают потомство).
Числа Fn, образующие последовательность 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, ... называются "числами Фибоначчи", а сама последовательность -
последовательностью Фибоначчи.
Итак, в последовательности Фибоначчи начиная с 3-го каждое следующее число
получается сложением двух предыдущих, но почему эта последовательность стала столь
известной?
Дело в том, что при увеличении порядковых номеров отношение двух соседних чисел
последовательности асимптотически стремится к некоторому постоянному соотношению.
Так, если какой-либо член последовательности Фибоначчи разделить на предшествующий
ему, результатом будет величина, близкая к 1,61803398875 – это отношение известно, как
«золотое сечение». В алгебре общепринято его обозначение греческой буквой φ (фи).
8
 Принято считать, что объекты, содержащие в себе «золотое сечение», воспринимаются
людьми как наиболее гармоничные. Пропорции пирамиды Хеопса, храмов, барельефов,
предметов быта и украшений из гробницы Тутанхамона якобы свидетельствуют, что
египетские мастера пользовались соотношениями золотого сечения при их создании.
Начиная с Леонардо да Винчи, многие художники сознательно использовали пропорции
«золотого сечения». Известно, что Сергей Эйзенштейн искусственно построил фильм
Броненосец Потёмкин по правилам «золотого сечения». Он разбил ленту на пять частей. В
первых трёх действие разворачивается на корабле. В двух последних – в Одессе, где
разворачивается восстание. Этот переход в город происходит точно в точке золотого сечения.
Да и в каждой части есть свой перелом, происходящий с учетом пропорции «золотого
сечения». Эйзенштейн считал, что такие переходы воспринимаются как наиболее
закономерные и естественные.
Тем не менее, существуют исследования показывающие, что значимость золотого
сечения в искусстве, архитектуре и в природе преувеличена. При обсуждении оптимальных
соотношений сторон прямоугольников (размеры листов бумаги A0 и кратные, размеры
фотопластинок (6:9, 9:12) или кадров фотоплёнки (часто 2:3), размеры кино- и
телевизионных экранов – например, 3:4 или 9:16) были испытаны самые разные варианты.
Восприятие гармонии слишком индивидуально и не все принимают «золотое сечение» как
оптимальное, удобное или комфортное.

Итак, последовательность чисел Фибоначчи можно задать таблицей:

порядковый
1 2 3 4 5 6 7 8 9 10
номер
значение
1 1 2 3 5 8 13 21 34 55
числа

или словами: первое и второе число равны единице, а каждое последующее есть
сумма двух предшествующих. Формально это можно выразить так:
Число 1 = 1
Число 2 = 1
Число N = Число(N-1) + Число(N-2)
Напишем соответствующую программу, в основе которой лежит рекурсивная
функция fib:
def fib(n):
if n < 3:
return 1
else:
return fib(n-1) + fib(n-2)

n = int(input("Введите номер числа - "))

print(fib(n))

Недостаток такой организации функции состоит в том, что при вычислении

очередного N-го числа происходит многократное перевычисление предыдущих
чисел Фибоначчи. Чтобы избежать многократного рекурсивного пересчёта одних и
тех же чисел, можно предложить подход, основанный на сохранении результатов
вычислений в специальной таблице (список, массив).
Когда возникает запрос на вычисление числа Фибоначчи программа смотрит
его наличие в списке, если его нет, то вызываем рекурсивную функцию для поиска
9
его значения, если есть, то берём его из списка.
Попробуем придать этим рассуждениям некоторое материальное
воплощение:
def fib(n):
if n < 3:
return 1
else:
fib_2 = tab[n - 2] if tab[n - 2] > 0 else fib(n - 2)
fib_1 = tab[n - 1] if tab[n - 1] > 0 else fib(n - 1)
tab[n - 2] = fib_2
tab[n - 1] = fib_1
return fib_1 + fib_2

n = int(input("Введите номер числа - "))

tab = [0] * n
print(fib(n))

Решение с сохранением промежуточных результатов называют решением с

«меморизацией».

Испытайте оба варианта (без таблицы для хранения промежуточных

результатов и с ней) реализации функции поиска числа Фибоначчи для достаточно
больших номеров и почувствуйте разницу во времени работы. Только не ставьте
сразу большие значения, иначе попросту не дождётесь ответа. Попробуйте для
начала вычислить число Фибоначчи с порядковым номером от 35 до 45 (зависит
от производительности вашей «машины») – разница во времени вычисления будет
почти незаметна. Но, если вы будете постепенно наращивать значения номера
числа, то вскоре вы поймете насколько может быть полезно выделение
дополнительной памяти для хранения промежуточных результатов. В такой
реализации расход памяти увеличивается незначительно, но производительность
резко возрастает.

Внимательный читатель заметит, что последняя реализация (с таблицей)

тоже несколько избыточна, так как на каждом шаге рекурсии ставится вопрос о
поиске двух значений Фибоначчи, но при поиске любого из них образуется целая
ветвь вычислений с сохранением всех промежуточных результатов и для второй
ветви вычислений уже можно не спрашивать: есть ли число в таблице:
def fib(n):
if n < 3:
return 1
else:
if tab[n - 1] == 0:
tab[n - 1] = fib(n - 1)
return tab[n - 1] + tab[n - 2]

n = int(input("Введите номер числа - "))

tab = [0] * n

10
tab[1] = 1
tab[2] = 1
print(fib(n))

Однако, именно в этой задаче, можно было бы обойтись обычным циклом от

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

Задания для самостоятельного исполнения

Задача 5. Число Фибоначчи циклом.

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

Задача 6. Магазин (без «меморизации»).

На расстоянии n шагов от магазина стоит человек. Каждую секунду он
выбирает, куда сделать шаг: к магазину или в противоположном
направлении. Напишите программу, которая определит, сколькими
способами он может попасть в магазин, пройдя ровно k шагов и
оказавшись в магазине только после выполнения последнего шага.
На вход подаются через пробел два целых числа n – расстояние до
магазина в шагах и k – требуемое количество шагов, которые должен
сделать человек (1 ≤ n ≤ k ≤ 37). На выход следует подать только одно
число - количество способов попадания в магазин.
Примеры:
входные данные 35 33 5 15
выходные данные 3 1 1001
Реализацию задачи 2 следует выполнить обыкновенной рекурсией без
«меморизации».

Задача 7. Магазин («с меморизацией»).

Условие этой задачи совпадает с предыдущей, но реализацию следует
выполнить рекурсией с «меморизацией».

Следует отметить, что даже рекурсия «с меморизацией» имеет

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

11
 2.3. Ханойская башня

Одна легенда гласит, что в Великом храме города Бенарес, под собором,
отмечающим середину мира, находится бронзовый диск, на котором укреплены 3
алмазных стержня, высотой в один
локоть и толщиной с пчелу. Давным-
давно, в самом начале времён, монахи
этого монастыря провинились перед
богом Брахмой. Разгневанный Брахма
воздвиг три высоких стержня и на один
из них возложил 64 диска, сделанных из
чистого золота. Причём так, что каждый меньший диск лежит на большем.
Как только все 64 диска будут переложены со стержня, на который Брахма
сложил их при создании мира, на другой стержень, башня вместе с храмом
обратятся в пыль и под громовые раскаты погибнет мир.
Количество перекладываний в зависимости от количества колец вычисляется
по формуле 2n-1.
Число перемещений дисков, которые должны совершить монахи, равно 18
446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую
секунду одно перемещение диска, их работа продолжалась бы почти 585
миллиардов лет.
Эту легенду как и саму игру придумал французский
математик Эдуард Люка в 1883 году, её продавали как забавную
игрушку. Первоначально она называлась «Профессор Клаус
(Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)», но вскоре
обнаружилось, что таинственный профессор из несуществующего
колледжа - не более чем анаграмма фамилии изобретателя игры,
профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).

Итак, даны три стержня, на один из которых нанизаны несколько колец,

причём кольца отличаются размером и лежат меньшее на большем. Задача состоит
в том, чтобы перенести пирамиду из n колец за наименьшее число ходов на другой
стержень. За один раз разрешается переносить только одно кольцо, причём нельзя
класть большее кольцо на меньшее.
Будем решать задачу переноса n колец с первого стержня на второй. Для
удобства наименования обозначим кольца номерами: 1, 2, 3. Пусть нужно все
кольца перенести со стержня с номером 1 на стержень с номером 2.

12
 Опишем рекурсивную функцию в обобщённом виде:
шаг 0: исходное состояние

шаг 1: перенесём n-1 колец с первого

стержня на третий
шаг 2: перенесём 1 большое кольцо с
первого стержня на второй
шаг 3: перенесём n-1 колец с третьего
стержня на второй

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

остальные шаги подразумевают некоторую последовательность движений.
Как видите, задача переноса n колец состоит из двух подзадач поменьше
(сложностью n-1) – это и есть реализация рекурсивных вызовов. В реализации
рекурсивной функции кроме шага рекурсии нужна ещё и точка останова – в данном
случае будем делать перебор пока есть ещё хотя бы одно кольцо на стержне, то
есть при n>0.

В программе сначала
устанавливаем количество
колец на первом стрежне n,
затем запускаем рекурсивную
функцию для n колец.

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

Код Результат
def Tower(n, a, b, c): Код функции
from 1 to 2
if n>0: from 1 to 3
Tower(n-1, a, c, b) from 2 to 3
print('from', a, 'to', b) from 1 to 2
from 3 to 1
Tower(n-1,c,b,a)
from 3 to 2
from 1 to 2
n = 3 Код программы
Tower(n,1,2,3)

13
 Можно немного усложнить себе задачу и сделать пошаговый показ того, как
кольца от шага к шагу мигрируют между стержнями:
Код Результат
def printTower(x,y): start Tower => 3 0 0
global lst from 1 to 2 => 2 1 0
lst[x-1] -= 1 from 1 to 3 => 1 1 1
lst[y-1] += 1 from 2 to 3 => 1 0 2
print(*lst)
from 1 to 2 => 0 1 2
from 3 to 1 => 1 1 1
def Tower(n, a, b, c):
from 3 to 2 => 1 2 0
if n>0:
Tower(n-1, a, c, b) from 1 to 2 => 0 3 0
print('from', a, 'to', b, '=>', end='')
printTower(a,b)
Tower(n-1,c,b,a)

n = 3
lst = [n,0,0] # количество колец на стержнях
print('start Tower =>', *lst)
Tower(n,1,2,3)

Задание 8. Ханойская башня.

Реализовать программу для вывода пошагового решения «Ханойской
башни» и уметь пояснить рекурсивный алгоритм решения.

14
 3. КОМБИНАТОРИКА

Как выбрать лучшую комбинацию элементов из некоторого множества

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

Пусть вместимость контейнера = 100 кг.

№ Масса Ценность Ценн./Вес
1 50 100 2,0
2 40 90 2,25
3 30 80 2,66
4 20 70 3,5

Что выбрать в заданных ограничениях:

- лучшие по абсолютной ценности или
- лучшие по относительной ценности?

Пусть вместимость контейнера = 100 кг.

№ Масса Ценность Ценн./Вес
1 40 30 9/12
2 30 40 16/12
3 20 30 18/12
4 20 20 12/12

Возможный подход – использовать дискретный жадный алгоритм.

Что выбрать в заданных ограничениях ща критерий сортировки:
- лучшие по относительной ценности или
- полный перебор всех комбинаций?

Поможет ли жадный (дискретный) алгоритм?

тут можно самостоятельно выполнить решение

или рассмотрим на Лекции
или реализуем на лабораторном занятии

15
 Решающие алгоритмы:
Перебор подмножеств (бинарные маски)
Порождение перестановок (рекурсия)
Поиск решения методом динамического программирования.

Сначала рассмотрим вспомогательный алгоритм – рекурсивное

порождение подмножеств.

Порождение подмножеств (рекурсия):

lst = ['a','b','c','d']
tmp = []

def getSubsets(k):
global tmp
if k == len(lst):
print(*tmp)
else:
[Link](lst[k])
getSubsets(k+1)
[Link]()
getSubsets(k+1)

Далее три варианта решения

1. Перебор подмножеств (бинарные маски):

lst = ['a','b','c','d']
tmp = []

def getSubsetsBin():
n = len(lst); count = 2**n
for variant in range(count):
tmp = []
for pos in range(n):
if (1 << pos) & variant:
[Link](lst[pos])
print(variant, '\t', *tmp)

2. Порождение перестановок (рекурсия):

lst = ['a','b','c','d']
tmp = []
choice = [False] * len(lst)

def getPermutations():
if len(tmp) == len(lst):
print(*tmp)
16
 else:
for i in range(len(lst)):
if not choice[i]:
choice[i] = True
[Link](lst[i])
getPermutations()
choice[i] = False
[Link]()

3. Поиск решения методом динамического программирования:

Его желательно рассмотреть после изучения одномерной динамики и

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

17
 4. Поиск в тексте

В текстовых редакторах, поисковых машинах, браузерах, в систе-

мах проверки на плагиат и других средствах работы с информацией
часто встречается задача поиска подстроки в строке. При реализации
соответствующей функции принято обозначать шаблон поиска как
needle (с англ. — «иголка»), а строку (текст), в которой ведётся поиск —
как haystack (с англ. — «стог сена»).
Рассмотрим два алгоритма:
1. наивный алгоритм;
2. алгоритм Бойера-Мура.

1. Наивный алгоритм.
Это простейший поиск, который предполагает последовательное
сравнение шаблона поиска с символами основного текста, начиная с
самой левой позиции и, в худшем случае, завершая позицией, равной
длина текста минус длина шаблона поиска.
Допустим, что нужно в тексте "Раму мыла мама" найти подстроку
"мама".
Для наглядности представим шаги поиска наивным алгоритмом
в виде последовательных строк таблицы:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 Р а м у м ы л а м а м а
1 м а м а
2 м а м а
3 м а м а
4 м а м а
...

10 м а м а
11 м а м а

На первом шаге работы алгоритма "приложим" искомую строку

"мама" к самой левой (с индексом 0) позиции текста. Сравним посим-
вольно слева-направо символы искомой строки и текста. При несов-

18
падении хотя бы одного символа сдвигаем строку поиска на один сим-
вол вправо и снова производим посимвольное сравнение слева-
направо по всей длине строки поиска.
haystack = "Раму мыла мама"
needle = "мама"

haystack = [Link]()
needle = [Link]()

'''
Наивный алгоритм:
двойной цикл и сравнение символов слева-направо
'''
result = "Строка не найдена"
for pos in range(len(haystack)-len(needle)):
for i in range(len(needle)):
if needle[i] != haystack[pos+i]:
break
if i == len(needle)-1:
result = pos
break
print(result)
Эффективность такого алгоритма невысока, так как при большом
количестве частичных совпадений оценка мощности поиска будет
приближаться к O(len(haystack)·len(needle)), а при малом числе частич-
ных совпадений (когда внутренний цикл выполняется только один раз)
оценка снижается до len(haystack)-len(needle).

2. Алгоритм Бойера-Мура.
При рассмотрении наивного алгоритма было показано, что про-
исходит множество заведомо излишних проверок. Преимущество ал-
горитма Бойера-Мура в том, что часть проверок пропускаются как за-
ведомо не дающие результата. Это достигается ценой некоторого ко-
личества предварительных вычислений над шаблоном поиска, после
чего шаблон можно сравнивать с исходным текстом не во всех пози-
циях. Рассмотрим пример: текст "Большой корабль" и подстрока для
поиска в нём "кора". При первом же сравнении мы понимаем, что под-
строка не совпадает с тестом, далее перед нами стоит выбор как далеко
вправо сдвинуть шаблон поиска на один символ или больше. Так вот,
посмотрим на позицию в основной строке напротив последнего сим-
вола в шаблоне поиска - это символ "ь". Внимание вопрос: а есть ли
этот символ в шаблоне поиска? Конечно нет! А значит нет смысла пе-
репроверять все позиции и можно сдвинут шаблон сразу на следующий
19
после "ь" символ. Там также повторяется ситуации отсутствия символа
" " в шаблоне поиска и на третьем шагу поиска мы уже находим пози-
цию искомой подстроки в строке:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 Б о л ь ш о й к о р а б л ь

1 к о р а

2 к о р а

3 к о р а

При наивном поиске мы бы затратили в три раза больше времени

даже для такого короткого текста.
Итак, первый вывод: если мы сталкиваемся с символом основ-
ного текста, которого нет в шаблоне поиска, то шаблон сдвигаем на
позицию, следующую за этим отсутствующим символом.
Второй вывод, при сопоставлении шаблона поиска с текстом будем
проверять последовательно символы с конца шаблона, чтобы обеспе-
чить наибольший сдвиг в случае отсутствия символа.
А как поступать, если последний символ шаблона совпал с сим-
волом в основном тексте, а несовпадения происходят на каких-то дру-
гих позициях?
Рассмотрим простейший пример, чтобы прояснить ситуацию. Да-
лее представлен текст и шаги поиска подстроки в нём:
туман скрывал обман
обман
обман
обман
обман
На первом шаге поиска начинаем с крайней левой позиции и про-
веряем справа-налево по шаблону: "ман" совпало с символами в ос-
новной строке, далее "б" не совпало с "у", тогда сдвигаем на позицию,
сразу за символом "н", так как он в шаблоне поиска более нигде не
встречается, а крайнюю позицию мы уже проверили с неудачным ре-
зультатом. На втором шаге поиска сравниваем "н" с "ы" - несовпадение,
сдвигаем сразу за "ы", так как её нет в шаблоне. А вот на третьем шаге
поиска мы встречаемся с ситуацией, когда "н" не совпало с "о", но сим-

20
вол "о" встречается в шаблоне, поэтому сдвигаем так, чтобы совме-
стить "о" из шаблона с "о" в тексте, то есть на расстояние символа "о"
от правого края шаблона.
Итак, основная идея алгоритма состоит в том, чтобы сдвигать
подстроку поиска настолько далеко вправо за один шаг насколько это
возможно, чтобы не пропустить позицию ответа. Важная особенность
состоит в том, что, если символ, стоящий в основном тексте напротив
последнего символа шаблона встречается в шаблоне не один раз, то
сдвигаем шаблон вправо на расстояние от правой границы шаблона до
этого символа (исключая самый правый).
Проанализируйте шаги поиска подстроки в тексте по примеру,
приведенному в следующей таблице:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 Р а м у м ы л а м а м а

1 м а м а

2 м а м а

3 м а м а

4 м а м а

Оказывается, что для реализации такого алгоритма нужно знать

насколько далеко можно сдвинуть шаблон вправо, если сейчас он не
совпал с текстом. Чтобы не определять это каждый раз в момент по-
иска, проделывая одни и те же вычисления многократно, разумнее бу-
дет заранее составить словарь, в котором для каждого символа из тек-
ста определить величину сдвига. Если же символа нет в шаблоне, то
величина сдвига будет равна длине шаблона.
Словарь - это структура данных, представленная парами значений
- (ключ, величина), причем все ключи должны быть уникальными.
Таким образом реализация поиска будет содержать два этапа:
 подготовку словаря,
 поиск позиции подстроки.
Проанализируйте возможную реализацию алгоритма поиска
подстроки в строке методом Бойера-Мура:
haystack = "Раму мыла мама"
needle = "мама"

haystack = [Link]()
needle = [Link]()
21
# шаг 1 - составим словарь пар (символ, сдвиг)

d = {} # объявили словарь
setText = set(haystack) # сбросили во множество, чтобы сократить перебор
for char in setText: # тут перебор по множеству символов
d[char] = len(needle) # инициализируем значениями, равными длине needle

# можно проверить - все ли символы из needle встречаются во множестве setText

# если нет, то и поиск бесполезен

for pos in range(1, len(needle)): # крайний справа не берём, поэтому от 1

char = needle[len(needle)-1-pos] # символ может и не оказаться в тексте
if char in [Link]() and pos < d[char]:
d[char] = pos

print(d) # тут можно оценить сформированный словарь

# шаг 2 - поиск подстроки

# pos - позиция левой границы шаблона
pos = 0; result = -1
while pos <= len(haystack)-len(needle):
# print(pos)
for i in range(len(needle)-1, -1, -1):
if needle[i] != haystack[pos+i]:
pos += d[haystack[pos+len(needle)-1]]
break
if i == 0:
result = pos
break

print("Слово не найдено" if result == -1 else "Позиция = " + str(result))

Таким образом, алгоритм Бойера-Мура ненамного сложнее наив-

ного алгоритма, но даёт заметный прирост в скорости поиска позиции
подстроки в тексте.
Задача для самостоятельной реализации:
1. вам предоставлен текстовый файл ([Link] ска-
чайте и разместите в папке с программой - при запуске вашей программы нужно
будет открыть этот файл и загрузить содержимое в переменную haystack;
2. добавьте диалог: пользователь сам вводит подстроку поиска needle с клавиа-
туры;
3. напишите три функции: для поиска наивным методом, для подготовки словаря
и поиска методом Бойера-Мура;
4. все функции нужно разместить в один модуль и подключить его к основной про-
грамме;
5. подготовиться в подробностях ответить на вопросы о работе обоих методов и
об их реализации на языке программирования;
6. добавить в модуль функцию предварительной проверки наличия всех символов
из подстроки needle во множестве setText (если нет, то и поиск бесполезен) и
применить её для оптимизации поиска.

22
23
 5. Область оптимальных решений.
Задания для самостоятельного исполнения.

Одно комплексное задание.

Дан входной текстовый файл [Link]:

1 samsung a1 17 3
2 samsung a2 15 4
3 samsung a3 13 4
4 samsung a4 7 6
5 samsung a5 5 5
6 samsung a6 5 8
7 samsung a7 7 9
8 samsung a8 9 10
9 samsung a9 7 11
10 iphone x10 3 13
11 iphone 7 9 12
12 samsung 8 12 9
13 samsung se 14 7

Каждая строка файла – запись про один телефон. Запись состоит из

четырёх полей: id, name, time, power. Поля разделены символом
табуляции (можно использовать другой символ). Наименования и
величины условны.

Техническое задание.
Разработать программу со следующим функционалом:
1) разработать класс Smartphone для хранения данных об
объектах, объекты – это телефоны;
2) считать данные из файла [Link] и поместить их в список
объектов;
3) отсортировать список по убыванию по производительности
смартфонов (поле power) и вывести три лучших;
4) отсортировать список по убыванию по продолжительности
работы (поле time) и вывести три лучших;
5) выбрать объекты, которые находятся в области Pareto (см.
рисунок) и вывести данные о них в текстовый файл [Link].
Выводить данные в том же формате, как они были во входном
файле.

Декларацию класса и все функции обработки данных разместить в

модуле [Link]. Основная программа должна обращаться к функциям из
этого модуля.
24
 6. Алгоритмы сортировки

Рассмотрим несколько разных алгоритмов и сравним их по времени и

потребляемой памяти.

Сортировка:
пузырьковая
выбором
вставкой
пирамидальная
быстрая (рекурсивный метод)
перечислением

25
 7. Объекты и сортировка.
Задания для самостоятельного исполнения.
Вспомогательные материалы
смотрите в Презентациях Лекций…

Пусть дан текстовый файл:

№ Фамилия Имя Отчество Возраст Средний балл
1 Абрамович Петя Иванович 24 4.5
2 Кокорин Петро Петрович 18 3.8
3 Саакашвили Адольф Семёнович 33 4.1
4 Папов Коля Олич 19 4.4
5 Некто Оле Лукойе 14 3.3

тут пробел
тут табуляция

Первая строка служебная и не участвует в обработке информации,

но присутствует в файле и нужна только для наглядности
представления информации. Во время чтения данных из файла учтите
это и первую строку не включайте в список для обработки данных.
Разделителем для столбцов Номер, «Фамилия Имя Отчество», Возраст,
«Средний балл» является символ табуляции, а Фамилия Имя Отчество
разделены пробелом.
Во время выполнения заданий данные из файла сначала
считывайте в список объектов, потом уже ведите обработку этого
массива в разных заданиях по-разному. Файл с указанными
параметрами структуры создайте самостоятельно и выполните для
него с использованием объектно-ориентированного стиля следующие
задания:

1. Вывести в столбик на экран Фамилии и Инициалы студентов в виде:

Абрамович П.И.
Кокорин П.П.
Саакашвили А.С.
Папов К.О.
Некто О.Л.

2. Вывести на экран в столбик Возраст и, через пробел, Фамилии и

26
 Инициалы совершеннолетних студентов:
24 Абрамович П.И.
18 Кокорин П.П.
33 Саакашвили А.С.
19 Папов К.О.

3. Вывести на экран в столбик Возраст, Средний балл и Фамилии и

Инициалы студентов, у которых Средний балл выше, чем средний
балл в группе, отсортировав (можно использовать любой метод
сортировки) их по возрасту:
19 4.4 Папов К.О.
24 4.5 Абрамович П.И.
33 4.1 Саакашвили А.С.

4. Напишите модуль [Link] в котором разместите функцию

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

5. Добавьте в модуль функцию сортировки методом пузырька.

Объясните алгоритм сортировки «пузырьком».

6. Добавьте в программу возможность измерения времени

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

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

Динамическое программирование — способ решения сложных задач путём

разбиения их на более простые подзадачи, позволяющий значительно сократить
время вычислений по сравнению с "наивными" методами полного перебора. По-
кажу суть "динамики" на простом примере: чтобы найти факториал числа 5 - нужно
найти факториал числа 4 и умножить его на 5. Мы декомпозировали задачу и ре-
курсивно вызвали для решения более простую задачу поиска факториала числа 4,
которую, в свою очередь, можно решить аналогичным способом: чтобы найти фак-
ториал числа 4 - нужно найти факториал числа 3 и умножить его на 4. Так будем
продолжать до тех пор, пока не встретимся с элементарной задачей, для которой
уже не нужен рекурсивный вызов - в данном примере это факториал числа 1, рав-
ный единице.

def factorial(n) {
if n == 1:
return 1
else:
return factorial(n-1) * n

n = 5
print(factorial(n))

# нисходящий и восходящий пути рекурсии

После того как мы добрались до самого "низа" рекурсивных вызовов, нашли

решение для элементарной подзадачи factorial(1)=1, следует произвести в обрат-
ном порядке все отложенные вычисления: 1*2*3*4*5. Таким образом, на прямом
ходе рекурсии происходят декомпозиции сложных задач на простые, а на обрат-
ном ходе - происходят необходимые вычисления.
Это и есть так называемое динамическое программирование "снизу", осно-
ванное на декомпозиции сложной задачи на рекурсивную последовательность бо-
лее простых подзадач. Однако, при решении практических задач с помощью ре-
курсии можно встретиться с рядом недостатков реализации через рекурсивные
функции, таких как ограничения на количество рекурсивных вызовов и многократ-
ный пересчет одних и тех же значений. В этом случае более эффективным оказы-
вается динамическое программирование "сверху".
Метод динамического программирования сверху заключается в последова-
тельном решении частных подзадач основной задачи, начиная с элементарных, с
запоминанием результатов их решения для использования в дальнейшем. Для луч-
шего понимания разберем задачу "Минимальная цена пути ".

28
 Минимальная цена пути

Пусть есть прямоугольная таблица N×M, в каждой клетке которой записано

некоторое целое число. Игрок находится в левой верхней клетке. За один ход ему
разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и
вверх перемещаться запрещено). При проходе через клетку (включая и первую и
последнюю клетки таблицы) с игрока берут столько монет, сколько записано в
этой клетке.
Требуется найти минимальное количество
монет при проходе до выхода из таблицы из пра- 1 1 1 1
вого нижнего угла. На рисунке вы видите мини-
мальный путь, выделенный цветом. Итоговая стои- 5 2 2 10
мость прохода по этим клеткам равна 8, так как
9 4 2 1
1+1+1+2+2+1=8.

Входные данные
В первой строке ввода задано два числа N и M - размеры таблицы (1 ≤ N ≤ 20,
1 ≤ M ≤ 20).
В последующих N строках по M чисел в каждой - стоимость соответствую-
щих клеток таблицы (целые числа от 0 до 100).
Выходные данные
Выведите одно целое число - это количество монет за минимальную стои-
мость прохода от входа до выхода из таблицы.
Примеры
№ INPUT OUTPUT

1 3 4 8
1 1 1 1
5 2 2 10
9 4 2 1

2 5 5 11
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1
Если решать задачу поиска пути "наивным" методом полного перебора, то
мы встретимся с "проклятием размерности" - на каждом шаге выбор делается
между двумя возможными траекториями, таким образом порождается бинарное де-
рево решений. Например, в таблице со сравнительно небольшой размерностью
21Х21 чтобы дойти от левого верхнего угла только до середины таблицы (второ-
степенная диагональ) нужно будет перебрать 2^20 путей, то есть более миллиона
вариантов – попробуйте сами нарисовать небольшую таблицу, например, размером
4Х4 и подсчитать общее количество возможных путей от угла до диагонали.

29
 Рассмотренный алгоритм не подходит для оперативного принятия решения,
например, в играх. Представьте, что вам нужно в динамичной сцене 2D-игры вы-
числять оптимальные пути для 10 бойцов на сравнительно небольшом поле 100 на
100 (сами оцените порядок вычислений).
К примеру, для данной карты общее количество возможных вариантов путей
(из угла в угол) около 140 миллиардов:

Проход по каждому блоку определённого вида территории снимает

сколько-то пунктов из энергии бойца, поэтому имеет смысл выбирать оптималь-
ный путь, но за минимально возможное время, чтобы игра не лагала…
Таким образом, для некоторых задач недостаточно давать правильный ответ,
ещё необходимо обеспечить оперативность его вычисления!
Очевидно, что в реальных задачах могут встретиться иные требуемые траек-
тории – не из угла в угол, а от некоторой начальной точки до некоторой конечной.
Но на предлагаемой в этом разделе упрощенной задаче можно понять принцип
двумерной динамики как способа снижения размерности поиска решения.

* * * * *

Попробуем изменить стратегию поиска - давайте будем на каждом шаге в

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

30
 Далее приведено пошаговое решение задачи поиска минимальной длины
пути. Обратите внимание, что итоговая таблица «потребляет» данные из исходной
– в исходной приведены «стоимости» каждой отдельной ячейки, а в итоговой «сто-
имость» прохода по минимальному пути до каждой ячейки:
Исходная таблица: Длины путей по границам:
1 1 1 1 1 2 3 4

5 2 2 10 6

9 4 2 1 15

Выбор длины пути из двух вариантов - Заполняем пошагово слева-направо по

путь слева даёт 6+2=8, сверху - 2+2=4, строкам всю таблицу, при каждом пар-
выбираем меньший: ном сравнении выбираем меньший:
1 2 3 4 1 2 3 4

6 4 6 4 5 14

15 15 8 7 8

После заполнения таблицы в крайней справа внизу ячейке будет записан

результат - минимальный путь по всей таблице.

Напишем соответствующую реализацию алгоритма на языке Python:

n, m = map(int, input().split())

tab = []
for i in range(n): # ввод исходной таблицы
[Link](list(map(int, input().split()[:m])))

for y in range(1,n): # заполняем путь по левому столбцу

tab[y][0] += tab[y-1][0]
for x in range(1, m): # заполняем путь по верхней строке
tab[0][x] += tab[0][x - 1]

for y in range(1, n): # перебор таблицы по вертикали

for x in range(1, m): # перебор таблицы по горизонтали
tab[y][x] = # в этом месте добавьте свой код

print(tab[n - 1][m - 1]) # результат из крайней справа снизу ячейки

1. В данной программе оставлено место для заполнения логики выбора на

каждом шаге сравнения – заполните его самостоятельно.
2. Дайте оценку эффективности такого алгоритма, например, для матрицы
10Х10 и сравните с асимптотикой предыдущего варианта алгоритма по-
иска минимального пути.

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

1 1 10 10

1 1 1 1
Как видите из левой верхней ячейки можно сделать ход на один шаг вниз
или вправо. Но из следующей справа ячейки сразу (и только) на 10 ячеек вниз или
вправо, то есть с "вылетом" из таблицы. Такой ход недопустим, а задача форму-
лируется так, чтобы дойти именно до нижней правой ячейки. Так что для приве-
денной таблицы возможны только два пути от входа до выхода (по клеткам стои-
мостью 1).

Как же нужно поступить при решении данной задачи, чтобы успешно приме-
нить принципы динамического программирования?

Количество путей в матрице

Прямоугольное поле размерностью N×M заполняется целыми неотрица-

тельными числами. Цель состоит в том, чтобы пройти по любому разрешенному
пути от верхнего левого угла до правого нижнего. Целое число в каждой клетке
указывает, какой длины шаг должен быть из текущей клетки. Все шаги могут быть
или направо, или вниз. Запрещены шаги за пределы поля игры.
На рисунке 1 приведен пример поля 3×4, где сплошная окружность показы-
вает положение начала, а пунктирная – цель. Рисунок 2 содержит три таблицы – это
три возможных варианта движения от начала до цели для рассматриваемого при-
мера поля, с удаленными промежуточными числами для наглядности.

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

вариантов путей от верхнего левого угла до правого нижнего.
Входные данные
Первая строка задает размеры поля N (1 ≤ N ≤ 70) и M (1 ≤ M ≤ 70).

32
 Следующие N строк описывают отдельную строку игрового поля - это за-
писанные через пробел M целых чисел от 0 до 100 – длины шагов из клеток данной
строки.
Выходные данные
Вывести одно число - количество различных вариантов путей от верхнего
левого угла до правого нижнего. Для каждого поля будет менее чем 2^31 различ-
ных путей.
Пример:
№ INPUT OUTPUT

1 3 4 3
2 1 1 2
3 2 1 44
3 1 1 0

Очевидно, что оптимальное решение этой задачи можно построить анало-

гично задаче "Минимальный путь в таблице", только учитывать будем не длину
пути до данной ячейки, а количество путей до неё.
Шаг 1: читаем входные данные.
Шаг 2: устанавливаем путь до первой - левой верхней ячейки, равный 1.
Шаг 3: перебираем построчно всю таблицу запоминая в ячейках данные.
Шаг 4: выводим результат из правой нижней ячейки.

Особенность реализации состоит в том, что ранее мы могли вносить данные

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

Пусть дана таблица:

Из крайней справа внизу ячейки уже ни- 1 1 2
куда не ходим, поэтому там стоит 0. Без
алгоритма, вручную, мы можем посчи- 1 1 1
тать, что в ячейку, которая выделена
красным мы можем дойти шестью пу- 2 1 0
тями.

Количество путей на входе – в левой

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

Записывая в соответствующие ячейки

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

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

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

Итоговая таблица будет изначально за- 1 1 1

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

Продолжаю заполнять итоговую таб- 1 1 2

лица, выбирая данные по длинам
прыжков из исходной - тут хранятся 1 1 1
только длины прыжков:
2 1 1

Вид итоговой таблицы после третьей 1 1 1

итерации - тут количества путей:
1 2 2

1 2 2

34
 В правой нижней ячейке записано 2 пути, так как туда будет прыжки из верх-
ней правой ячейки (там длина 2) и из левой нижней (и там длина 2). В предпо-
следние ячейки записаны двойки, так как туда возможны пути только из централь-
ной ячейки, до которой количество путей равно 2.

В последней ячейке уже было накоп- 1 1 1

лено 2 пути и к ним добавились 2 пути
из верхней ячейки и 2 из левой - всего 1 2 2
6 путей. Вид таблицы после последней
итерации: 1 2 6

Изучите реализацию алгоритма:

n, m = map(int, input().split())

tab = []
for i in range(n): # ввод исходной таблицы
[Link](list(map(int, input().split()[:m])))
res = [[0]*m for _ in range(n)] # итоговая таблица

res[0][0] = 1
for y in range(n): # все строки
for x in range(m): # все столбцы
step = tab[y][x] # длина прыжка
if step > 0:
if x+step<m: # если в пределах таблицы
# тут добавьте свой код
if y+step<n: # если в пределах таблицы
# тут добавьте свой код

print(res[n-1][m-1]) # результат из крайней справа снизу ячейки

3. В данной программе оставлено место для заполнения логики выбора на

каждом шаге сравнения – заполните его самостоятельно.
4. Дайте оценку асимптотики такого алгоритма.

35
9. Алгоритмы на графах

0 1 0

1 2 2 0 1 2

4 3 4 5 6

а) б) в)

36
 1. Алгоритмы анализа данных.
Задания для самостоятельного исполнения.

1. Свой-Чужой
Жители племени «Тумба-Юмба» единственные в долине, которые
умеют правильно отвечать на один особенный вопрос. По
правильному ответу их можно отличить от жителей других племён.
Вот этот вопрос: назовите сумму целых чисел от 1 (включительно)
до N (включительно). Не стоит недооценивать задачу, ведь N может
быть отрицательным.
Напишите программу для проверки жителей. На вход в консоли с
клавиатуры вводится одно целое число N (по модулю не более 104), а
на выход – на экран выводится искомая сумма.

2. Дороги
В племени «Тумба-Юмба» есть N точек для охоты, некоторые из
которых соединены тропами. Вождь племени решил провести
инвентаризацию троп. Но, он не силен в математике, поэтому он
просит вас сосчитать количество дорог. Требуется написать
программу, помогающую сосчитать количество дорог по заданной
матрице связности точек.
Входные данные
В первой строке входного файла [Link] записано число N (0
≤ N ≤ 100). В следующих N строках записано по N чисел, каждое из
которых является единичкой или ноликом. Причем, если в позиции (i,
j) квадратной матрицы стоит единичка, то i-ый и j-ый точки охоты
соединены тропами, а если нолик, то не соединены.
Выходные данные
На экран необходимо вывести число, определяющее количество
троп.
Пример.
Если входной файл такой:
5
0 1 0 0 0
1 0 1 1 0
0 1 0 0 0
0 1 0 0 0
0 0 0 0 0

37
 то правильный ответ = 3.

3. Прямоугольники
Дети племени «Тумба-Юмба» любят играть в логические игры.
Однажды вождь племени придумал детям задачу на построение
прямоугольников одинаковой площади. Пусть дана площадь
прямоугольника, тогда нужно найти количество различных
прямоугольников с целочисленными длинами сторон заданной
площади. Например, для площади 20 можно построить три
различающихся прямоугольника с такой же площадью.
Итак, пользователь с клавиатуры вводит одно целое
положительное число, не превосходящее 109 – это заданная площадь
прямоугольника. А на экран нужно вывести искомое количество
прямоугольников.

4. Результаты охоты
Вождь племени «Тумба-Юмба» очень аккуратен в подсчёте
успехов на охоте, но он особенным образом записывает результаты. В
местных лесах водятся 9 разных видов животных – они обозначаются
цифрами от 1 до 9. После охоты вождь раскладывает трофеи по видам
животных подряд, например, так:
334555
то есть пойманы две «тройки», одна «четвёрка», три «пятёрки», и,
затем, так же как мы только что назвали результаты, так и записывает
их:
231435
Вождь таким образом шифрует результаты охоты. Помогите
вождю – напишите программу, которая из входной строки будет делать
зашифрованную. Длина входной строки не превышает 100 символов.

5. Ход конём

38
 Интеллектуалы племени «Тумба-Юмба»
после охоты учатся играть в шахматы. На
этой неделе они осваивают ход Конём.
Напишите программу, которая будет
проверять правильность хода.
На вход подаётся строка – это шахматная
запись начальной позиции фигуры и
конечной позиции, например, так:
D5-C7
На выход нужно вывести результат анализа записи хода.
YES
- если указанный ход верный,
NO
- если такой ход не по правилам, указанным для Коня.
Гарантируется, что запись хода будет указана корректно, то есть
будет состоять из 5-ти символов, в середине «дефис», буквы и цифры
на правильных местах и в разрешённом диапазоне для шахматной
доски.

6. Шамбала
Шаман племени «Тумба-Юмба» особым даром – он умеет отгонять
беду от посевов племени. Но для успешного камлания он должен в
день начала посевов правильно сложить особенную фигуру,
называемую Шамбалой, чтобы боги погоды были благосклонны к
жителям племени. Как строится Шамбала посмотрите из примеров:
1-й 2-й день 3-й день 4-й день 5-й день
день

В данной задаче нужно вывести на экран в символическом виде

концентрические круги символами ‘X’ и пробелами, количество
которых зависят от номера N текущего дня. N вводит пользователь.
Ограничим N диапазоном от 1 до 30.

39
 Попробуйте реализовать рекурсивную функцию заполнения таблицы
«концентрическими кругами».

40
 2. Байки Солнечного города.
Задания для самостоятельного исполнения.

1. Тот-кого-нельзя-называть
Чтобы настроение жителей Солнечного города находилось по
«Шкале Счастья» в рамках от Хорошего до Прекрасного достаточно
обеспечить такое распределение зарплат, чтобы коротышка с самой
низкой зарплатой получал не менее 10% от самой большой зарплаты
в городе. Самый активный житель города – Тот-кого-нельзя-называть,
его все так называли, даже мэр города - Тот-кого-нельзя-оскорблять,
решил отслеживать настроение жителей. Помогите ему и напишите
программу.
На вход подаётся последовательность целых чисел (это зарплаты
горожан), например, такая:
600 100 500 1000
на экран нужно вывести отношение самой низкой зарплаты к самой
высокой, выраженное в процентах с округлением до целого.

2. Уравнение Незнайки
Уравнение для Незнайки представляет собой строку длиной 5
символов, например, такую: x+5=7.
Второй символ строки является либо знаком '+' (плюс) либо '-'
(минус), четвёртый символ — знак '=' (равно). Из первого, третьего и
пятого символов ровно два являются цифрами из диапазона от 0 до 9,
и один — буквой x, обозначающей неизвестное.
Требуется написать программу, которая позволит решить данное
уравнение, то есть найти величину x.
На вход подаётся одна строка, например:
3-x=9.
На выход значение x:
-6

3. Нумерология Кнопочки
Как и многие другие коротышки, малышка Кнопочка верит во
всякие чудеса, обожает разные гадания и нумерологию. Кнопочка
руководит солнечногорской гостиницей и считает, что некоторым
особенным клиентам нужно делать значительную скидку, чтобы
коротышечьи боги были благосклонны к её бизнесу. Особенность
41
клиентов определяется по их порядковому номеру заселения
следующим образом: пусть n – номер заселения, нужно подсчитать
сумму всех целых чисел (от 1 до n), на которые n делится без остатка
и, если эта сумма окажется нечётной, то данный гость получает скидку
(если n=3, то 1+3=4 – не особенный гость; если n=4, то 1+2+4=7 -
особенный). Кнопочка не успевает выполнять все обязанности по
гостинице и ей очень нужна программа, которая автоматизирует
процесс вычисления особенных клиентов.
На вход подаётся текстовый файл формата – порядковый номер
клиента, символ табуляции, имя клиента, например:
1 Стекляшкин
2 Пилюлькин
3 Смекайло
4 Растеряйка
5 Молчун
6 Сахариныч
7 Винтик
8 Шпунтик
9 Пачкуля Пёстренький
10 Гусля
11 Винтик
12 Шпунтик
Нужно вывести на экран список Фамилий особенных клиентов.

4. Шифрование Пилюлькина
Пилюлькин решил производить сладкую газировку в
промышленных масштабах, но монополии запрещены в Солнечном
городе. Однако он решил работать через подставные компании, а
рецепт и ингредиенты каждый раз оставлял в одном из номеров
солнечногорской гостиницы. Своим подельникам, Жулио и Нига, из
Лос-Поганоса он передавал лишь шифрованную запись, публикуя её в
«Газете дураков». Запись состоит из последовательности нулей и
единиц без пробелов общей длиной не более 255 символов. Самая
длинная непрерывная цепочка нулей в шифровке Пилюлькина и
обозначала номер, которые должны были снять подельники в
гостинице и там забрать искомые компоненты.
Например, если дана такая последовательность - 00101110000110,
то зашифрован номер 4.
Продажные полицейские солнечногорска не в состоянии
разгадать такой шифр, а, возможно и не хотят, так как они продажные.
Помогите детективу Биглю, не являющемуся полицейским, –
напишите программу, которая по шифру Пилюлькина будет
восстанавливать зашифрованный гостиничный номер.
42
 5. Лекции Незнайки
Незнайка регулярно посещает лекции Знайки по истории, но он так
неаккуратно ведёт записи, что это каждый раз становится проблемой
при подготовке к экзаменам. Незнайка решил исправляться - ему нужно
вести статистику своих ошибок, чтобы отслеживать улучшения.
Ошибки Незнайки состоят в том, что он в каждом записываемом
имени допускает ровно одну орфографическую ошибку, то есть
заменяет ровно одну из букв имени какой-то другой буквой.
Пусть дан список правильных написаний имён, и список имён или
других слов из записей Незнайки. Сопоставлять два списка сам
Незнайка не в состоянии. Напишите программу, которая поможет вести
статистику ошибок Незнайки.
Входные данные – это текстовый файл «[Link]».
В первой строке файла находится целое число N – это количество
правильных имён из лекций Знайки. Следующие N строк содержат
правильные имена. Далее идет строка, содержащая целое число M –
количество «подозрительных» имен и слов из записей Незнайки.
Следующие M строк – это те самые имена с ошибкой и слова. Каждое
из имен – последовательность из K заглавных букв английского
алфавита (1 ≤ N, M, K ≤ 30).
По результатам работы программы на экран нужно вывести одну
строку, состоящую из N чисел – для каждого правильного имени
выводится количество «подозрительных слов» из записей Незнайки,
то есть тех, которые отличаются строго на одну букву.
Пример входного файла:
3
ZEUS
POSEIDON
AFINA
4
ZEVS
POSEYDON
AVYNA
ZERS
Вывод на экран:
2 1 0

6. Равнобедренные треугольники

43
 Знайка иногда ведёт частные уроки по геометрии и ему нужно
рисовать равнобедренные треугольники. Но это рутинная операция и
Знайке совсем не хочется тратить на это своё время. Помогите ему и
напишите соответствующую программу.
На вход подаётся целое число N в диапазоне от 1 до 30.
По результатам работы программы на экран выводится
равнобедренный треугольник по такому формату: N – это высота
треугольника, основание треугольника параллельно вертикальной
стороне экрана, остальные параметры смотрите по примерам:
Ввод N: 1 2 3 4 5
Вывод: * * * * *
** ** ** **
* * * * * * *
** * * * *
* * * * *
** * *
* * *
**
*

44
 3. Безумное чаепитие.
Задания для самостоятельного исполнения.
В этой работе нужно написать функции и разместить их в модуле [Link].
Основная программа должна обращаться к функциям из модуля [Link].

1. Точное время.
Около дома под
деревом стоял накрытый
стол, а за столом пили чай
Мартовский Заяц и
Безумный Шляпник.
Стол был большой,
хорошо сервированный,
готовый к чаепитию.
Однако чаёвники сидели с
пустыми чашками.
Это ничуть не смутило
Алису - она выбрала место сама и, не спрашивая, уселась в удобное
большое кресло.
- Приступим, - дерзко сказала Алиса.
- Мы не можем, - нервно выкрикнул Мартовский Заяц.
- Отчего же? - не унималась Алиса.
- От того, что мы не знаем, когда заварится чай... - с горечью
вымолвил Безумный Шляпник.
Тягостная пауза. Алиса с недоумением смотрит на
присутствующих.
- Ну, вот смотри, - нехотя продолжил Шляпник, вынимая из
кармана часы. - Сколько сейчас времени?
- Полпервого, - уверенно заявила Алиса.
- Что ты, что ты, - засуетился Мартовский Заяц, - твоя
самоуверенность тебя погубит, подытожил он.
Шляпник решил прояснить ситуацию:
- У нас принято всё делать точно. "Сейчас не полпервого"...
Мартовский кот пренебрежительно хмыкнул.
- Сейчас 12.28.05, - уточнил Шляпник.
- А зачем говорить секунды? - продолжала вредничать Алиса.

45
 - А затем, глупое создание, что наш чай нужно
заваривать ровно 333 секунды и не секундой
дольше.

Помогите Алисе, напишите функцию, в которую в

качестве аргументов подаются начальное время и
количество секунд, а функция возвращает конечное
время.
Начальное время всегда задаётся в формате: ХХ:ХХ:ХХ, то есть,
например: 00:01:02 или 14:14:14 - всегда по два разряда на часы,
минуты и секунды.
Нужно найти сколько будет времени, если прибавить Y секунд.
Примеры. В первой строчке подаётся начальное время, во второй
количество секунд для заваривания чая.
Вход: Вход: Вход:
00:00:00 00:00:58 09:54:28
1 3 333
Выход: Выход: Выход:
00:00:01 00:01:01 10:00:01
Гарантируется, что итоговое время не превысит 23:59:59

2. Палиндромы.
- А что будет, если мы
не уложимся в точное
время заваривания чая? -
никак не унималась
Алиса.
- Ничего хорошего не
будет, - буркнул в ответ
Заяц.
- Он не далёк от
истины, последствия
непредсказуемы, - пояснил Шляпник.
- В прошлый раз время пошло вспять, - продолжил он после паузы,
занятой отхлёбыванием свежеТочноЗаваренного ароматного чая.
- Как же вы выкрутились? - удивилась Алиса.
- А также, ответил Шляпник, - мы знали заранее и подготовились,
мы пользовались только числами, словами и фразами, которые и в
прямом и в обратном направлении читаются одинаково -

46
палиндромами (данный термин имеет греческое происхождение и
обозначает "движущийся обратно").
Например, число «1231» и слово «рокот» - не палиндромы, они
нам не нужны. А вот, число "12321" – палиндром, слово "топот" и фраза
"Аргентина манит негра!" – палиндромы. Их можно использовать при
любом течении времени...

Помогите Алисе и напишите функцию, которая будет проверять

вводимую строку на палиндромность.
При проверке на палиндромность регистр буквы не имеет значение,
знаки препинания и знаки пунктуации не учитываются.
Примеры палиндромов:
На в лоб, болван.
Я иду с мечем судия. Автор Гавриил Державин.
А роза упала на лапу Азора. Автор Афанасий Афанасьевич Фет.
Есть даже стихи:
Перевертень. Автор Велимир Хлебников
Кони, топот, инок,
Но не речь, а черен он.
Идем, молод, долом меди.
Чин зван мечем навзничь.
Голод, чем меч долог?
Пал, а норов худ и дух ворона лап.
А что? Я лав? Воля отча!

3. Игра.
- О чём вы общаетесь во время чаепития? - спросила Алиса всех
присутствующих.
- Ни о чём! - фыркнул Мартовский Заяц.
- Как так? - озадачилась Алиса.
- Мы не занимаемся пустой болтовнёй, мы думаем... -
многозначительно добавил Шляпник.
- О чём же вы думаете? - с ехидством поинтересовалась Алиса.
- О том, как не проиграть, конечно же! - сорвался Заяц.

47
 - Или о том, как победить, - уточнил Шляпник, ну, вот смотри:
загадаю я, предположим, целое число, а ты должна угадать его за
минимальное количество попыток. В попытке ты говоришь мне
предполагаемое число. После каждой твоей попытки я тебе отвечаю
либо "угадала", либо "больше", либо "меньше". В начале игры я выдаю
тебе 10 печенюшек к чаю, за каждую ошибочную попытку ты мне
возвращаешь одну печенюшку. Все печенюшки, которые останутся
после угадывания моего числа, ты можешь использовать при
чаепитии - понятно?
- А если с первой угадаю? - пыталась съязвить Алиса.
- Угадала бы, если бы я загадывал число от 0 до 1, - ухмыльнулся
Шляпник, - я же загадываю трёхзначное число.

Напишите программу для игры в угадывание трёхзначного числа.

Программа сначала сама загадывает трёхзначное число. Далее
пользователь пытается его угадать. Сначала у пользователя 10
печенюшек. С каждой неудачной попыткой у него изымается 1 печенюшка.
Попытка - это ход числом. Например, загадано x=666. Пользователь
ходит 400, программа должна ответить из списка вариантов (ровно,
больше, меньше). Таким образом, пользователь, делая ходы,
последовательно приближается к загаданному числу. Игра
заканчивается, когда программа ответит на ход "ровно" или печенюшки
закончатся. Нужно вывести на экран число оставшихся печенюшек.

4. Шаги.
- Ну, ладно, засиделась я с вами тут, - вздохнула Алиса, - пойду я.
- Не спеши, - резко выпалил Мартовский Заяц.
- А то что? - с угрозой парировала Алиса.
- А то никогда не вернёшься домой, - обречённо ответил Шляпник.
На Алису от неожиданности накатилась волна страха, но она и виду
не подала. Она уже поняла, что с чаёвниками можно обсудить любую
тему, главное не молчать и соображать.
48
 - Но я же знаю обратную дорогу, - с осторожностью произнесла
Алиса.
- В том то и дело, что чай наш заваривался на грибах и на обратном
пути твой левый шаг не будет равен правому, будет меняться.
Твой путь можно будет разбить на отдельные отрезки по Х шагов.
Участков будет несколько - болото, тропа, пустырь, лес и т.д., а
последний участок поляна со входом в кроличью нору всегда
находится в тумане, поэтому нужно будет вслепую подходить ко входу
в нору.
Так вот, на каждом из участков мы определим длину шага левой
ногой и правой ногой в сантиметрах, а также количество шагов на
участке, получится примерно вот такая таблица:
55 45 1000
60 62 800
58 47 1100
52 59 500
Если в конце пути знать
насколько больше ты прошагала
одной ногой по сравнению к другой, то
можно будет гарантированно вернутся ко входу в
нору, и ты успешно вернёшься домой!

Помогите Алисе и напишите программу для вычисления разницы,

полученной в конце пути. Входные данные брать из текстового файла
"[Link]". Например, для случая, указанного выше можно получить
такой результат:
Левой ногой =>55*1000 + 60*800 + 58*1100 + 52*500 = 192800
сантиметров или 1928 метров.
Правой ногой => 45*1000 + 62*800 + 47*1100 + 59*500 = 175800
сантиметров или 1758 метров.
Таким образом, мы получаем разницу равную 170 метров.
Ответ давать в метрах без знака, то есть по абсолютной величине.

49
 4. Матрица.

Задания для самостоятельного исполнения.

В этой работе нужно написать функции и разместить их в модуле [Link].
Основная программа должна обращаться к функциям из модуля [Link].

1. Код Пифии.
Хакер Нео, не понимая своей миссии в Матрице,
ищет встречи с Пифией. Личная встреча опасна, как и
любое электронное сообщение, так как Нео уже давно
попал под наблюдение Матрицы, и за ним охотится
Агент Смит. Чтобы передавать сообщения, Пифия
размещает их в сети, но адреса документов шифрует.
Описание кода Пифии. Вы знаете, что каждый
символ имеет свой порядковый номер в таблице
символов, таким образом буквы можно заменить на их
номера, а слова на последовательности целых чисел. Например,
рассмотрим кодировку для имени Neo. Первая буква - N в таблице
символов стоит на 78-ой позиции – это и есть её номер. Но Пифия пошла
дальше и стала кодировать эти номера в шестнадцатеричной системе
счисления, то есть нужно заменить 7810 на 4E16, так как
4E16 => 4*161 + 14*160 = 64 + 14 = 7810
Итак, если зашифровать имя Neo кодом Пифии, то
получится такая последовательность: 4E656F, где
каждые два последовательно записанных символа
кодируют одну букву.
Нео проводит дни в ожидании послания от Пифии
– это будет адрес некоторого файла в сети. Однажды
сообщение придёт и нужно будет оперативно его
декодировать.

Помогите Избранному - напишите программу для декодирования послания

от Пифии и попробуйте декодировать это сообщение:

68747470733A2F2F70636F64696E672E72752F7478742F776F7264732E747874

Послание содержит адрес необходимого файла в сети. После

декодирования адреса скачайте файл, он понадобится в следующем задании.

2. Бинарный поиск.

50
 Скачанный на предыдущем этапе файл,
содержит важную информацию – 100, а может
даже 200 тысяч ключевых слов, расположенных
в алфавитном порядке. Нео должен хранить этот
файл и, при получении ключевого слова от
Тринити, найти его позицию в списке слов.

Помогите Избранному и напишите программу для бинарного поиска

позиции искомого слова в файле. В файле в каждой новой строчке находится
новое слово. Программа должна гарантировать, что слово найдётся не
более, чем за 20 итераций цикла. Линейный поиск недопустим из-за его
продолжительности, что в условиях постоянной слежки недопустимая
роскошь.
Проведите испытание своей программы со словами ‘ячейка’, ‘матрица’,
‘избранный’.

3. Звонок Морфеусу.
После того, как позиция слова ‘матрица’ будет
найдена, её нужно будет передать Морфеусу.
Чтобы Агент Смит не догадался по какому номеру
отслеживать звонок - Морфеус кодирует свой номер с
помощью графических матриц, где для каждой цифры
выделяется прямоугольное поле размером 2 по
горизонтали и 4 по вертикали:

0 1 2 3 4 5 6 7 8 9
** * ** ** ** ** * ** ** **
** ** * * ** * * * **
** * * * * * ** * ** *
** * ** ** * ** ** * ** *
Закодированный таким образом номер телефона может выглядеть как
некий узор:
********** ********* *
******* * * ** * ***
* *** ***** * * ** *
* * *** ****** ***** *
В этом узоре матрицы отдельных цифр размещены подряд без
дополнительных пробелов. Возьмите этот узор, скопируйте и поместите в
текстовом файле [Link]. Напишите программу, которая читает
текстовый файл с узором, распознаёт там образы цифр и выводит на экран
зашифрованный номер телефона.

51
 ПРИМЕРЫ ТЕСТОВЫХ ЗАДАНИЙ

ТЕСТ_1 Python Структурные операторы

Какое значение будет в переменной x после выполнения кода:

x = 0
for i in range(1,5):
x = x + i
print(x)

Какое значение будет в переменной x после выполнения кода:

x = 0
for i in range(9):
x += i % 3
print(x)

Какое значение будет в переменной x после выполнения кода:

x = 0
for i in range(9,0,-1):
if i % 2 == 0:
x = x + 1
print(x)

ТЕСТ_2 Python Списки, строки, функции, классы

Что будет выведено на экран после выполнения кода:

nums = [1,2,3,4,5]
print(3 in nums)

Что будет выведено на экран после выполнения кода:

def func(x,y):
return x if y%x==0 else y)
print(func(5,6))

Сколько строчек будет выведено на экран в результате выполнения этого кода:

for i in range(1,6):
if i<3 == 0:
continue
print(i)

Что будет выведено на экран в результате выполнения этого кода:

a = '22222'
print(a[2:])

52