Некоторые алгоритмы
Для разогрева (повтор):
Вложенные циклы на примере TODO
- Вызов функций
- В т. ч. друг из друга
- Работа с индексами в списках и строках
Как идею алгоритма превратить в программу?
Записать действия на наиболее знакомом вам языке
- можно по-русски!
можно не записывать только при условии, что вы способны повторить слово-в-слово
Подумать над моделированием данных реального мира с помощью типов данных Python
- Например, как из того, что вам предлагается вводить, сделать эти данные
Превратить придуманные вами действия в последовательность порождения и преобразования данных
- Какую дополнительную информацию вы используете
- Какое действие за каким следует
- При каких условиях вы делаете одно, а при каких — другое
- При каких условиях действия повторяются
- Есть ли чётко формулируемые подзадачи
Попытаться однозначно перевести каждое действие на Python
Обратите внимание на то, что лишних слов в формулировке не бывает!
- Например, если вы используете слово «каждый», это с точки зрения последовательности действий почти наверняка означает цикл
- И вообще про каждое слово в вашей формулировке задайте себе вопрос «а что оно значит» — наверняка вам придётся отражать это в программе
- Представить подзадачи в виде функций — тогда все действия, выполняемые одной функцией, будут выглядеть как как один шаг алгоритма
Разбор простого алгоритма
Поиск номера наименьшего элемента в списке
- Оформим это в виде функции
- Модифицируем функцию: поиск наименьшего элемента в списке, начиная с позиции N
Алгоритм сортировки обменом
- Формулировка на русском
- Перевод на Python
- Предыдущая функция как подзадача
- Запись в виде без функции
Понятие рекурсии
- Вызов функции и локальное пространство имён
Вызов функции из функции и стопка таких пространств
Вызов функции из самой себя (прямо или опосредованно)
- Проблема останова
- Проблема перерасхода пространств имён и памяти для объектов
- Проблема ориентации при разборе программы (о каком пространстве из стопки я сейчас думаю?)
Решение этой проблемы: о любом!
Рекурсивная реализация двоичного поиска
- Алгоритм
- Перевод на Python
Результат практического показа на лекции
1 def imin(L, k):
2 '''Номер наименьшего элемента в списке L, начиная с k-го'''
3 # Начнём с k элемента
4 m = k
5 # Для всех остальных позиций в L
6 for i in range(k + 1, len(L)):
7 # Проверим, не меньше него ли элемент в этой позиции
8 if L[i] < L[m]:
9 # И если да, запомним эту позицию
10 m = i
11 # Её и вернём
12 return m
13
14 def isort(L):
15 '''Обменная сортировка списка L по возрастанию'''
16 # Для всех позиций, кроме последней
17 for i in range(len(L) - 1):
18 # Найти позицию минимума среди элементов, начиная с этой позиции
19 m = imin(L, i)
20 # Поменять местами минимальный элемент и элемент в текущей позиции
21 L[i], L[m] = L[m], L[i]
22
23 def iisort(L):
24 '''Обменная сортировка списка L по возрастанию, полная версия'''
25 for k in range(len(L) - 1):
26 m = k
27 for i in range(k + 1, len(L)):
28 if L[i] < L[m]:
29 m = i
30 L[k], L[m] = L[m], L[k]
31
32 def binsearch(L, k):
33 '''Двоичный поиск k в упорядоченном списке L'''
34 # Если длина L — 1
35 if len(L) == 1:
36 # Проверяем, что k принадлежит L непосредствекнно
37 # и возвращаем ответ
38 return k == L[0]
39 # Берём середину списка
40 m = len(L) // 2
41 # Если эелмент посредине больше k,
42 if L[m] > k:
43 # ищем в левой
44 # и возвращаем резульата
45 return binsearch(L[:m], k)
46 # Иначе
47 else:
48 # ищем в правой половине L
49 # и возвращаем резульата
50 return binsearch(L[m:], k)
51
Создание дубликатов левой и правой части списка в двоичном поиске требует дополнительного времени на копирование и дополнительной памяти (примерно столько же, сколько исходных данных). Это сводит на нет эффект от низкого количества сравнений и делает сложность всё такой же линейной, как и алгоритма простого поиска. Однако небольшим усложнением реализации алгоритма (передача в качестве параметра левой и правой границ вместо дублирования всего списка) эта проблема решается. Попробуйте!
Сортировкa слиянием
В алгоритме обменной сортировки мы слишком часто сравниваем одни и те же элементы (особенно после того, как переставляем их местами). Этих сравнений настолько много, что сложность алгоритма получается квадратичной — примерно $$ ((N-1)(N-2))/2 $$ действий.
В идеале, поскольку сравниваются всегда два значения, можно достичь сложности в $$ N * log_2 N $$ действий.
Алгоритм слияния двух заранее упорядоченных последовательностей
Идея: в начале каждой упорядоченной последовательности стоит её наименьший элемент. Значит, наименьший элемент объединения обеих последовательностей — один из этих двух. Заберём его, и снова окажется, что один из двух — наименьший среди оставшихся.
- Проблема: одна последовательность кончится раньше другой
Решение: в этой другой лежит упорядоченный кусок, элементы которого не меньше всего остального, так что его можно просто приписать в конец результата
- Формализация на русском:
- Первоначальный вариант
# До тех пор, пока обе последовательности непусты # Сравним их начальные элементы # Минимальный заберём и добавим в ответ # По окончании припишем к ответу оставшуюся непустую последовательность
Выберем тип данных для моделирования последовательности. Нам понадобится определять, что последовательность пуста. Список подходит.
- Уточнение формализации
- Выделим цикл и условный оператор
- Фраза «минимальный заберём» явно недостаточно детализирована, распишем её
Адаптируем алгоритм к спискам: зная, что операция удаления из начала списка не рекомендуется (слишком долгая), заменим удаление на перемещение счётчика, а оба списка оставим нетронутыми
- По этой же причине придётся заменить проверку на пустоту проверкой на то, что счётчик достиг конца списка
# Установим оба счётчика в 0 # До тех пор, пока ни один счётчик не вышел за пределы своего списка # Если соответствующий элемент первого списка меньше соответствующего элемента второго # Добавим в ответ элемент первого списка # Увеличим первый счётчик # Иначе # Добавим в ответ элемент второго списка # Увеличим второй счётчик # По окончании припишем к ответу оба окончания списков
Обратите внимание на последнюю строку, там небольшая хитрость: вместо того, чтобы проверять, какой из списков исчерпан, просто добавим к ответу оба их окончания, зная, что одно из них заведомо пусто и на ответ не повлияет
- Первоначальный вариант
- Перевод на python в виде функции
1 def joinseq(A, B): 2 # Установим оба счётчика в 0, заведём пустой ответ 3 res, i, j = [], 0, 0 4 # До тех пор, пока ни один счётчик не вышел за пределы своего списка 5 while i < len(A) and j < len(B): 6 # Если соответствующий элемент первого списка меньше соответствующего элемента второго 7 if A[i] < B[j]: 8 # Добавим в ответ элемент первого списка 9 res.append(A[i]) 10 # Увеличим первый счётчик 11 i += 1 12 # Иначе 13 else: 14 # Добавим в ответ элемент второго списка 15 res.append(B[j]) 16 # Увеличим второй счётчик 17 j += 1 18 # По окончании припишем к ответу оба окончания списков 19 return res + A[i:] + B[j:]
Рекурсивный алгоритм сортировки слиянием
Идея: если обе половины списка отсортированы, их достаточно слить с помощью joinseq() для получения результата. Значит, достаточно отсортировать обе половины списка, а затем их слить. Если длина списка меньше 2, сортировать его не надо.
- Проблема: куда слить?
- Решение: в новый список
- Формализация на русском
- Первоначальный вариант
# Если длина списка больше 1 # Вернуть результат слияния отсортированных половин # В противном случае вернуть сам список
- Первоначальный вариант
- Перевод на Python
1 def joinsort(seq): 2 # Если длина списка больше 1 3 if len(seq) > 1: 4 # Сгенерировать половины списка 5 A, B = seq[:len(seq)//2], seq[len(seq)//2:] 6 # Вернуть результат слияния отсортированных половин 7 return joinseq(joinsort(A), joinsort(B)) 8 # В противном случае 9 else: 10 # вернуть сам список 11 return seq
Как и в случае двоичного поиска, многочисленное копирование секций списков сильно снижает выигрыш в количестве сравнений и может быть преодолено работой с парами индексов вместо самих дубликатов списков. Однако даже в таком виде сложность алгоритма не является квадратичной.
Сводный текст (не факт, что функцию joinseq() стоило удалять)
1 def joinsort(seq):
2 if len(seq) > 1:
3 A, B = joinsort(seq[:len(seq)//2]), joinsort(seq[len(seq)//2:])
4 res, i, j = [], 0, 0
5 while i < len(A) and j < len(B):
6 if A[i] < B[j]:
7 res.append(A[i])
8 i += 1
9 else:
10 res.append(B[j])
11 j += 1
12 return res + A[i:] + B[j:]
13 else:
14 return seq
Д/З
TODO
EJudge: PaidStairs 'Платная лестница'
Input:(MCCME) Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму (положительное целое число). Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки. На последнюю ступеньку наступать обязательно. Ввести стоимость ступенек через запятую, вывести минимальную сумму прохода.
- Пояснения и алгоритм — в полном тексте задачи
Output:1,3,1,1,2,2
5
- Input:
Написать функцию cross(width, paper, ink), которая на вход принимает три параметра — натуральное число width⩾2 и две строки единичной длины, paper, и ink. Возвращать эта функция должна строковый объект, при выводе на экран которого получается приведенная ниже фигура. Это квадрат шириной width, стороны и диагонали которого состоят из строки ink, а остальное пространство заполнено строкой paper.
- Пояснения и алгоритм — в полном тексте задачи
Output:1 print(cross(11, ".", "*"))*********** **.......** *.*.....*.* *..*...*..* *...*.*...* *....*....* *...*.*...* *..*...*..* *.*.....*.* **.......** ***********