Challenging Programming
in Python: A Problem
Solving Perspective
Habib Izadkhah · Rashid Behzadidoost
Решение трудных
и увлекательных задач
на Python
Хабиб Изадха, Рашид Бехзадидуст
Москва, 2024
УДК 004.438Python
ББК 32.973.22
И32
И32 Изадха Х., Бехзадидуст Р.
Решение трудных и увлекательных задач на Python / пер. с англ.
А. Н. Киселева. – М.: ДМК Пресс, 2024. – 240 с.: ил.
ISBN 978-5-93700-280-8
Цель данной книги – укрепить навыки логического рассуждения и развить творческое мышление, представив и решив 90 не самых простых задач
на Python. Задачи изложены доходчиво и сжато, снабжены алгоритмами и
комментариями, что помогает читателям следить за процессом их решения
и понимать его суть.
Издание предназначено читателям с базовыми знаниями языка Python,
которые стремятся вывести свои способности на новый уровень. Книга будет
полезна студентам, преподавателям, разработчикам, а также участникам
соревнований по программированию.
ISBN 978-3-03139-998-5 (англ.)
ISBN 978-5-93700-280-8 (рус.)
Оглавление
Предисловие.................................................................................................................... 9
Об авторах..................................................................................................................... 11
Глава 1. Введение.......................................................................................................... 12
1.1. Почему Python?................................................................................................................ 12
1.2. Без использования библиотек................................................................................... 13
1.3. Развитие навыков программирования и творческого мышления
при решении сложных задач...................................................................................... 13
1.4. Предварительные условия........................................................................................... 14
1.5. Целевая аудитория......................................................................................................... 14
Глава 2. Математика..................................................................................................... 15
2.1. Задача Иосифа Флавия................................................................................................. 16
Алгоритм............................................................................................................................................ 17
2.2. Подсчет количества путей к точке (0,0) на координатной сетке................. 19
2.3. Создание отсортированного списка целых чисел для задачи
выбора Брюсселя.............................................................................................................. 21
2.4. Поиск решения обратной гипотезы Коллатца..................................................... 23
2.5. Подсчет правильных прямых углов......................................................................... 27
2.6. Ближайшее s‑угольное число..................................................................................... 28
2.7. Поиск точки опоры физических весов.................................................................... 30
2.8. Вычисление общего количества блоков, необходимых
для построения пирамиды из сфер.....................................................................................32
2.9. Группировка монет.......................................................................................................... 33
2.10. Поиск медианы по тройкам чисел......................................................................... 35
2.11. Наименьшее число из семерок и нулей.............................................................. 38
2.12. Оценка математических выражений в постфиксной нотации................... 40
2.13. Достижение стабильного состояния в болгарском пасьянсе...................... 43
2.14. Вычисление площади прямоугольных башен Манхэттена
на линии горизонта......................................................................................................... 46
2.15. Разрезание прямоугольника на квадраты.......................................................... 50
2.16. Удаление правильных прямых углов в двумерной сетке............................. 53
2.17. Треугольник Лейбница................................................................................................ 56
2.18. Расстояние Коллатца................................................................................................... 60
2.19. Сумма двух квадратов................................................................................................ 62
2.20. Поиск трех чисел........................................................................................................... 64
6
Оглавление
2.21. Определение совершенной степени.................................................................... 68
2.22. Лунное умножение целых чисел............................................................................ 70
2.23. n‑й член последовательности Рекамана............................................................. 73
2.24. n‑й член последовательности Ван Эка................................................................. 74
2.25. Поиск суммы чисел Фибоначчи на основе теоремы
Цекендорфа........................................................................................................................ 77
2.26. Поиск k‑го слова Фибоначчи................................................................................... 79
2.27. Поиск прямой в двумерной сетке, пересекающей наибольшее
количество точек.............................................................................................................. 80
2.28. Проверка сбалансированности центрифуги..................................................... 83
Глава 3. Числа................................................................................................................ 88
3.1. Число Циклопа................................................................................................................. 89
3.2. Цикл домино..................................................................................................................... 90
3.3. Извлечение возрастающих чисел............................................................................. 91
3.4. Развертывание целочисленных интервалов........................................................ 93
3.5. Свертывание целочисленных интервалов............................................................ 96
3.6. Левосторонний игральный кубик............................................................................. 97
3.7. Очки за повторяющиеся числа................................................................................... 99
3.8. Первое меньшее число............................................................................................... 102
3.9. Первый объект, предшествующий k меньшим объектам.............................. 105
3.10. Поиск n‑го члена последовательности Калкина–Уилфа............................ 106
3.11. Поиск и обращение восходящих подмассивов.............................................. 109
3.12. Наименьшие целые степени.................................................................................. 111
3.13. Сортировка циклов в графе................................................................................... 112
3.14. Получение представления числа в сбалансированной
троичной системе........................................................................................................... 116
3.15. Строгое возрастание.................................................................................................. 118
3.16. Сортировка по приоритетам.................................................................................. 119
3.17. Сортировка положительных чисел с сохранением порядка
отрицательных чисел.................................................................................................... 122
3.18. Сортировка: сначала числа, потом символы.................................................... 124
3.19. Сортировка дат............................................................................................................. 125
3.20. Сортировка по алфавиту и длине........................................................................ 127
3.21. Сортировка чисел по количеству цифр.............................................................. 129
Глава 4. Строки............................................................................................................. 132
4.1. Шифрование текста блинчиком.............................................................................. 132
4.2. Перестановка гласных в обратном порядке...................................................... 134
4.3. Форма слова из текстового корпуса...................................................................... 135
Оглавление 7
4.4. Высота слова из текстового корпуса..................................................................... 137
4.5. Объединение соседних цветов по заданным правилам............................... 141
4.6. Вторая машина Маккаллоха..................................................................................... 144
4.7. Слово Чампернауна...................................................................................................... 146
4.8. Объединение строк....................................................................................................... 148
4.9. Расшифровка слов........................................................................................................ 151
4.10. Автокорректор слов................................................................................................... 153
4.11. Правильная форма глагола в испанском языке............................................. 155
4.12. Выбор слов с одним и тем же набором букв.................................................. 159
4.13. Выбор слов из текстового корпуса, соответствующих шаблону.............. 161
Глава 5. Игры................................................................................................................ 164
5.1. Определение выигрышной карты.......................................................................... 164
5.2. Подсчет карт каждой масти в игре бридж.......................................................... 170
5.3. Получение сокращенного представления карт в раздаче в игре
«Контрактный бридж».................................................................................................. 171
5.4. Наборы карт одинаковой формы в карточной игре....................................... 174
5.5. Подсчет количества раундов обработки чисел в порядке
возрастания...................................................................................................................... 176
5.6. Достижение стабильного состояния в распределении конфет.................. 177
5.7. Игра вари.......................................................................................................................... 180
5.8. Количество безопасных полей на шахматной доске с ладьями............... 183
5.9. Количество безопасных полей на шахматной доске со слонами............. 184
5.10. Достижимость поля для коня в многомерных шахматах........................... 186
5.11. Захват максимального количества шашек на шахматной доске............ 188
5.12. Количество безопасных полей для размещения дружественных
фигур на шахматной доске........................................................................................ 193
5.13. Количество очков в игре в кости «Скала»........................................................ 195
5.14. Наилучший результат из нескольких бросков в игре
в кости «Скала»............................................................................................................... 198
Глава 6. Счет................................................................................................................. 202
6.1. Подсчет количества переносов при сложении двух заданных чисел..... 202
6.2. Подсчет количества рычащих животных............................................................. 204
6.3. Подсчет количества способов выражения вежливого числа...................... 208
6.4. Подсчет вхождений каждой цифры...................................................................... 209
6.5. Подсчет количества максимальных слоев на двумерной плоскости...... 211
6.6. Подсчет количества доминирующих чисел........................................................ 213
6.7. Подсчет количества троек чисел............................................................................. 215
6.8. Подсчет пар пересекающихся кругов................................................................... 216
8
Оглавление
Глава 7. Разные задачи............................................................................................... 218
7.1. Идеальное перемешивание элементов списка................................................. 218
7.2. Точный размен монет с учетом имеющихся номиналов............................... 221
7.3. Удаление избыточных элементов из списка....................................................... 222
7.4. Когда две лягушки встретятся в одном квадрате............................................. 224
7.5. Определение позиции числа в массиве Витхофа............................................ 228
7.6. Интерпретация программы на Fractran................................................................ 232
Предметный указатель.............................................................................................. 236
Предисловие
Программирование – это увлекательнейшая область человеческой дея
тельности, требующая творческого подхода, навыков решения задач
и любознательности. Python – это популярный и универсальный язык
программирования, широко используемый в различных областях: от нау
ки о данных и машинного обучения до веб-разработки и научных вычислений. Простой синтаксис Python, обширная экосистема библиотек и динамичный характер делают его идеальным языком для решения сложных
задач. Программирование заставляет людей мыслить логично, потому что
процесс достижения результата должен быть точно сформулирован. По
этому всякому программисту очень важно иметь книги, описывающие
приемы решения сложных задач. С другой стороны, книги также необходимы для совершенствования навыков мышления и рассуждения в повседневной жизни и работе. Творческое мышление и логическое рассуждение
имеют решающее значение для решения задач, и эта книга направлена
на достижение двух общих целей:
1) совершенствование навыков мышления и рассуждения путем исследования и программирования сложных задач;
2) улучшение навыков программирования на Python путем постановки сложных задач и их последовательного решения.
Эта книга адресована всем желающим поднять на новый уровень свои
навыки владения языком Python и решения сложных задач. Она будет
полезна всем, кто владеет навыками программирования на Python независимо от их уровня, а также всем, кто желает освоить язык программирования достаточно хорошо, чтобы решать сложные задачи. В этой книге
вы найдете многочисленные примеры решения сложных задач на Python
с алгоритмами и примечаниями. Мы преследовали две основные цели,
представляя 90 задач из различных областей и их решения. Каждая глава посвящена конкретному типу задач, что, как нам кажется, должно способствовать росту интереса у читателя. Эта книга разделена на семь глав.
В первой главе даются самые основы программирования на Python, а в последующих главах рассматриваются конкретные типы задач. Например,
в главе 2 разбираются математические задачи, в главе 3 – сложные числовые задачи, в главе 4 – задачи, связанные с обработкой строк, в главе 5 –
игровые задачи, в главе 6 – счетные задачи и в главе 7 – разные задачи,
не попавшие в предыдущие главы.
10
Предисловие
Эта книга рекомендуется студентам всех специальностей независимо
от их уровня владения навыками программирования, а также преподавателям и вообще всем, желающим совершенствовать свои навыки программирования на Python. Также книга будет полезна студентам, готовящимся к участию в соревнованиях по программированию. Изучив темы,
представленные в нашей книге, учащийся сможет решать сложные задачи
на Python.
Тебриз, Иран
Хабиб Изадха, Рашид Бехзадидуст
Об авторах
Доктор Хабиб Изадха (Dr. Habib Izadkhah) – доцент кафедры информатики Тебризского университета, Иран. Прежде чем уйти в академическую науку, он десять лет проработал инженером-программистом. В круг
его исследовательских интересов входят: алгоритмы и графы, разработка
программного обеспечения и биоинформатика. Совсем недавно он занимался разработкой и применением глубокого обучения для решения различных задач, связанных с интерпретацией медицинских изображений,
распознаванием речи и текста и генеративными моделями. Участвовал
в различных исследовательских проектах, был автором ряда научных статей на международных конференциях, семинарах и в журналах, а также
написал пять книг, в том числе «Source Code Modularization: Theory and
Techniques» (Springer) и «Deep Learning in Bioinformatics» (Elsevier).
Рашид Бехзадидуст (Rashid Behzadidoost) – кандидат наук, работает
на кафедре информатики Тебризского университета, Иран. В настоящее
время пишет докторскую диссертацию, специализируясь на искусственном интеллекте и обработке естественного языка. Рашид страстно увлечен
программированием и любит решать сложные задачи. Он приобрел свои
навыки за годы учебы, практики и преподавания. Читал несколько курсов
по информатике, включая продвинутое программирование, микропроцессорную технику и структуры данных, в университете Тебриза.
Глава
1
Введение
В этой главе обсуждаются цели и применение данной книги.
1.1. Почему Python?
Python – это язык программирования высокого уровня, имеющий более
простой синтаксис, по сравнению со многими другими языками программирования. Кроме того, Python – это универсальный, кросс-платформенный, многопарадигмальный и объектно ориентированный язык,
поддерживающий динамические типы данных. Python – очень простой
язык, его быстро освоит любой, имеющий хоть какие-то знания в облас
ти программирования. Основная причина такой простоты заключается
в том, что инструкции языка Python подобны словам в английском языке, что значительно упрощает процесс обучения. Python имеет интерактивную оболочку, которая позволяет экспериментировать и тестировать
команды. Кросс-платформенность – важное преимущество, позволяющее
пользоваться языком в различных операционных системах, таких как Mac,
Windows, Linux и даже iOS и Android. Одно из наиболее значительных преимуществ Python – обширная экосистема библиотек, охватывающая самые
разные сферы практического применения. Фактически библиотека предо
ставляет множество готовых фрагментов кода, которые программисты
могут использовать в своей работе. Например, чтобы подключить Python
к базе данных, необязательно писать свой код, реализующий все тонкос
ти подключения. Вместо этого можно воспользоваться готовой библиотекой. Все перечисленные особенности делают Python отличным языком для
изучения. Кроме того, Python имеет множество практических применений, таких как веб-разработка, разработка игр, наука о данных и искусственный интеллект. Помимо простоты и универсальности, Python также
известен среди разработчиков своим активным и доброжелательным сообществом. Будучи языком с открытым исходным кодом, Python сплотил
вокруг себя огромное сообщество, способствующее его росту и развитию.
1.3. Развитие навыков программирования и творческого мышления при решении сложных задач 13
Это сообщество предоставляет множество ресурсов, включая документацию, форумы и учебные пособия, что упрощает обучение новичков и поиск решений опытным разработчикам. Кроме того, сообщество постоянно
совершенствует Python, разрабатывая новые пакеты, библиотеки и фреймворки, гарантируя актуальность и востребованность языка в постоянно
меняющемся технологическом ландшафте. Это доброжелательное и динамичное сообщество – еще одна причина, почему Python считается замечательным языком для изучения.
1.2. Без использования библиотек
Большинство книг по Python либо описывают синтаксис языка с базовыми
примерами, либо фокусируются на пакетах, предназначенных для решения конкретных задач. Описание библиотек и предоставление простых
упражнений часто весьма полезно для изучения Python и обретения навыков решения сложных задач.
Однако мы считаем, что такие подходы не годятся для профессиональных программистов, разрабатывающих сложные программы. Поэтому
в этой книге применяется другой подход: обсуждаются задачи, не связанные с библиотеками (хотя в некоторых программах мы действительно будем использовать стандартные библиотеки), и представлены подробные
пошаговые алгоритмы решения с подсказками и примерами кода с комментариями. Следуя этому подходу, мы надеемся привить программистам
навыки решения сложных задач и тем самым улучшить их способности
к программированию.
1.3. Развитие навыков программирования
и творческого мышления при решении
сложных задач
Решение сложных задач – эффективный способ улучшения навыков программирования и развития творческого мышления. Программисты должны сначала определить задачу, разработать решение, затем преобразовать
его в алгоритм и, наконец, реализовать его на конкретном языке программирования. Решая различные сложные задачи, программисты учатся использовать систематический подход и улучшают свои навыки программирования. Целью этой книги является повышение эффективности
мышления, развитие умения рассуждать, а также углубление понимания
языка Python на примере 90 задач, решение которых подробно рассматривается в главах. Задачи сгруппированы по таким темам, как математика,
числа, строки, игры, счет и др. Каждая глава содержит набор задач с примерами, подсказками и реализациями на Python. Задачи распределены
14
Глава 1. Введение
по темам следующим образом: математика – 28, числа – 21, строки – 13,
игры – 14, счет – 8 и прочие задачи – 6.
1.4. Предварительные условия
В книге присутствуют только главы, посвященные решению сложных задач. Мы решили не включать в нее главу, посвященную основам Python,
так как в интернете можно найти много хороших учебников, где эта тема
рассматривается очень подробно. Поэтому единственное предварительное условие, предполагаемое этой книгой, – знание Python на самом базовом уровне.
1.5. Целевая аудитория
В этой книге представлены решения 90 задач, которые могут быть интересны широкому кругу людей, включая студентов, изучающих информатику и инженерные специальности, а также всех, кто хочет улучшить свои
навыки владения языком Python. Представленные задачи охватывают
различные области, что делает их пригодными для широкого круга практических применений. Более того, эта книга расширяет навыки мышления
и рассуждения, независимо от используемого вами языка программирования. Она послужит ценным ресурсом для преподавателей Python в университетах или школах. Кроме того, разработчики программного обеспечения и участники соревнований могут воспользоваться этой книгой для
совершенствования своих навыков программирования.
Глава
2
Математика
В этой главе рассматриваются 28 математических задач, которые сопровождаются примерами решения на Python. Вот эти задачи:
1. Вычисление порядкового номера в задаче Иосифа Флавия.
2. Подсчет количества путей к точке (0,0) на координатной сетке.
3. Создание отсортированного списка целых чисел для задачи выбора
Брюсселя.
4. Поиск решения обратной гипотезы Коллатца.
5. Подсчет правильных прямых углов.
6. Ближайшее s‑угольное число.
7. Поиск точки опоры физических весов.
8. Вычисление общего количества блоков, необходимых для построения пирамиды сфер.
9. Группировка одинаковых монет по некоторым условиям.
10. Поиск медианы по тройкам чисел.
11. Наименьшее число из семерок и нулей.
12. Преобразование математических выражений из постфиксной нотации в инфиксную и их оценка.
13. Достижение стабильного состояния в болгарском пасьянсе.
14. Вычисление площади прямоугольных башен Манхэттена на линии
горизонта.
15. Разрезание прямоугольника на квадраты.
16. Удаление правильных прямых углов в двумерной сетке.
17. Вычисление значений в нижней грани гармонического треугольника Лейбница.
18. Достижение цели на основе расстояния Коллатца.
19. Поиск суммы двух квадратов для числа n.
20. Поиск трех чисел, сумма которых равна целевому числу n.
21. Определение совершенной степени.
22. Лунное умножение целых чисел.
23. n‑й член последовательности Рекамана.
16
Глава 2. Математика
24.
25.
26.
27.
n‑й член последовательности Ван Эка.
Поиск суммы чисел Фибоначчи на основе теоремы Цекендорфа.
Поиск k‑го слова Фибоначчи.
Поиск прямой в двумерной сетке, пересекающей наибольшее количество точек.
28. Проверка сбалансированности центрифуги.
2.1. Задача Иосифа Флавия
Задача Иосифа Флавия – широко известная в информатике теоретическая
задача. Суть ее заключается в следующем: в круг выстраивается n человек.
Из стоящих выбирается k‑й человек, который покидает круг. Далее покинувшие круг не участвуют в процессе подсчета, а последний оставшийся
считается победителем. Цель состоит в том, чтобы разработать функцию,
которая принимает заданные значения n и k и возвращает порядок, в котором игроки будут покидать круг. Здесь n представляет общее количест
во людей, а k – количество пропусков. Важно отметить, что k может быть
меньше, равно или даже больше n.
Например, рассмотрим рис. 2.1, где в круг встали пять человек. Для
k = 2 и n = 5 определите, в каком порядке они будут покидать круг. Пусть ex –
это массив людей, покинувших круг. Поскольку k = 2, то сразу после начала
игры выбирается x2 и исключается из круга; ex = [2]. Далее выполняется
k шагов по кругу и выбывает 2 + 2 = 4‑й участник, т. е. x4; ex = [2, 4]. И снова выполняется k шагов, в результате выбывает участник x1; ex = [2, 4, 1].
Обратите внимание, что при пересечении конца массива происходит переход в его начало (как по кругу), поэтому на предыдущем шаге выбор
пал на игрока x1. Теперь в круге остаются x3 и x5. После выполнения k шагов из круга выбывает x5, соответственно, ex = [2, 4, 1, 5]. Последний игрок,
оставшийся в круге, – x3, поэтому искомый порядок исключения из круга
ex = [2, 4, 1, 5, 3]. В табл. 2.1 показаны некоторые ожидаемые результаты
(содержимое массива ex) для разных значений k и n.
Таблица 2.1. Некоторые ожидаемые результаты
для разных значений k и n
n, k
Ожидаемый результат
6, 2
[2, 4, 6, 3, 1, 5]
5, 2
[2, 4, 1, 5, 3]
8, 8
[8, 1, 3, 6, 5, 2, 7, 4]
3, 9
[3, 1, 2]
4, 3
[3, 2, 4, 1]
2.1. Задача Иосифа Флавия 17
Рис. 2.1. Пример людей, вставших в круг
Алгоритм
Алгоритм принимает два аргумента: n – количество людей в круге и k –
сколько людей нужно отсчитать, чтобы выбрать следующего для исключения из круга. В результате получается список чисел от 1 до n, представляющих людей в круге. Затем алгоритм последовательно исключает из круга
каждого k‑го человека, пока не останется только один, и возвращает список в том порядке, в котором люди исключались из круга. Чтобы гарантировать переход через правую границу массива к его началу, используется
оператор деления по модулю. Вот подробное описание шагов алгоритма:
1.
2.
3.
4.
5.
Принимаются два значения, n и k.
Создается список с именем m, содержащий все числа от 1 до n.
Создается пустой список с именем ans для хранения результата.
Устанавливается переменная i = 0.
Создается цикл while, который будет продолжать выполняться, пока
список m не опустеет.
6. В цикле while обновляется индекс i по формуле 2.1: к значению i
прибавляется k и вычитается 1. Затем вычисляется остаток от деления индекса i на длину m, чтобы гарантировать, что i останется
в пределах списка.
7. Вызовом метода pop из списка m исключается элемент с индексом i
и добавляется в конец списка ans.
18
Глава 2. Математика
8. По завершении возвращается список ans.
9. В листинге 2.1 приводится код на Python, решающий задачу Иосифа
Флавия.
(i + k – 1) mod m.
(2.1)
Листинг 2.1. Решение задачи Иосифа Флавия на Python
1 def josephus (n , k ) :
2
'''
3
Создать список чисел от 1 до n,
4
представляющий людей в круге.
5
'''
6
m = l i s t ( range (1 , n + 1))
7
8
'''
9
Создать пустой список для хранения номеров людей
10
в порядке их исключения из круга.
11
'''
12
ans = [ ]
13
14
'''
15
Инициализировать переменную i, хранящую
16
текущую позицию в списке.
17
'''
18
i = 0
19
20
'''
21
Цикл, продолжающий исключать людей из круга,
22
пока в нем никого не останется.
23
'''
24
while m:
25
# Вычислить индекс следующего человека, исключаемого из круга.
26
i = ( i + k − 1) % len (m)
27
28
'''
29
Исключить человека из списка
30
и добавить его в список с результатами.
31
'''
32
ans.append(m.pop(i))
33
34
# Вернуть результат.
35
return ans
2.2. Подсчет количества путей к точке (0,0) на координатной сетке 19
Функция josephus действует, как описано ниже.
1. Генерирует список m, включающий все числа от 1 до n.
2. Для хранения результата – списка людей, исключаемых из круга, –
создает пустой список ans.
3. Создает переменную индекса i и присваивает ей начальное значение 0.
4. Входит в цикл while, который продолжается до тех пор, пока из круга
не будут исключены все игроки.
5. Внутри цикла функция вычисляет индекс следующего числа для исключения, прибавляя k – 1 к текущему индексу i и определяя остаток от деления на длину оставшегося списка m.
6. Затем число, находящееся в списке m по вычисленному индексу, добавляется в конец списка ans и исключается из списка m с вызовом
метода pop.
7. Наконец, функция возвращает список ans, с людьми, расположенными в порядке исключения из круга.
2.2. Подсчет количества путей к точке (0,0)
на координатной сетке
В координатной сетке дана точка (x, y), представленная парой натуральных чисел, и нужно из нее добраться до точки (0,0). Задача состоит в том,
чтобы подсчитать, сколькими возможными путями можно достичь начала координат (0,0), выполняя шаги влево или вниз. Напишите функцию,
подсчитывающую наибольшее количество таких путей, не пересекающих
точки с координатами в запретном списке. На входе даются x и y – координаты исходной точки, а tabu – список точек с запретными координатами.
В табл. 2.2 показаны ожидаемые результаты для некоторых входных данных.
Таблица 2.2. Некоторые ожидаемые результаты
для разных значений x, y и tabu
x, y, tabu
Ожидаемый результат
3, 2, []
10
1, 6, [(7, 1), (4, 4)]
7
8, 8, [(9, 10), (1, 4)]
11220
7, 5, [6,8]
792
20
Глава 2. Математика
Алгоритм
Для поиска решения используется следующий алгоритм.
1.
2.
3.
4.
Принимаются координаты (row, col) исходной точки и список tabu.
Создается двумерный массив paths с размером (row + 1) × (col + 1).
Элементу paths [0] [0] присваивается значение 1.
Для всех i от 1 до row, если точка (i,0) не включена в tabu, присвоить
элементу paths [i] [0] значение элемента paths [i – 1] [0].
5. Для всех j от 1 до col, если точка (0, j) не включена в tabu, присвоить
элементу paths [0] [j] значение paths [0] [j – 1].
6. Для всех i от 1 до row и для всех j от 1 до col, если точка (i, j) не включена в tabu, присвоить элементу paths [i] [j] значение выражения
paths [i – 1] [j] + paths [i] [j – 1].
7. Вернуть paths [row] [col].
В листинге 2.2 приводится код на Python, решающий задачу подсчета
наибольшего числа переходов в точку (0,0).
Листинг 2.2. Решение задачи подсчета наибольшего числа переходов в точку (0,0)
1 def lattice_paths (row, col , tabu ) :
2
'''Создать двумерный массив с размерами (row+1) x (col+1)
3
и инициализировать все его элементы нулями
4
'''
5
paths = [ [0] * ( col+1) for _ in range(row+1)]
6
7
'''Присвоить 1 элементу, соответствующему точке в левом нижнем
8
углу, поскольку есть только один путь, чтобы достичь ее
9
'''
10
paths [0] [0] = 1
11
12
'''Заполнить первый столбец в таблице,
13
пропуская точки, присутствующие в списке 'tabu' '''
14
for i in range(1 , row+1):
15
if (i, 0) not in tabu:
16
paths[i][0] = paths[i−1][0]
17
18
'''Заполнить первую строку в таблице,
19
пропуская точки, присутствующие в списке 'tabu'
20
'''
21
for j in range(1, col+1):
22
if (0, j) not in tabu:
23
paths[0][j] = paths[0][j−1]
2.3. Создание отсортированного списка целых чисел для задачи выбора Брюсселя 21
24
25
26
27
28
29
30
31
32
33
34
35
# Заполнить остальные ячйки таблицы
for i in range(1, row+1):
for j in range(1, col+1):
# Пропустить ячейки в списке 'tabu'
if (i, j) not in tabu:
'''Значение каждой незапрещенной ячейки
определяется как сумма значений ячеек
выше левее.'''
paths[i][j] = paths[i−1][j] + paths[i][j−1]
return paths[row][col]
2.3. Создание отсортированного списка целых
чисел для задачи выбора Брюсселя
В этой задаче необходимо написать функцию, которая принимает положительные целые числа n, mink и maxk и генерирует отсортированный
список всех положительных целых чисел, образованных подмножеством
цифр m исходного числа, которые либо в 2 раза больше m, либо в 2 раза
меньше. Значения в получившемся списке должны следовать в порядке
возрастания, при этом подмножество m должно попадать в диапазон значений от mink до maxk. В табл. 2.3 показаны ожидаемые результаты для
некоторых входных данных.
Таблица 2.3. Некоторые ожидаемые результаты
для разных входных значений в задаче выбора Брюсселя
n, mink, maxk
Ожидаемый результат
10, 2, 5
[5, 20]
9, 1, 4
18
47, 1, 1
[27, 87, 414]
100, 84, 99
[]
Алгоритм
Алгоритм решения задачи создает список, выполняя определенные
операции с цифрами входного числа n. Указанные операции включают
деление или умножение подмножества цифр на 2 в зависимости от того,
представляет подмножество четное или нечетное целое число. Впоследст
вии полученный список чисел сортируется в порядке возрастания. Для поиска решения используется следующий алгоритм.
22
Глава 2. Математика
1. Алгоритм принимает три параметра: n, mink и maxk.
2. Создается пустой список с именем result.
3. Входное целое число n преобразуется в список его цифр с использованием генератора списков и сохраняется в переменной digits.
4. Далее выполняется цикл, перебирающий значения k в диапазоне
от mink до maxk+1.
5. Для каждого значения k выполняется цикл по i от 0 до len (digits)-k+1.
6. Из списка digits извлекается срез от i до i+k–1, этот срез преобразуется в целое число, которое затем сохраняется в переменной digit.
7. Если digit – четное число, то оно делится на два, и результат сохраняется в переменной half_digit.
8. Создается новый список с именем new_digits, состоящий из первых i
элементов списка digits, за которыми следуют цифры из half_digit
и потом оставшиеся элементы из digits.
9. Список new_digits преобразуется в целое число и сохраняется в переменной new_num.
10. Число new_num добавляется в список result.
11. Значение digit умножается на 2, и результат сохраняется в переменной с именем nd.
12. Создается новый список с именем new_digits, состоящий из первых i
элементов списка digits, за которыми следуют цифры из new_digit
и потом оставшиеся элементы из digits.
13. Список new_digits преобразуется в целое число и сохраняется в переменной new_num.
14. Значение new_num добавляется в конец списка result.
15. Список result сортируется в порядке возрастания с использованием
алгоритма сортировки вставками.
16. И полученный отсортированный список result возвращается вызывающему коду.
В листинге 2.3 приводится код на Python, решающий задачу выбора
Брюсселя.
Листинг 2.3. Решение задачи выбора Брюсселя
1 def insertion_sort(arr):
2
for i in range(1, len(arr)):
3
k = arr[i]
4
j = i − 1
5
while j >= 0 and k < arr[j]:
2.4. Поиск решения обратной гипотезы Коллатца 23
6
arr[j+1] = arr[j]
7
j −= 1
8
arr[j + 1] = k
9
return arr
10
11 def brussels_choice_problem(n, min_k, max_k) :
12
res = []
13
digits = [int(d) for d in str(n)]
14
for k in range(min_k, max_k + 1):
15
for i in range(len(digits) − k + 1):
16
d = int(''.join(str(d)
17
for d in digits[i:i + k]))
18
if d % 2 == 0:
19
hd = d // 2
20
new_digits = digits[:i] + \
21
[int(d) for d in str(hd)] + digits[i + k:]
22
new_num = int(''.join(str(d)
23
for d in new_digits))
24
res.append(new_num)
25
nd = d * 2
26
new_digits = digits[:i] + \
27
[int(d) for d in str(nd)] + digits[i + k:]
28
new_num = int(''.join(str(d)
29
for d in new_digits))
30
res.append(new_num)
31
res = insertion_sort(res)
32
return res
2.4. Поиск решения обратной
гипотезы Коллатца
Гипотеза Коллатца – это математическое утверждение, согласно которому
любое целое число меньше 268, удовлетворяющее двум условиям, указанным в формуле 2.2, в конечном итоге достигнет числа 1 после конечного
числа шагов. Гипотеза касается последовательностей и может быть выражена следующим образом: берется натуральное число n, и из него генерируются два числа в соответствии с формулой 2.2. Этот процесс повторяется для всех последующих чисел, пока последовательность не закончится
единицей.
Ваша задача: написать функцию, которая вычисляет решение обратной
гипотезы Коллатца. Если вычисление дает неверный результат (т. е. нецелое число), то функция должна вернуть значение None. Обратная гипотеза
24
Глава 2. Математика
Коллатца удваивает четные числа, а из нечетных чисел вычитает 1 и делит
разность на 3. Формально гипотеза Коллатца представлена в формуле 2.2,
а обратная гипотеза Коллатца – в формуле 2.3. В табл. 2.4 оказаны ожидаемые результаты для некоторых входных данных.
Таблица 2.4. Некоторые ожидаемые результаты для разных
входных значений в обратной гипотезе Коллатца
shape
Ожидаемый результат
'dd'
4
'uudduuudd'
None
'ududududddddudddd'
15
'uduuddduddduu'
None
Например, если входная строка shape = ududddd, то на первом этапе выбирается последний элемент в shape – символ d и применяется соответствующий ему первый случай в формуле 2.3, т. е. выполняется умножение
на 2, в результате получается x = x × 2 (первоначально x = 1). Далее, продолжая просматривать shape с конца, обнаруживаем три следующих подряд
символа d, поэтому x обновляется следующим образом: x = 2 → 2 × 2 = 4,
x = 4 → 4 × 2 = 8, x = 8 → 8 × 2 = 16. На следующем шаге обнаруживается
символ u, поэтому применяется второй случай в формуле 2.3 и из числа x вычитается 1, а полученная разность делится на 3, соответст
венно, x = 16 → (16–1)/3 = 5, далее снова следует символ d, поэтому
x = 5 → 5 × 2 = 10. Последним следует символ u, соответственно,
x = 10 → (10 × 1)/3 = 3. То есть решением обратной гипотезы Коллатца для
shape = ududdddd является число 3. Чтобы проверить правильность полученного значения, строку, что была передана в обратную гипотезу Коллатца,
нужно сравнить со строкой, получаемой в ходе решения прямой гипотезы Коллатца, согласно формуле 2.2, которая применяется, пока x не достигнет 1. Итак, возьмем предыдущий полученный результат x = 3 и пус
тую строку t. На первом шаге имеем: num = x, (num mod 2) = 1, поэтому
num = (3 ∗ num + 1) → num = (3 ∗ 3 + 1) = 10 и t = u. Продолжим, num = 10,
10 mod 2 = 0, поэтому 10/2 = 5 и t = ud. На следующем шаге num = 5, и мы
все еще не достигли единицы, поэтому num = 5 ∗ 3 + 1 = 16 и t = udu. Далее
выполняется такая последовательность шагов:
num = 16 mod 2 = 0 → num = num/2 = 8 → t = udud,
num = 8 mod 2 = 0 → num = num/2 = 4 → t = ududd,
num = 4 mod 2 = 0 → num = num/2 = 2 → t = ududdd,
num = 2 mod 2 = 0 → num = num/2 = 1 → t = ududddd.
2.4. Поиск решения обратной гипотезы Коллатца 25
x / 2 if x%2 == 0
x=
.
3 x + 1 if x%2 == 1
(2.2)
if x%2 == 0
2x
x=
.
( x − 1) / 3 if x%2 == 1
(2.3)
Алгоритм
Алгоритм решения этой задачи заключается в преобразовании входной строки, состоящей только из символов 'u' и 'd', в числовое значение, согласно обратной гипотезе Коллатца. Алгоритм инициализирует x
числом 1.0 и приступает к обработке каждого символа во входной строке справа налево. Если текущий символ равен 'd', то алгоритм удваивает x. И наоборот, если текущий символ равен 'u', то уменьшает x, согласно обратной гипотезе Коллатца. Если предыдущее значение x не является
целым числом, то алгоритм немедленно возвращает None. Как только все
символы будут обработаны, алгоритм убеждается, что значение x не равно нулю. Далее алгоритм вычисляет ожидаемый результат, применяя гипотезу Коллатца к сгенерированному числу, и сравнивает его с исходной
входной строкой. Если строки совпадают, то алгоритм возвращает вычисленное целое число. В противном случае он возвращает None. В листинге
2.4 приводится код на Python, решающий обратную гипотезу Коллатца.
Листинг 2.4. Поиск решения обратной гипотезы Коллатца
1 def check_if_integer(number):
2
'''
3
Проверить, является ли number целым числом,
4
путем определения остатка от деления на 1
5
'''
6
if number % 1 == 0:
7
return True
8
else:
9
return False
10
11 def pop_last_item(input_list):
12
# Извлекает и удаляет последний символ из input_list
13
list_length = len(input_list)
14
last_item = input_list[list_length−1]
15
del input_list[list_length−1]
16
return last_item
17
18 def Inverse_collatz_conjecture(shape):
'''
Преобразовать входную строку в список символов
и инициализировать x значением 1.0
'''
shape_list = list(shape)
x = 1.0
# Цикл по символам в списке
while shape_list:
item = pop_last_item(shape_list)
if item == 'd':
'''Удвоить значение x, если текущий
символ 'd'
'''
x *= 2
elif item == 'u':
'''Уменьшить значение x, согласно
обратной гипотезе Коллатца, если
текущий символ 'u'
'''
prev = (x − 1) / 3
is_integer = check_if_integer(prev)
'''Если prev имеет целочисленное значение,
то присвоить его переменной x
'''
if is_integer:
x = prev
else:
# Если значение не является целым числом, то вернуть None
return None
# Если x равно 0 или входная строка пустая
if x == 0 or not shape:
return None
true_answer = ''
num = x
'''
Вычисление правильного ответа
согласно прямой гипотезе Коллатца
'''
2.5. Подсчет правильных прямых углов 27
62
63
64
65
66
67
68
69
70
71
72
73
74
while num != 1:
if num % 2 == 0:
true_answer += 'd'
num /= 2
elif num % 2 == 1:
true_answer += 'u '
num = 3 * num + 1
# Сравнить вычисленный и ожидаемый ответы
if true_answer == shape:
return int(x)
else:
return None
2.5. Подсчет правильных прямых углов
В двумерной сетке с целочисленными координатами узлов правильный
прямой угол определяется тремя точками (x, y), (x, y+h) и (x+h, y) для некоторого значения h больше 0. Эти точки образуют фигуру, напоминающую столярный угольник или шеврон, направленный углом влево и вниз, причем
точка (x, y) соответствует острию угла, а (x, y+h) и (x+h, y) определяют концы крыльев одинаковой длины и параллельные осям координат. Напишите
функцию, которая принимает список точек, отсортированных по их координатам x, и возвращает количество правильных прямых углов. В табл. 2.5 показаны ожидаемые результаты для некоторых входных данных.
Таблица 2.5. Некоторые ожидаемые результаты для разных входных
значений в задаче подсчета правильных прямых углов
n, mink, maxk
Алгоритм
Алгоритм подсчета правильных прямых углов отыскивает все комбинации из трех точек в списке, которые образуют угол в форме столярного
угольника или шеврона, как описано в постановке задачи. Для поиска решения используется следующий алгоритм.
1. Переменная counter инициализируется значением 0.
2. Выполняется обход списка точек во вложенном цикле.
28
Глава 2. Математика
3. Для каждой точки проверяется, присутствует ли в списке другая точка с большей координатой x и такой же координатой y.
4. Если такая точка существует, то проверяется, присутствует ли
в списке третья точка, необходимая для формирования угла (согласно определению задачи).
5. Если третья точка существует, то переменная counter увеличивается
на 1.
6. По завершении вернуть значение counter.
В листинге 2.5 приводится код на Python, решающий задачу подсчета
правильных прямых углов.
Листинг 2.5. Подсчет количества углов
1 def counting_possible_corners(points):
2
counter = 0
3
for x, y in points:
4
for x2, y2 in points:
5
if x2 > x and y2 == y and \
6
(x + y2 − y, y + x2 − x) in points:
7
counter += 1
8
return counter
2.6. Ближайшее s‑угольное число
Пусть s > 2 – положительное целое число, определяющее бесконечную
последовательность s‑угольных чисел (их еще называют фигурными числами), где i‑й элемент представлен формулой 2.4. Напишите функцию,
которая принимает число сторон (или углов, если хотите) s и положительное целое число n и возвращает ближайшее s‑угольное число. Если будет
найдено два s‑угольных числа, то функция должна вернуть наименьшее
из них. В табл. 2.6 показаны ожидаемые результаты для некоторых входных данных.
Таблица 2.6. Некоторые ожидаемые результаты для разных
входных значений в задаче поиска ближайшего s‑угольного числа
n, sides
Ожидаемый результат
7, 8
8
1, 19
1
15, 18
18
87, 36
105
2.6. Ближайшее s‑угольное число 29
Алгоритм
Чтобы найти фигурное число с указанным числом сторон, ближайшее
к заданному целому числу n, алгоритм выполняет вычисления в три этапа.
Сначала он вычисляет фигурное число для конкретного индекса i по формуле 2.4. Затем использует двоичный поиск для определения индекса, соответствующего фигурному числу, ближайшему к n. И наконец, для трех
индексов, окружающих средний индекс и полученных посредством двоичного поиска, вычисляет абсолютную разность между фигурными числами и n и возвращает фигурное число, ближайшее к n.
((s − 2) × i ) − ((s − 4) × i ) .
2
(2.4)
2
В листинге 2.6 приводится код на Python, решающий задачу поиска ближайшего s‑угольного числа.
Листинг 2.6. Поиск ближайшего s‑угольного числа
# Получить длину списка
n = len(items)
'''
Если в списке только один элемент,
вернуть его как медиану
'''
if n == 1:
return items[0]
else:
# Создать пустой список для хранения медиан
medians = []
'''
Разбить список на подсписки
по три элемента, отсортировать их и
взять средние элементы как медианы
'''
for i in range(0, n, 3):
sublist = items[i:i + 3]
if len(sublist) < 3:
median = sublist[len(sublist) // 2]
else:
sorted_sublist = insertion_sort(sublist)
median = sorted_sublist[1]
medians.append(median)
'''
Рекурсивно вызывать функцию со
списком medians, пока
не останется не более трех элементов
'''
if len(medians) > 3:
return median_of_medians(medians)
else:
'''
Если осталось три элемента или меньше,
то отсортировать их и взять средний
элемент, который и будет конечной медианой
'''
sorted_items = insertion_sort(medians)
return sorted_items[len(sorted_items) // 2]
38
Глава 2. Математика
2.11. Наименьшее число из семерок и нулей
В западной культуре число семь считается символом удачи, а число ноль,
напротив, считается нежелательным. Числа, составленные из семерок
и нулей, такие как 77777777777777777 или 77700, часто называют «семьноль». Одна замечательная теорема доказывает, что для любого положительного целого числа существует множество целых чисел, составленных
из семерок и нулей, которые делятся на n без остатка.
Ваша задача: написать функцию, которая отыскивает наименьшее положительное целое число, состоящее из семерок и нулей, которое без остатка
делится на заданное число n. При этом число, состоящее из одних нулей,
не считается желаемым результатом.
В табл. 2.11 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.11. Некоторые ожидаемые результаты для задачи поиска
наименьшего числа из семерок и нулей
n
Ожидаемый результат
25
700
49
777777
1023
777777777777777777777777777777
104
777777000
Алгоритм
Чтобы определить наименьшее целое число, состоящее только из 7 или
из комбинации семерок и нулей, которое без остатка делится на заданное
положительное целое число, используется алгоритм, который выполняет итерации по возрастающим степеням числа 10, пока не будет найдено число, кратное n, состоящее только из семерок (например, 777777) или
семерок и нулей (например, 777777000). Начальное пространство поиска
находится в диапазоне от 1 до 10.
В каждой итерации к произведению предыдущего остатка на 10 прибавляется 7. Если остаток числа появляется более одного раза, это указывает на то, что данная последовательность цифр из семерок и нулей представляет число, кратное n, которое начинается с 7 и заканчивается на 0.
Если достигнут остаток 0, то это говорит о том, что число, начинающееся
с цифры 7 и кратное числу n, найдено.
Если в текущем диапазоне поиска решение не обнаружено, то алгоритм
расширяет диапазон поиска и продолжает итерации. Ниже подробно описаны шаги алгоритма.
2.11. Наименьшее число из семерок и нулей 39
1. Создается словарь с именем remainder_positions для отслеживания
остатков и их позиций в каждой итерации. Создается переменная
current_remainder с начальным значением 0.
2. Переменные digits_min и digits_max инициализируются начальными
значениями 1 и 10 соответственно. Они определяют пространство
поиска числа из семерок и нулей, кратного n, и переменная num_digits
изменяется в диапазоне от digits_min до digits_max.
3. Затем запускается цикл while, который выполняется до тех пор, пока
не будет найдено число из семерок и нулей, кратное n.
4. В цикле while переменная num_digits последовательно получает значение от digits_min до digits_max включительно.
5. Для каждого значения num_digits вычисляется остаток по формуле
(current_remainder ∗ 10 + 7) % n.
6. Если текущий остаток равен нулю, возвращается целое число, состоящее из последовательности семерок.
7. Если текущий остаток уже появлялся раньше, то из предыдущего
и текущего блоков формируется число, кратное числу n, которое
начинается с 7 и заканчивается 0. Для этого отыскивается позиция i предыдущего вхождения current_remainder в словаре remainder_
positions и целое число, состоящее из последовательности 7, за которой следуют 0 с использованием выражения
'7' ∗ (num_digits – i) + '0' ∗ i.
8. Если текущий остаток ранее не появлялся, он добавляется в словарь
remainder_positions со своей позицией num_digits.
9. После завершения всех итераций в текущем пространстве поиска оно расширяется путем установки digits_min равным digits_max
и умножения digits_max на 10.
10. Шаги 4–9 повторяются до тех пор, пока не будет найдено число
из семерок и нулей, кратное заданному числу n. Если число из семерок и нулей не отыщется, то итерации будут продолжаться бесконечно.
В листинге 2.11 приводится код на Python, решающий задачу поиска
числа из семерок и нулей, кратного заданному числу n.
Листинг 2.10. Поиск наименьшего числа из семерок и нулей
1 def Smallest_Seven_Zero(n):
2
# Словарь для хранения остатков и их позиций
remainder_positions = {}
current_remainder = 0
# Определить начальное пространство поиска
digits_min = 1
digits_max = 10
'''
Выполнять итерации по степеням 10,
пока не будет найдено число, кратное n
'''
while True:
for num_digits in range(digits_min, digits_max ):
current_remainder = \
(current_remainder * 10 + 7) % n
if current_remainder == 0:
return int('7' * num_digits)
elif current_remainder in remainder_positions:
# объединить предыдущий блок с текущим
i = remainder_positions[current_remainder]
return int('7' * (num_digits − i) + '0' * i)
else:
remainder_positions[current_remainder ] =\
num_digits
# Расширить пространство поиска, если необходимо
digits_min = digits_max
digits_max *= 10
2.12. Оценка математических выражений
в постфиксной нотации
Целью этой задачи являются преобразование математических выражений
из постфиксной нотации в инфиксную и их оценка. В инфиксной нотации операторы в математическом выражении записываются между парами операндов, например a + b. В постфиксной нотации оператор следует
за парой операндов, например a b +. Соответственно, выражение 2 7 + 3 *,
записанное в постфиксной нотации, эквивалентно выражению (2 + 7) *
3 в инфиксной нотации, которое дает в результате число 27.
Ваша задача: написать функцию, возвращающую числовой результат,
но не эквивалент в инфиксной нотации.
2.12. Оценка математических выражений в постфиксной нотации 41
В табл. 2.12 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.12. Некоторые ожидаемые результаты для задачи
оценки математических выражений, записанных в постфиксной нотации
Выражение
Ожидаемый результат
[5, 6, '+', 7, '*']
77
[3, 7, 9, '*', '+']
66
[3, 7, 9, '/', '+']
3
[8, 2, '+']
10
Алгоритм
Алгоритм оценки выражения в постфиксной нотации выполняет следующие шаги.
1. Выбирает каждый элемент из заданного выражения в постфиксной
нотации.
2. Если элемент является целым числом, то он добавляется в список
Storage.
3. Если элемент является оператором (+, –, ∗, /), то из списка Storage извлекаются два последних элемента (операнда).
4. И затем с этой парой операндов выполняется соответствующая операция (+, –, ∗, /). Результат операции сохраняется в переменной result
и затем добавляется в список Storage.
5. Шаги 3–4 повторяются до тех пор, пока не будут обработаны все
элементы в выражении.
6. В завершение возвращается результат – последний элемент в спис
ке Storage.
В листинге 2.12 приводится код на Python, решающий задачу оценки математических выражений в постфиксной нотации.
Листинг 2.12. Оценка математических выражений в постфиксной нотации
1 def pop_last_item(input_list):
2
# Извлекает последний элемент из входного списка и возвращает его
3
list_length = len(input_list)
4
last_item = input_list[list_length − 1]
5
del input_list[list_length − 1]
42
Глава 2. Математика
6
return last_item
7 def postfix_evaluate(Postfix):
8
'''
9
Создать пустой список для
10
хранения операндов и результатов
11
'''
12
Storage = []
13
14
'''
15
Выполнить обход элементов в списке Postfix
16
с выражением, записанным в постфиксной нотации
17
'''
18
for item in Postfix:
19
'''
20
Если это целое число,
21
то добавить его в конец списка Storage
22
'''
23
if isinstance(item, int):
24
Storage.append(item)
25
else:
26
'''
27
Если это оператор,
28
то извлечь два последних операнда из списка Storage
29
'''
30
Number0, Number1 = \
31
pop_last_item(Storage), pop_last_item(Storage)
32
'''
33
Выполнить соответствующую операцию
34
с двумя операндами
35
'''
36
if item == '−':
37
result = Number1 − Number0
38
elif item == '+':
39
result = Number1 + Number0
40
elif item == '*':
41
result = Number1 * Number0
42
elif item == '/':
43
result = \
44
Number1 // Number0 if Number0 != 0 else 0
45
Storage.append(result)
46
47
return pop_last_item(Storage)
2.13. Достижение стабильного состояния в болгарском пасьянсе 43
2.13. Достижение стабильного состояния
в болгарском пасьянсе
В этой задаче дается список из n карт, представленных положительными
целыми числами. Цель состоит в том, чтобы продолжать генерировать новые списки чисел, отличающиеся от исходного, пока не будет достигнуто
стабильное состояние. Под стабильным состоянием понимается ситуация,
когда новый список содержит те же элементы, что и предыдущий список,
но сами элементы могут быть упорядочены иначе.
При генерировании новых списков применяются два правила:
1) сумма чисел в списке должна быть равна треугольному числу (тре
угольные числа определяются согласно формуле 2.6);
k × ( k + 1)
;
2
(2.6)
2) при создании нового списка на каждом этапе из всех чисел вычитается одна единица, а последним элементом списка становится длина предыдущего списка. Если результат вычитания равен нулю, он
удаляется.
Этот процесс повторяется до тех пор, пока не будет достигнуто стабильное состояние. Таким образом задача требует найти список, удовлетворяющий обоим условиям. Этот процесс называется болгарским
пасьянсом. Например, подсчитаем количество шагов для достижения
стабильного состояния для [3] – заданного списка чисел и k = 2. Сначала необходимо проверить, равно ли треугольное число сумме элементов
данного списка:
k × (k + 1)/2 → 2 × (2 + 1)/2 = 3, т. е. 3 = 3.
Следующие шаги показывают, как достигается стабильное состояние:
[3] → [2, 1] → [1, 2, 0] → [1, 2].
Поскольку элементы [2, 1] и [1, 2] равны, можно считать, что стабильное
состояние достигнуто, даже притом что элементы в списках [2,1] и [1, 2]
упорядочены по-разному. Поэтому стабильное состояние достигается уже
после одного шага.
Ваша задача: написать функцию, которая принимает список из n положительных целых чисел и треугольное число и возвращает количество шагов, необходимых для достижения стабильного состояния.
В табл. 2.13 показаны ожидаемые результаты для некоторых входных
данных.
44
Глава 2. Математика
Таблица 2.13. Некоторые ожидаемые результаты для задачи подсчета
шагов, необходимых для достижения стабильного состояния
Points, k
Ожидаемый результат
[3], 2
1
[3, 7, 8, 14], 4
0
[10, 10, 10, 10, 10, 5],10
74
[3000, 2050], 100
7325
Один из важнейших шагов в решении этой задачи – правильное определение момента стабилизации. Для этого нужно отсортировать текущий
список и сравнить его с предыдущим. Если два списка совпадают, то это
указывает, что стабильное состояние достигнуто. Однако, несмотря на кажущуюся простоту, этот подход может быть очень сложным.
Для определения состояния (стабильного или нет) используются два алгоритма: is_stable_state и Stable_State_in_Bulgarian_Solitaire.
Алгоритм
Алгоритм Stable_State_in_Bulgarian_Solitaire выполняет следующие шаги.
1. Принимает два аргумента: points (список положительных целых чисел) и k (целое число). Инициализирует переменную number_of _moves
значением 0.
2. Вычисляет сумму чисел во входном списке по формуле
k ∗ (k + 1)//2
и сохраняет ее в переменной equation.
3. Вызывает алгоритм is_stable_state, который принимает два аргумента: points (список положительных целых чисел) и k (целое число).
4. Сравнивает сумму чисел в списке points со значением equation. Если
они не равны, то возвращает ноль, чтобы сообщить, что стабильное
состояние пока не достигнуто. Пока стабильное состояние не будет
достигнуто, выполняется следующий цикл:
• из каждого элемента в списке points вычитается 1;
• из списка points удаляются все нулевые значения;
• в конец списка points добавляется элемент с длиной текущего
списка точек;
• переменная number_of _moves увеличивается на 1;
• проверяется стабильность текущего состояния с использованием алгоритма is_stable_state.
5. Возвращает конечное значение number_of _moves.
2.13. Достижение стабильного состояния в болгарском пасьянсе 45
6. Алгоритм is_stable_state выполняет следующие шаги.
7. Принимает два аргумента: points (список целых положительных чисел) и k (целое число).
8. Создает массив count с k+1 нулями.
9. Перебирает в цикле значения p в списке points и увеличивает соответствующий элемент в count, если p меньше или равно k.
10. Перебирает элементы в массиве count и сравнивает каждый c 1. Если
встречается элемент, не равный 1, то возвращается False, указывающее, что состояние нестабильно.
11. Если цикл завершается без возврата False, то возвращается True, указывающее, что состояние стабильно.
В листинге 2.13 приводится код на Python, определяющий состояние
в болгарском пасьянсе.
Листинг 2.13. Определение состояния в болгарском пасьянсе
1 def Stable_State_in_Bulgarian_Solitaire(points, k):
2
# Инициализировать число ходов нулем
3
number_of_moves = 0
4
5
'''
6
Формула вычисления
7
суммы очков
8
'''
9
equation = k * (k + 1) // 2
10
11
def is_stable_state(points, k):
12
"""
13
Для отслеживания частоты каждого целого числа
14
между 1 и k в списке points
15
используется массив счетчиков count. Если какое-то
целое число встречается несколько раз или вообще не встречается,
16
17
то это значит, что стабильное состояние пока не достигнуто
18
и поэтому функция должна вернуть False.
19
И напротив, если каждое число от 1 до k
20
встречается ровно один раз, то функция возвращает True,
21
указывая, что стабильное состояние достигнуто.
22
"""
23
count = [0] * (k + 1)
24
for p in points:
25
if p 0]
'''
Добавить новый элемент в points
с размером списка после удаления нулевых элементов
'''
points.append(points_Length)
# Увеличить счетчик ходов
number_of_moves += 1
# Вернуть общее число ходов
return number_of_moves
2.14. Вычисление площади прямоугольных
башен Манхэттена на линии горизонта
Есть список прямоугольных башен в виде (s, e, h), где s, e и h – это начало
и конец на оси X и высота соответственно. Ваша задача: написать функцию, которая принимает кортеж (s, e, h) и возвращает площадь прямо
угольных башен. Обратите внимание, что общая площадь башен не должна вычисляться дважды.
В табл. 2.14 показаны ожидаемые результаты для некоторых входных
данных.
2.14. Вычисление площади прямоугольных башен Манхэттена на линии горизонта 47
Таблица 2.14. Некоторые ожидаемые результаты для задачи вычисления
площади прямоугольных башен Манхэттена на линии горизонта
Towers
Ожидаемый результат
[(2, 6, 98), (1, 0, 9)]
383
[(3, 7, 1)]
4
[(–8, 6, 3), (6, 14, 11), (0, 4,–5)]
130
[(2, 550, 222), (1, 0, 4)]
121652
Алгоритм
Для вычисления площади данных башен используются два алгоритма:
divide и Manhattan_Skyline. Алгоритм divide выполняет следующие шаги.
1. Принимает два параметра: start и end. Если start равно end, то возвращается список, содержащий два элемента: [towers [start] [0],
towers [start] [2]] и [towers [start] [1],0].
2. В противном случае вычисляется средняя точка между началом
и концом и алгоритм рекурсивно вызывается для левой и правой
половин списка башен. Затем результаты для левой и правой половин объединяются в новый список. На этом шаге выполняются следующие действия:
• вычисляется средняя позиция;
• создается пустой список merged и инициализируются нулем две
переменные i и j;
• инициализируются значением None две переменные h1 и h2;
• в цикле выполняется обход элементов списка merged по диапазону len (left) + len (right);
• если значение i больше или равно длине списка left, то в merged
добавляется список, содержащий [right [j] [0], right [j] [1] if
h1 is None else max (h1, right [j] [1])], затем j увеличивается
на 1 и цикл продолжается;
• если значение j больше или равно длине списка right, то в merged
добавляется список, содержащий [left [i] [0], left [i] [1] if
h2 is None else max (h2, left [i] [1])], затем i увеличивается
на 1 и цикл продолжается;
• если координата X i‑го элемента в left меньше или равна координате X j‑го элемента, то в merged добавляется список, содержащий [left [i] [0], left [i] [1] if h2 is None else max (h2, left
[i] [1])], затем переменной h1 присваивается координата Y i‑го
элемента в left и i увеличивается на 1;
48
Глава 2. Математика
• в противном случае в merged добавляется список [right [j] [0],
right [j] [1] if h1 is None else max (h1, right [j] [1])], затем
переменной h2 присваивается координата Y j‑го элемента в right
и j увеличивается на 1.
3. В завершение возвращается объединенный список merged.
Алгоритм Manhattan_Skyline выполняет следующие шаги.
1. Принимает список башен towers.
2. Вычисляет площадь, ограниченную линией горизонта, с использованием divide.
3. Возвращает вычисленную площадь.
В листинге 2.14 приводится код на Python, вычисляющий площади прямоугольных башен Манхэттена на линии горизонта.
Листинг 2.14. Вычисление площади прямоугольных башен Манхэттена
на линии горизонта
1 def rectangular_towers_in_manhattan_skyline(towers):
2
3
''' divide_and_conquer вычисляет
4
линию горизонта для данного диапазона башен
5
'''
6
def divide_and_conquer(start, end):
7
'''
8
Если в заданном диапазоне имеется только одна башня,
9
то вернуть координаты X ее начала и конца
10
'''
11
if start == end:
12
return [[towers[start][0],
13
towers[start][2]],
14
[towers[start][1],0]]
15
16
'''
17
Разделить диапазон на две половины и
18
рекурсивно вычислить линии горизонта для каждой половины
19
'''
20
mid = (start + end) // 2
21
left = divide_and_conquer(start, mid)
22
right = divide_and_conquer(mid + 1, end)
23
24
'''
25
Объединить две линии горизонта,
2.14. Вычисление площади прямоугольных башен Манхэттена на линии горизонта 49
используя слияние с сортировкой
'''
merged = []
i, j = 0, 0
# Высоты левой и правой башен
h1, h2 = None, None
for x in range(len(left) + len(right)):
if i >= len(left):
merged.append([right[j][0], right[j][1]
if h1 is None else max(h1, right[j][1])])
j += 1
elif j >= len(right):
merged.append([left[i][0],left[i][1]
if h2 is None else max(h2, left[i][1])])
i += 1
'''
Если следующий элемент в left
совпадает со следующим
элементом в right, то добавить
элемент из left и обновить его высоту
'''
elif left[i][0] 0,
представляющие острие угла с двумя крыльями. Ваша задача: написать
функцию, которая принимает список точек, упорядоченных по углам,
и возвращает минимальное количество точек, которые необходимо удалить из списка, чтобы исключить все правильные прямые углы.
В табл. 2.16 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.16. Некоторые ожидаемые результаты для задачи удаления правильных
прямых углов в двумерной сетке
Points
Алгоритм
Чтобы удалить все углы, образованные тройками точек в заданном
списке, путем удаления из списка минимального количества точек, алгоритм сначала выявляет все правильные прямые углы, которые образуют
54
Глава 2. Математика
тройки точек во входном списке, используя вложенные циклы. Затем он
использует рекурсию с мемоизацией, чтобы определить минимальное
количество точек, которые необходимо удалить из списка, дабы удалить
все правильные прямые углы.
В листинге 2.16 приводится код на Python, вычисляющий минимальное
количество точек, которые нужно удалить из входного списка, чтобы удалить все правильные прямые углы.
Листинг 2.16. Вычисление минимального количества точек, которые нужно удалить
из входного списка, чтобы удалить все правильные прямые углы
'''
Рекурсивно удаляет минимальное количество точек для удаления углов
'''
def MinCornerRemover(corners, memo):
'''
Базовый случай: если список углов пуст
и ничего не нужно удалять
'''
if len(corners) == 0:
return 0
'''
Проверить, обрабатывался ли
текущий список углов прежде
'''
key = tuple(corners)
if key in memo:
return memo[key]
removals = len(corners)
'''
Инициализировать множество, в котором запоминаются
уже обработанные точки
'''
points_set = set ( )
# Цикл по углам в списке
for corner in corners:
'''
Цикл по точкам
текущего угла
2.16. Удаление правильных прямых углов в двумерной сетке 55
'''
for point in corner:
'''
Если точка еще не обрабатывалась,
то добавить ее в множество
'''
if point not in points_set:
points_set.add(point)
'''
Вычислить углы, оставшиеся
после исключения текущей точки
'''
remaining_corners = \
[c for c in corners if point not in c]
'''
Рекурсивно вычислить минимальное число
удаляемых точек для удаления остальных углов
'''
'''и прибавить 1, чтобы учесть
текущую удаленную точку
'''
removals = \
min(1 + MinCornerRemover \
(remaining_corners, memo), removals)
'''
Запомнить результат для текущего
списка углов
'''
memo[key] = removals
# Вернуть минимальное число удаленных точек
return removals
'''
Удаляет все углы
из заданного списка точек
'''
# Принимает список кортежей, представляющих точки
def cut_corners(points):
# Создать пустой список для хранения углов
corners = [ ]
# Цикл по точкам в списке
for i in range(len(points)):
x = points[i][0]
y = points[i][1]
'''
Проверить, имеется ли другая точка
с такой же координатой y
'''
# т. е. имеется ли другая точка правее текущей
for j in range(i + 1, len(points)):
if points[j][1] == y:
h = points[j][0] − x
'''Проверить, имеется ли точка на h единиц
выше текущей
'''
'''и правее другой точки
с той же координатой y
'''
if h > 0 and (x, y + h) in points:
'''
Добавить кортеж, представляющий угол
в список углов corners
'''
corners.append \
(((x, y), (x + h, y), (x, y + h)))
'''
Создать пустой словарь
для хранения прежде вычисленных результатов
'''
memo = {}
'''
Вызвать функцию, которая рекурсивно удалит
минимальное количество точек с использованием мемоизации
'''
return MinCornerRemover(corners, memo)
2.17. Треугольник Лейбница
В треугольнике Паскаля каждое число равно сумме двух чисел, находящихся непосредственно над ним, тогда как в треугольнике Лейбница каждое
число равно сумме двух чисел под ним.
Ваша задача: написать функцию, которая принимает значения крайней
левой грани треугольника и возвращает соответствующее значение нижнего ряда в указанной позиции.
2.17. Треугольник Лейбница 57
В табл. 2.17 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.17. Некоторые ожидаемые результаты для задачи вычисления значений
в нижней грани гармонического треугольника Лейбница
LeftMost_Values, positions
Ожидаемый результат
[1, 2, 3], range (3)
[3,–1, 0]
[4, 7, 9, 3], range (4)
[3, 6,–8, 7]
[88, 90, 1, 0, 9], range (4)
[9,–9, 10, 78]
[20, 95], range (2)
[95,–75]
Например, на рис. 2.2 показаны два численных примера треугольника
Лейбница. Входными данными для первого примера (А) являются 2 и 3,
а позиция – range (2). Функция range возвращает последовательность
чисел, начинающуюся с 0, поэтому нулевой и первой позициям отвечают 2 и 1 соответственно.
Входные
данные
Позиции
Ожидаемый
результат
[3, 2]
range (2)
[2, 1]
3
?
2
3–2=1
А) Числовой пример треугольника Лейбница
Входные
данные
Алгоритм
Для решения поставленной задачи воспользуемся алгоритмом, выполняющим следующие шаги.
1. Принимает два входных параметра: LeftMost_Rows – список значений, представляющих крайнюю левую грань треугольника Лейбница, и positions – список целых чисел, представляющих позиции
в нижней грани, значения для которой нужно найти.
2. Создается пустой список result для хранения искомых значений.
3. Создается словарь memo для хранения промежуточных значений, вычисленных в ходе решения.
4. На основе представленных значений в левой грани вычисляются
значения в первом столбце треугольника.
5. Полученные значения сохраняются в словаре memo с ключами, соответствующими индексам.
6. На основе значений из предыдущего ряда вычисляются оставшиеся значения в треугольнике.
7. Каждое значение в треугольнике вычисляется как разность между
значением, стоящим выше текущего ряда, и значением в текущем
ряду.
8. Полученные значения сохраняются в словаре memo с ключами, соответствующими индексам.
9. Значения, соответствующие нижней грани треугольника, хранящие
ся в словаре, добавляются в список результатов result.
10. Полученный список возвращается.
11. В листинге 2.17 приводится код на Python, вычисляющий значения
в нижней грани гармонического треугольника Лейбница.
Листинг 2.17. Вычисление значений в нижней грани гармонического
треугольника Лейбница
1
2
3
4
5
6
7
8
9
10
'''
Эта функция принимает два аргумента:
список значений, представляющих
левую грань треугольника Лейбница,
и список целых чисел, представляющих
позиции в нижней грани тругольника,
для которых нужно найти значения.
'''
def Leibniz_triangle(LeftMost_Rows, positions):
'''
Создать пустой список для хранения
искомых результатов
'''
result = []
'''
Создать словарь для хранения результатов
промежуточных вычислений, выполняемых в ходе алгоритма
'''
memo = {}
'''
Вычислить значения в первом столбце треугольника,
опираясь на представленные значения в левой грани.
'''
for i in range(len(LeftMost_Rows)):
memo[(i, 0)] = LeftMost_Rows[i]
'''
На основе предыдущего столбца вычислить
остальные значения в треугольнике.
'''
for i in range(1, len(LeftMost_Rows)):
for j in range(1, i + 1):
'''
Каждое значение в треугольнике вычисляется
как разность между вышестояшим и нижестоящим
значениями
'''
value = memo[(i − 1, j − 1)] − memo[(i, j − 1)]
memo[(i,j)] = value
'''
Извлечь значения для нижней грани
треугольника из словаря
memo и добавить их
в список результатов result.
'''
for i in positions:
result.append(memo[(len(LeftMost_Rows) − 1, i)])
# Вернуть результаты.
return result
60
Глава 2. Математика
2.18. Расстояние Коллатца
Имея заданное целое число n, требуется достичь некоторого положительного целого числа с применением формул 3 × n + 1 и n//2, взятых из гипотезы Коллатца. Пусть путь между начальным и конечным числами start
и goal имеет несколько слоев, содержащих по нескольку положительных
целых чисел. Первый слой инициализируется начальным числом start. Все
положительные целые числа имеют одинаковое расстояние в каждом слое.
Начиная с начального числа start для каждого следующего слоя генерируются числа однократным применением формул 3 × n + 1 и n//2 к каждому
числу в предыдущем слое. Создание слоев продолжается, пока в каком-то
из них не будет получено искомое число goal. Рассмотрим следующий пример. Пусть start = 10 и goal = 20. На каждом шаге генерируется несколько
положительных целых чисел с одинаковым расстоянием, пока не будет
получено число goal. Поскольку первый (будем считать его нулевым) слой
инициализируется числом start, в нем имеется только число 10. Далее:
• слой 1: к числу 10 применяются формулы 3 × n + 1 и n//2, и получаются два числа (3n + 1) = (3 × 10 + 1) = 31, (n//2) = (10//2) = 5;
• слой 2: к числам 31 и 5 применяются те же формулы, и получаются
четыре числа (3 × 31 + 1) = 94, (3 × 5 + 1) = 16, (31//2) = 15, (5//2) = 2;
• слой 3: 283, 49, 46, 7, 47, 8, 7, 1;
• слой 4: 850, 148, 139, 22, 142, 25, 22, 4, 141, 24, 23, 3, 23, 4, 3, 0;
• слой 5: 2551, 445, 418, 67, 427, 76, 67, 13, 424, 73, 70, 10, 70, …;
• слой 6: 7654, 1336, 1255, 202, 1282, 229, 202, 40, …;
• слой 7: 22963, 4009, 3766, …, 20…
Как видите, в слое 7 обнаружилось целевое число 20. Ваша задача: написать функцию, которая принимает начальное и конечное числа и возвращает номер слоя, в котором присутствует целевое число.
В табл. 2.18 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.18. Некоторые ожидаемые результаты для задачи
поиска целевого числа на основе расстояния Коллатца
Start, goal
Ожидаемый результат
20, 321
9
22, 15
8
4, 7
2
10, 20
7
2.18. Расстояние Коллатца 61
Алгоритм
Для достижения целевого числа используется метод поиска в ширину
(Breadth-First Search, BFS). Алгоритм BFS сначала обходит все узлы на одном уровне и только потом переходит на следующий. В нашем случае
каждый сгенерированный слой, возникающий в результате применения
формул из гипотезы Коллатца, образует уровень, который нужно исследовать. Алгоритм начинает исследование с числа start_num, представляющего первый слой, и генерирует последующие слои, применяя одни и те же
формулы. Вот подробное описание шагов алгоритма.
1. Принимаются два положительных целых числа start_num и goal_num.
2. Инициализируются переменные num_layers и curr_layer, где num_
layers = 0 и curr_layer – множество, содержащее только начальное
число, т. е. start_num.
3. Пока goal_num не обнаружится в curr_layer, выполняются следующие
действия:
• создается пустое множество next_layer (поскольку повторяющиеся числа нам не нужны);
• для каждого числа в curr_layer вычисляются значения по формулам num//2 и 3 ∗ num + 1;
• эти значения добавляются в next_layer;
• значение next_layer присваивается переменной curr_layer;
• num_layers увеличивается на 1.
4. Если goal_num присутствует в curr_layer, то возвращается num_layers.
В листинге 2.18 приводится код на Python, вычисляющий расстояние
Коллатца.
Листинг 2.18. Вычисление расстояния Коллатца
1 def get_collatz_distance(start_num, goal_num):
2
"""
3
Принимает начальное и целевое числа
4
и генерирует все слои с положительными
5
целыми числами, используя последовательность
6
Коллатца для поиска кратчайшего пути от
7
start_num до goal_num.
8
"""
9
# Инициализировать счетчик слоев
10
num_layers = 0
11
'''
12
Инициализировать текущий слой как
множество с единственным числом start_num
'''
curr_layer = {start_num}
'''
Продолжать выполнять цикл, пока в текущем слое
не обнаружится число goal_num
'''
while goal_num not in curr_layer:
'''
Создать пустое множество,
представляющее следующий слой
'''
next_layer = set ( )
for num in curr_layer:
'''Сгенерировать следующие числа в
последовательности Коллатца для каждого числа
в текущем слое
'''
next_layer.update([
num // 2,
3 * num + 1
])
'''
Сделать текущим вновь
сгенерированный слой
'''
curr_layer = next_layer
'''
Увеличить счетчик слоев
'''
num_layers += 1
'''
Вернуть количество слоев, которые потребовалось
пересечь для достижения целевого числа
'''
return num_layers
2.19. Сумма двух квадратов
Дано положительное целое число n, и требуется найти два числа, сумма
квадратов которых равна n. Например, если n равно 145, то ответом будет
пара чисел (12, 1). Если есть несколько ответов, то следует выбрать ответ
2.19. Сумма двух квадратов 63
с наибольшим максимальным числом. Например, для n = 50 есть два возможных ответа: (7, 1) и (5, 5). Поскольку 7 больше 5, правильный ответ:
(7, 1). Ваша задача: написать функцию, которая принимает положительное
целое число n и возвращает два числа, сумма квадратов которых равна n.
Если таких чисел нет, функция должна вернуть None.
В табл. 2.19 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.19. Некоторые ожидаемые результаты
для задачи суммы двух квадратов
n
Ожидаемый результат
50
(7,1)
145
(12, 1)
1480
(38, 6)
540
None
Алгоритм
Алгоритм находит основания второй степени, сначала выбирая максимальное значение для первого основания, а затем проверяя все значениякандидаты для второго основания. Если значение-кандидат для второго
основания дает пару оснований, удовлетворяющих условиям, то функция
возвращает эту пару. Вот подробное описание шагов алгоритма.
1. Принимается целое положительное число n.
2. Вычисляется максимальное значение первого основания как квад
ратный корень из половины числа n.
3. Создается набор возможных значений для второго основания
от 1 до значения первого основания.
4. Перебираются возможные значения второго основания.
5. Для каждого возможного значения второго основания вычисляется
разность между n и квадратом второго основания.
6. Вычисляется квадратный корень разности.
7. Проверяется равенство квадрата корня разнице.
8. Если равно, то возвращается пара оснований, сумма квадратов которых равна n.
9. Если такой пары не существует, возвращается None.
В листинге 2.19 приводится код на Python, отыскивающий пару чисел,
сумма квадратов которых равна заданному числу.
64
Глава 2. Математика
Листинг 2.19. Поиск пары чисел, сумма квадратов которых равна заданному числу
1 def get_squares_summing_to_n(n ) :
2
"""
3
Эта функция возвращает кортеж с двумя
4
целыми числами, сумма квадратов которых равна n.
5
"""
6
# Максимальное значение первого основания
7
max_first_base = int((n / 2) ** 0.5)
8
# Множество значений-кандидатов для второго основания
9
'''
10
Второе основание не может быть больше первого,
11
поэтому 1 + max_first_base
12
'''
13
candidates = set(range(1, 1 + max_first_base))
14
# Цикл по значениям-кандидатам второго основания
15
for second_base in candidates:
16
'''
17
Вычислить разность между n
18
и квадратом второго основания
19
'''
20
difference = n − second_base ** 2
21
# Вычислить квадратный корень разности
22
root = int(difference ** 0.5)
23
'''
24
Сравнить квадрат корня
25
с разностью
26
'''
27
if root ** 2 == difference:
28
'''
29
Вернуть пару оснований,
30
сумма квадратов которых равна n
31
'''
32
return (root, second_base)
33
# Если пара не найдена, вернуть None
34
return None
2.20. Поиск трех чисел
Дан отсортированный список положительных целых чисел, в котором
нужно отыскать три числа, сумма которых равна заданному.
Ваша задача: написать функцию, которая принимает отсортированный
список положительных целых чисел и возвращает True, если в списке есть
2.20. Поиск трех чисел 65
три числа, сумма которых равна заданному числу target, в противном случае она должна возвращать False.
В табл. 2.20 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.20. Некоторые ожидаемые результаты для задачи поиска трех чисел
ListNumbers, target
Ожидаемый результат
[3, 5, 6, 8, 9, 21], 14
True
[2, 4, 8, 16, 32], 16
False
[550, 600, 2000, 3000, 4000], 900
False
[1, 2, 16, 79, 80, 340], 83
True
Алгоритм
В решении используются три вложенных цикла for для обхода всех чисел
и сравнения их сумм с целевым числом target. Однако это простое решение имеет высокую временную сложность. Для достижения поставленной
задачи алгоритм использует следующие шаги.
1. Принимается отсортированный список чисел и целевое число target.
2. Длина списка сравнивается с числом 3. Если она меньше, то возвращается False.
3. Выполняется обход элементов списка.
4. Для каждого числа в списке вычисляется новое целевое число, вычитанием текущего числа из целевого.
5. На следующем этапе используется алгоритм поиска двух чисел. Алгоритм поиска двух чисел принимает список чисел и целевое число
и возвращает True, если в списке есть два числа, сумма которых равна целевому числу. В противном случае возвращается False.
6. Алгоритм поиска двух чисел выполняет следующие шаги:
а) длина списка сравнивается с числом 3. Если она меньше, то возвращается False;
б) инициализируются два указателя: один указывает на начало
списка, а другой – на его конец;
в) пока начальный указатель меньше конечного указателя:
1) вычисляется сумма двух чисел в позициях начального и конечного указателей;
2) если сумма равна целевому числу, вернуть True;
3) если сумма меньше целевого числа, увеличивается начальный указатель, чтобы перейти к большему числу;
66
Глава 2. Математика
4) если сумма больше целевого числа, уменьшается конечный
указатель, чтобы перейти к меньшему числу;
д) если совпадение не найдено, возвращается False.
7. Если такая пара существует, возвращается True.
8. Если в списке не найдено совпадений, возвращается False.
В листинге 2.20 приводится код на Python, отыскивающий три числа,
сумма которых равна заданному числу.
Листинг 2.20. Поиск трех чисел, сумма которых равна заданному числу
1 def has_two_sum(numbers, target):
2
'''
3
Если длина списка
4
меньше 2, то в нем
5
невозможно найти два числа,
6
сумма которых равна заданному числу
7
'''
8
if len(numbers) < 2:
9
return False
10
11
'''Инициализировать указатели, указывающие
12
на начало и конец списка
13
'''
14
start = 0
15
end = len(numbers) − 1
16
17
'''Продолжать перемещать указатели,
18
пока они не встретятся
19
'''
20
while start < end:
21
two_sum = numbers[start] + numbers[end]
22
23
'''Если сумма двух чисел равна
24
целевому, значит, мы нашли ответ
25
'''
26
if two_sum == target:
27
return True
28
29
'''Если сумма меньше целевого числа,
30
то увеличить указатель start,
31
чтобы перейти к следующему большему числу
32
'''
elif two_sum < target:
start += 1
# Если сумма больше целевого числа,
# то уменьшить указатель end,
# чтобы перейти к следующему меньшему числу
else:
end −= 1
'''Если искомой пары чисел не нашлось,
то вернуть False
'''
return False
'''
Главная функция, отыскивающая три числа
в сортированном списке целых чисел,
сумма которых
равна целевому числу
'''
def has_three_summers(numbers_list, goal):
'''Если длина списка
меньше 3, то в нем невозможно
найти три числа,
сумма которых равна целевому числу
'''
if len(numbers_list) < 3:
return False
# Цикл по элементам списка
for i in range(len(numbers_list)):
'''Получить очередное число
из списка
'''
x = numbers_list[i]
'''Вычислить новое целевое число
вычитанием
'''
new_goal = goal − x
'''
Проверить наличие в оставшейся части списка
пары чисел, сумма которых
68
Глава 2. Математика
76
77
78
79
80
81
82
83
84
85
равна новому целевому числу
'''
if has_two_sum(numbers_list[i + 1:], new_goal):
return True
'''
Если ничего не найдено,
вернуть False
'''
return False
2.21. Определение совершенной степени
Положительное целое число считается совершенной степенью, если его
можно выразить в виде basepower, где base и power являются целыми числами больше 1. Ваша задача: написать функцию, которая принимает положительное целое число n, и если ей удастся найти basepower = n, то она
возвращает True, иначе она должна возвращать False. Например, для n = 64
существует пара чисел base = 2 и power = 6, т. е. 26 = 64.
В табл. 2.21 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.21. Некоторые ожидаемые результаты
для задачи определения идеальной степени
n
Ожидаемый результат
2
False
27
True
729
True
1369
True
Алгоритм
Чтобы определить, является ли положительное целое число n совершенной степенью, используется алгоритм, выполняющий двоичный поиск
основания совершенной степени. Алгоритм начинается с показателя степени, равного 2, и продолжает перебирать в цикле все возрастающие числа, пока не найдет идеальную степень или не выяснит, что таковой не существует. Вот подробное описание шагов алгоритма.
1. Принимается целое положительное число n.
2. Показателю степени power присваивается значение 2.
3. Запускается цикл while True:.
2.21. Определение совершенной степени 69
4. Если 2 ** power > n, возвращается False.
5. Инициализируются переменные low = 2 и high = n.
6. Пока low меньше или равно high:
1) переменной mid присваивается результат деления (low + high)
на 2 с округлением вниз;
2) переменной guess присваивается значение mid, возведенное
в степень power;
3) если guess равно n, верните True;
4) иначе, если guess меньше n, переменной low присваивается значение mid + 1;
5) иначе переменной high присваивается значение mid – 1.
7. Если base ** power равно n, то возвращается True.
8. Значение power увеличивается на 1.
В листинге 2.21 приводится код на Python, проверяющий, является ли
заданное число совершенной степенью.
Листинг 2.21. Определение совершенной степени
1 def perfect_power(n):
2
'''
3
В языке Python оператор ** выполняет возведение в степень
4
'''
5
power = 2
6
7
while True:
8
if 2 ** power > n:
9
return False
10
11
# Найти наибольшую степень, используя двоичный поиск
12
low = 2
13
high = n
14
while low 0 и числа еще нет в последовательности. (2.7)
a + n else
n −1
В табл. 2.23 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.23. Некоторые ожидаемые результаты для задачи
поиска n‑го члена последовательности Рекамана
n
Ожидаемый результат
17
25
83
72
919
756
632
308
Алгоритм
Чтобы найти n‑й член, алгоритм инициализирует последовательность
ее первым элементом и запоминает в ней все последующие элементы. Затем выполняет итерации по оставшимся элементам до n и для каждого
вычисляет следующий элемент, используя формулу 2.7. Если следующий
элемент отрицательный или уже присутствует в последовательности,
то использует альтернативную формулу для расчета следующего элемента. Затем следующий вычисленный элемент добавляется в последовательность и в множество использованных элементов. Наконец, алгоритм возвращает n‑й элемент последовательности.
В листинге 2.23 приводится код на Python, выполняющий поиск n‑го
члена последовательности Рекамана.
74
Глава 2. Математика
Листинг 2.23. Поиск n‑го члена последовательности Рекамана
1 def Nth_term_of_recaman_sequence(n):
2
'''
3
Возвращает n-й член последовательности Рекамана
4
'''
5
# Инициализировать последовательность первым элементом
6
seq=[0]
7
# Инициализировать множество использовавшихся элементов
8
seen = {0}
9
# Обход остальных элементов до n-го
10
for i in range(1, n + 1):
11
# Получить предыдущий элемент в последовательности
12
prev = seq[−1]
13
'''Вычислить следующий элемент
14
по формуле, как показано ниже
15
'''
16
next = prev − i
17
'''
18
Если следующий элемент отрицательный или уже использовался,
19
то выполнить вычисления по альтернативной формуле
20
'''
21
if next < 0 or next in seen:
22
next = prev + i
23
# Добавить элемент в последовательность
24
seq.append(next)
# Поместить этот элемент в множество использовавшихсяэлементов
25
26
seen.add(next)
27
# Вернуть n-й элемент
28
return seq[−1]
2.24. n‑й член последовательности Ван Эка
Рассмотрим последовательность S, состоящую из положительных целых
чисел. Первый член S равен 0. Есть ли ноль перед текущим нулем? Нет,
поэтому последовательность равна (0, 0). Для последнего числа (в данном случае для второго нуля) задается тот же вопрос: есть ли ноль перед
текущим (вторым) нулем? Да, поэтому последовательность равна (0, 0,
1). И снова для последнего числа (1) задается вопрос: есть ли «единица»
перед текущей единицей? Нет, значит, последовательность равна (0, 0,
1, 0). И снова для последнего числа (0) задается вопрос: есть ли ноль перед текущим нулем? Да, поэтому последовательность равна (0, 0, 1, 0, 2)
2.24. n‑й член последовательности Ван Эка 75
и т. д. Проще говоря, последовательность подсчитывает количество шагов,
необходимых для достижения первого запрошенного числа, если следовать начиная с хвоста последовательности до запрошенного числа, и подсчет прекращается, когда обнаруживается искомое число. Эта популярная
последовательность называется последовательностью Ван Эка. Ее члены
определяются рекурсивно, поскольку каждый следующий член вычисляется на основе предыдущих. Ваша задача: написать функцию, которая
принимает положительное целое число n и возвращает n‑й член последовательности Ван Эка.
В табл. 2.24 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.24. Некоторые ожидаемые результаты
для задачи поиска n‑го члена последовательности Ван Эка
n
Ожидаемый результат
258
3
25
4
2
1
2089
0
Алгоритм
Ниже перечислены шаги, выполняемые алгоритмом поиска n‑го члена
последовательности Ван Эка.
1. Последовательность инициализируется первым членом, равным 0.
2. Создается пустой словарь для хранения каждого значения в последовательности с их индексами.
3. Для каждого индекса от 0 до n – 1:
1) получить предыдущее значение в последовательности seq [i];
2) проверить, встречалось ли предыдущее значение раньше, поиском его в словаре;
3) если встречалось, то вычислить разность между текущим и предыдущим значениями;
4) добавить разность в последовательность;
5) если предыдущее значение не встречалось, добавить в последовательность 0;
6) обновить словарь, указав текущий индекс i для предыдущего
значения.
4. Вернуть n‑й член последовательности, то есть seq [n – 1].
76
Глава 2. Математика
В листинге 2.24 приводится код на Python, выполняющий поиск n‑го
члена последовательности Ван Эка.
Листинг 2.24. Поиск n‑го члена последовательности Ван Эка
"""
Возвращает n-й член
последовательности Ван Эка.
"""
def find_nth_term_in_van_eck_sequence(n):
'''
Инициализировать последовательность
первым членом
'''
sequence = [0]
'''
Создать словарь для хранения
значений членов последовательности с их индексами
'''
value_to_latest_index = {}
for i in range(n):
# Проверить, встречалось ли предыдущее значение раньше
previous_value = sequence[i]
if previous_value in value_to_latest_index:
'''
Если встречалось, то вычислить разность между
текущим индексом и предыдущим
'''
difference = i − \
value_to_latest_index[previous_value]
# Добавить разность в последовательность
sequence.append(difference)
else:
# Если не встречалось, то добавить 0 в последовательность
sequence.append(0)
'''
Обновить индекс текущего
значения в словаре
'''
value_to_latest_index [ previous_value ] = i
# Вернуть последнее значение в последовательности
return sequence[−1]
2.25. Поиск суммы чисел Фибоначчи на основе теоремы Цекендорфа 77
2.25. Поиск суммы чисел Фибоначчи на основе
теоремы Цекендорфа
Согласно теореме Цекендорфа, любое произвольное положительное целое можно выразить как сумму (необязательно последовательных) чисел
Фибоначчи. Напишите функцию, которая принимает положительное целое число n и возвращает список непоследовательных чисел Фибоначчи,
сумма которых равна n. Числа в списке должны следовать в порядке убывания.
В табл. 2.25 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 2.25. Некоторые ожидаемые результаты
для задачи поиска суммы чисел Фибоначчи
n
Ожидаемый результат
53
[34, 13, 5, 1]
25
[21, 3,1]
31
[21, 8, 2]
3009
[2584, 377, 34, 13, 1]
Алгоритм
Алгоритм генерирует последовательность чисел Фибоначчи, сортирует
ее в порядке убывания с использованием алгоритма сортировки вставками и выбирает элементы из отсортированной последовательности, руководствуясь определенными критериями. Ниже перечислены шаги, выполняемые алгоритмом.
1. Принимается целое положительное число n.
2. Инициализируются переменные: previous_fibonacci_number – значением 0, current_fibonacci_number – значением 1, fibonacci_numbers – списком, содержащим previous_fibonacci_number и current_fibonacci_number,
selected_fibonacci_numbers – пустым списком и current_sum – суммой
previous_fibonacci_number + current_fibonacci_number.
3. Используется цикл while, чтобы сгенерировать числа Фибоначчи до n:
1) добавить current_sum в fibonacci_numbers;
2) обновить previous_fibonacci_number значением current_fibonacci_number;
3) обновить current_fibonacci_number значением current_fibonacci_
number + previous_fibonacci_number;
4) обновить current_sum значением previous_fibonacci_number + current_
fibonacci_number;
78
Глава 2. Математика
5) продолжать выполнять цикл, пока current_sum не станет больше n;
6) отсортировать fibonacci_numbers в порядке убывания.
4. Используется цикл for для выбора чисел Фибоначчи, сумма которых
дает в результате n, выполняющий следующие действия:
1) переменная sum_of_fibonacci_numbers инициализируется значением 0;
2) для каждого числа в fibonacci_numbers выполняются следующие
действия:
а) если sum_of_fibonacci_numbers + number меньше или равно n,
то number добавляется в selected_fibonacci_numbers и переменная sum_of_fibonacci_numbers обновляется значением sum_of_
fibonacci_numbers + number;
б) если sum_of_fibonacci_numbers равна n, то возвращается selected_
fibonacci_numbers.
В листинге 2.25 приводится код на Python, выполняющий поиск суммы
чисел Фибоначчи, равной заданному числу n.
Листинг 2.25. Поиск суммы чисел Фибоначчи, равной заданному числу n
1 def sort_desc(arr):
2
for i in range(1, len(arr)):
3
curr = arr[i]
4
j= i − 1
5
while j >= 0 and curr > arr[j]:
6
arr[j + 1] = arr[j]
7
j −= 1
8
arr[j + 1] = curr
9
return arr
10
11 def get_non_consecutive_fibonacci_numbers_summing_to_n(n):
12
prev = 0
13
curr = 1
14
fib_nums = [prev, curr]
15
selected_fib_nums = []
16
curr_sum = prev + curr
17
18
while curr_sum 1:
if n % i == 0:
# Добавить множитель в список primes
if i not in primes:
primes.append(i)
'''Разделить число на множитель,
чтобы получить следущий множитель
'''
n /= i
else:
'''
Если не делится без остатка,
то попробовать следующее число
'''
i += 1
return primes
def can_build_number(arr, n):
"""
Проверяет, можно ли составить число
из элементов заданного списка.
"""
'''
Создать список ways, чтобы
проверить каждое число, меньшее целевого значения
'''
ways = [0] * (n + 1)
# Получить 0 можно только одним способом
ways[0] = 1
# Цикл по всем элементам списка
for i in range(len(arr)):
# Цикл по всем возможным числам, участвующим в сборке
for j in range(arr[i], n + 1):
'''
Прибавить число способов и получить текущее
число с использованием текущего элемента
'''
ways[j] += ways[j − arr[i]]
'''
Если есть хотя бы один способ сформировать
2.28. Проверка сбалансированности центрифуги 87
50
51
52
53
54
55
56
57
58
59
целевое число, то вернуть True
'''
return ways[n] != 0
# Получить список простых множителей для n
primes = get_primes(n)
# Проверить возможность балансировки
# с использованием списка простых множителей
return can_build_number(primes, k ) \
and can_build_number(primes, n − k)
Глава
3
Числа
В этой главе рассматривается 21 задача с сопровождением примерами решения на Python. Вот список задач:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
Проверка, является ли число числом Циклопа.
Проверка наличия цикла домино в списке чисел.
Извлечение возрастающих чисел из заданной строки.
Развертывание целочисленных интервалов.
Свертывание целочисленных интервалов.
Проверка левостороннего и правостороннего игрального кубика.
Очки за повторяющиеся числа.
Первое меньшее число.
Первый объект, предшествующий k меньшим объектам.
Поиск n‑го члена последовательности Калкина–Уилфа.
Поиск и обращение восходящих подмассивов.
Наименьшие целые степени.
Сортировка циклов в графе.
Получение представления числа в сбалансированной троичной системе.
Строгое возрастание.
Сортировка по приоритетам.
Сортировка положительных чисел с сохранением порядка отрицательных чисел.
Сортировка: сначала числа, потом символы.
Сортировка дат.
Сортировка по алфавиту и длине.
Сортировка чисел по количеству цифр.
3.1. Число Циклопа 89
3.1. Число Циклопа
Неотрицательное целое число называется числом Циклопа, если оно удовлетворяет следующим условиям: количество цифр нечетно, средняя цифра (также известная как «глаз») равна нулю, а все остальные цифры отличны от нуля. Ваша задача: написать функцию, проверяющую, является ли
заданное неотрицательное целое число числом Циклопа. Функция должна
принимать неотрицательное целое число и проверить, удовлетворяет ли
оно вышеперечисленным условиям. Если входное целое число является
числом Циклопа, то функция должна вернуть значение True, иначе она
должна вернуть False.
В табл. 3.1 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.1. Некоторые ожидаемые результаты
для задачи проверки числа Циклопа
n
Ожидаемый результат
11000
False
709
True
11318
False
6022
False
Алгоритм
Чтобы проверить, является ли заданное число числом Циклопа, алгоритм выполняет следующие шаги.
1. Принимается целое число n.
2. Число n преобразуется в строку цифр и сохраняется в переменной
digits.
3. Проверяется, четна ли длина строки digits. Если да, то возвращается
False, потому что число Циклопа должно иметь нечетное количество
цифр.
4. Выбирается цифра в середине, индекс которой определяется делением длины digits на 2 c использованием целочисленного деления
(//), и сохраняется в переменной middle_number.
5. Проверяется, равна ли цифра с индексом middle_number нулю (0). Если
нет, то возвращается False, потому что число Циклопа должно иметь
0 в середине.
6. Подсчитывается количество нулей в digits и результат сохраняется
в переменной count. Если число больше 1, возвращается False, пото-
90
Глава 3. Числа
му что число Циклопа может иметь только один ноль (0). Иначе возвращается True, потому что входное значение n удовлетворяет всем
условиям числа Циклопа.
В листинге 3.1 приводится код на Python, выполняющий проверку числа
Циклопа.
Листинг 3.1. Проверка числа Циклопа
3.2. Цикл домино
Костяшку домино можно представить кортежем (x, y), где x и y – положительные целые числа. Цель этой задачи – определить, имеется ли цикл домино в заданном наборе костяшек. Например, в наборе [(5, 2), (2, 3), (3, 4),
(4, 5)] имеется цикл домино. Первая костяшка (5, 2) связана с (2, 3); 2 → 2.
Костяшка (2, 3) связана с (3, 4); 3 → 3. Так же связаны остальные костяшки:
4 → 4, 5 → 5. Ваша задача: написать функцию, которая принимает список
костяшек домино и возвращает True, если в последовательности есть цикл,
иначе возвращает False.
В табл. 3.2 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.2. Некоторые ожидаемые результаты для задачи проверки цикла домино
Tiles
Алгоритм
Алгоритм должен проверить равенство компонентов y и x двух сравниваемых кортежей на каждом шаге. Если они не равны, он должен вернуть
False, иначе он должен вернуть True.
В листинге 3.2 приводится код на Python, выполняющий проверку цикла
домино.
Листинг 3.2. Проверка цикла домино
1 def Is_a_domino_cycle(tiles):
2
index = 0
3
while index < len(tiles):
4
# Проверить условия
5
if tiles[index][0] != tiles[(index - 1) % len(tiles)][1]:
6
'''
7
Если хотя бы одно условие не выполняется,
8
то вернуть False.
9
'''
10
return False
11
index += 1
12
return True
3.3. Извлечение возрастающих чисел
В этой задаче дается строка цифр и гарантируется, что в строке присутствуют только цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Требуется разбить строку на последовательность возрастающих чисел. Например, число 457990 можно
представить в виде последовательности возрастающих чисел 4, 5, 7, 9 и 90.
Ваша задача: написать функцию, которая принимает строку из цифр
и возвращает список возрастающих чисел.
В табл. 3.3 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.3. Некоторые ожидаемые результаты
для задачи извлечения возрастающих чисел
Digits
Ожидаемый результат
'457990'
[4, 5, 7, 9, 90]
'1'
[1]
'13900456'
[1, 3, 9, 45]
27811700
[2, 7, 8, 11, 70]
92
Глава 3. Числа
Алгоритм
Алгоритм состоит из двух блоков проверки возрастающих чисел. Сначала определяется пустая строка concatnumbers и переменная b со значением 1. Если b = 1, выполняется вход в первый блок, а если b = 0, выполняется вход во второй блок. Для каждой цифры в данной строке в первом
блоке производится линейный поиск, пока следующее число больше предыдущего и b = 1, и каждое следующее такое число добавляется в массив
storage, после чего оно становится предыдущим числом. Во втором блоке,
если условия входа в первый блок не выполняются, переменной b присваивается 0, затем текущее число объединяется со следующей цифрой
и помещается в concatnumbers. Если значение concatnumbers больше предыдущего числа, то оно сохраняется в storage и переменной concatnumbers
присваивается пустая строка. Пока объединение следующих цифр меньше или равно предыдущему числу, объединение повторяется для следующих цифр. Когда b = 0, алгоритм ни за что не сможет войти в первый блок,
поскольку ни одна цифра не будет больше предыдущих чисел и входить
в первый блок бессмысленно.
В листинге 3.3 приводится код на Python, выполняющий извлечение
возрастающих чисел.
Листинг 3.3. Извлечение возрастающих чисел
1 def extract_increasing_digits(digits):
2
number=[]
3
concatnumbers = ''
4
for x in str(digits):
5
number.append(int(x))
6
# Предыдущее число
7
prev = number[0]
8
storage = []
9
# Пока есть только одна цифра
10
storage = [number[0]]
11
number = number[1:]
12
b=1
13
for next_ in number:
14
'''
15
Этот блок извлекает возрастающие цифры,
16
т. е. числа из одной цифры,
17
такие как 2,3,4
18
'''
19
if next_ > prev and b == 1:
20
storage.append(next_)
21
prev = next_
else:
'''
Этот блок извлекает возрастающие числа,
состоящие из нескольких цифр,
такие как 90, 990, 9990
'''
b = 0
concatnumbers += str(next_)
if int(concatnumbers) > prev:
storage.append(int(concatnumbers))
prev = int(concatnumbers)
'''
Очистить строку concatnumbers, чтобы подготовить ее
для сборки следующего числа из цифр,
которое больше текущего
'''
concatnumbers = ''
return storage
3.4. Развертывание целочисленных интервалов
Диапазон последовательных положительных целых чисел можно представить как строку, включающую первое и последнее значения, разделенные дефисом (-). Вот пример допустимого интервала: «1,17–21,43,44».
Ваша задача: написать функцию, которая развертывает подобные интервалы в списки отдельных чисел. Функция должна принимать строку
с числами и возвращать список чисел, разделенных запятыми.
Важное условие: числа во входной строке гарантированно располагаются в порядке возрастания.
В табл. 3.4 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.4. Некоторые ожидаемые результаты для задачи развертывания
целочисленных интервалов
Intervals
Алгоритм
Сначала алгоритм должен разбить строку по символу запятой (,). Затем
отделить отдельные числа от интервалов. Отдельные числа сохраняются в списке, а интервалы развертываются с помощью цикла for, который
выполняет перебор от начала до конца интервала и включает в выходной
список каждое следующее число. Вот подробное описание шагов алгоритма.
1. Принимается строка intervals с интервалами.
2. Если строка intervals пустая, то возвращается пустой список.
3. Создается пустой список с именем result для хранения чисел, получающихся после развертывания интервалов.
4. Входная строка разбивается на отдельные интервалы по запятым
(,), которые сохраняются в списке intervals_list.
5. Для каждого интервала в списке intervals_list проверяется, содержит ли он одно число (точнее, отсутствие дефиса «-»). Если интервал –
это одно число, то он преобразуется в целое число с помощью int ()
и добавляется в список result.
6. Если интервал содержит диапазон чисел (т. е. присутствует дефис
«-»), то он разбивается на отдельные элементы по дефису, после чего
элементы преобразуются в числа start и end с помощью int ().
7. Генерируются числа между start и end с помощью функции range ()
и добавляются в список result посредством метода extend ().
8. После обработки всех интервалов возвращается окончательный
список result, содержащий все развернутые интервалы.
В листинге 3.4 приводится код на Python, выполняющий развертывание
целочисленных интервалов.
Листинг 3.4. Развертывание целочисленных интервалов
1 def Expanding_Integer_Intervals(intervals):
2
'''
3
Если входная строка пустая,
4
то вернуть пустой список
5
'''
6
if intervals == '':
7
return []
8
'''
9
создать пустой список для хранения
10
развернутых интервалов
'''
result = []
'''
разбить входную строку
на интервалы
'''
intervals_list = intervals.split(',')
for interval in intervals_list:
'''
Проверить, содержит ли интервал
только одно число
'''
if '-' not in interval:
'''
преобразовать его в целое число
и добавить в список result
'''
result.append(int(interval))
else:
# Если интервал содержит диапазон чисел,
# то извлечь начало и конец диапазона
start_end = interval.split('-')
start = int(start_end[0])
end = int(start_end[1])
'''
сгенерировать все числа между start
и end и добавить их в список result
'''
'''
range(x,y)---range(x,y-1),
поэтому (x,y+1), чтобы не упустить последний элемент
'''
result.extend(range(start , end + 1))
'''
Вернуть получившийся список
с развернутыми интервалами
'''
return result
96
Глава 3. Числа
3.5. Свертывание целочисленных интервалов
Эта задача является обратной к предыдущей задаче. Напишите функцию,
которая принимает список чисел и возвращает строку интервалов в форме
«первый–последний», разделенных запятыми.
В табл. 3.5 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.5. Некоторые ожидаемые результаты для задачи свертывания
целочисленных интервалов
Items
Алгоритм
Алгоритм решения этой задачи основан на правилах. Фактически он перебирает список целых чисел и определяет диапазоны последовательных
целых чисел.
1. Принимается список положительных целых чисел.
2. Инициализируются переменные start и end значением None.
3. Для каждого целочисленного элемента item во входном списке items
выполняются следующие действия:
а) если start имеет значение None, то обеим переменным, start и end,
присваивается значение item;
б) если item равен end + 1, то переменной end присваивается значение item;
в) иначе текущий получившийся диапазон добавляется в список
ranges, причем если значение start равно значению end, то добавляется str (start), иначе добавляется str (start) + '.' + str (end);
г) затем начинается свертывание нового диапазона, для чего обеим переменным, start и end, присваивается значение item.
4. Если переменная start имеет значение, отличное от None, то заключительный диапазон добавляется в ranges с использованием той же
логики, что и на предыдущем шаге.
5. Диапазоны объединяются через запятую, и полученная строка возвращается.
3.6. Левосторонний игральный кубик 97
В листинге 3.5 приводится код на Python, выполняющий свертывание
целочисленных интервалов.
Листинг 3.5. Свертывание целочисленных интервалов
1 def collapse_integer_intervals(items):
2
ranges = []
3
start = end = None
4
5
for item in items :
6
if start is None:
7
# Инициализировать новый диапазон
8
start = end = item
9
elif item == end + 1:
10
# Продолжить текущий диапазон
11
end = item
12
else:
13
# Добавить текущий диапазон в список
14
if start == end:
15
ranges.append(str(start))
16
else:
17
ranges.append(str(start) + '-' + str(end))
18
19
# Инициализировать новый диапазон
20
start = end = item
21
22
# Добавить последний диапазон в список
23
if start is not None:
24
if start == end:
25
ranges.append(str(start))
26
else:
27
ranges.append(str(start) + '-' + str(end))
28
29
# Объединить диапазоны в строку через запятую
30
return " ,".join(ranges)
3.6. Левосторонний игральный кубик
Рассмотрим игральные кубики, имеющие шесть граней с точками от одной до шести и восемь углов, причем если смотреть с каждого угла,
то видны три грани. Левосторонние и правосторонние кубики выглядят
по-разному. Например, на рис. 3.1 (б) изображен левосторонний кубик,
а на рис. 3.1 (а) – правосторонний. Чтение видимых граней производится слева направо (по часовой стрелке). Для левостороннего кубика числа
98
Глава 3. Числа
читаются как 1, 2, 3. Если повернуть левосторонний кубик против часовой
стрелки, то, следуя тому же правилу, мы прочитаем 2, 3, 1, если повернуть
еще раз, то 3, 1, 2. Следовательно, при взгляде на угол левостороннего
кубика, объединяющий грани 1, 2, 3, мы имеем три перестановки 1, 2, 3;
2, 3, 1 и 3, 1, 2. Кубик имеет восемь разных углов, и для каждого возможны
три перестановки, поэтому общее число перестановок равно 8 × 3 = 24.
То же верно и для правостороннего кубика. Всего имеется 24 + 24 = 48 перестановок для левостороннего и правостороннего кубиков вместе. Ваша
задача: написать функцию на Python, которая принимает угол и определяет, является кубик левосторонним или правосторонним. Если кубик левосторонний, то функция должна вернуть True, в противном случае – False.
(а) Правосторонний
(б) Левосторонний
Рис. 3.1. Примеры прово‑и левосторонних кубиков
В табл. 3.6 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.6. Некоторые ожидаемые результаты для задачи
определения типа кубика, лево‑ или правостороннего
n
Ожидаемый результат
(4, 2, 1)
True
(6, 3, 2)
True
(6, 5, 4)
False
3.7. Очки за повторяющиеся числа 99
Алгоритм
Количество перестановок чисел в левостороннем (и правостороннем)
кубике невелико, достаточно найти 24 левосторонних угла, и если входные данные совпадают с рассматриваемым углом, то следует вернуть True,
в противном случае – False.
В листинге 3.6 приводится код на Python, проверяющий, является ли кубик левосторонним.
Листинг 3.6. Проверка, является ли кубик левосторонним
3.7. Очки за повторяющиеся числа
Представьте, что вы идете по улице и встречаете два такси. Одно с номером 1729, другое с номером 6666. Очевидно, что число 6666 легче запомнить благодаря повторению цифр в последовательности. Человеческий
разум легче запоминает числа с повторяющимися цифрами. Например,
люди проще запоминают показания часов 12:12, чем показания, не имеющие повторяющихся цифр, например 10:23. Целью этого задания является привлечение внимания к последовательности чисел, в которых есть
повторяющиеся цифры. Последовательности оцениваются по количеству
повторяющихся цифр. Если в последовательности есть две повторяющие
ся цифры, то ей выставляется оценка 1. Если в последовательности три
повторяющиеся цифры, то она получает оценку 10. Если в последовательности четыре повторяющиеся цифры, то ей начисляется 100 очков и т. д.
Более того, если последовательность заканчивается последовательностью повторяющихся цифр, то полученное количество очков удваивается. Например, число 12333 имеет повторяющиеся цифры и заканчивает-
100
Глава 3. Числа
ся последовательностью повторяющихся цифр. Его оценка вычисляется
по формуле 3.1.
Есть последовательность повторяющихся цифр
10k − z
score =
k−z
Число заканчивается последовательностью . (3.1)
2 × 10
повторяющихся цифр
Напишите функцию, которая принимает положительное целое число n,
и если оно содержит последовательность повторяющихся цифр, то за каж
дую такую последовательность число получает 10 (k–2) очков, а если n заканчивается последовательностью повторяющихся цифр, то оценка за эту
последовательность умножается на 2, т. е. 2 × 10 (k–2).
В табл. 3.7 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.7. Некоторые ожидаемые результаты для задачи
начисления очков за последовательности повторяющихся цифр в числе
n
Ожидаемый результат
1233
2
1569
0
17777
200
588885515555
301
Алгоритм
Алгоритм принимает целое число, перебирает цифры во входном числе
и проверяет, совпадает ли текущая цифра с предыдущей цифрой. Если совпадает, то алгоритм увеличивает счетчик на количество повторяющихся
цифр. Если отличается, то алгоритм подсчитывает количество повторяющихся цифр на данный момент и сбрасывает счетчик для новой цифры.
Наконец, алгоритм подсчитывает все оставшиеся повторяющиеся цифры
в конце числа.
Вот подробное описание шагов алгоритма.
1.
2.
3.
4.
5.
Принимается целое число n.
Переменная score инициализируется нулем.
Переменная count инициализируется единицей.
Переменная prev_digit инициализируется значением None.
Число n преобразуется в строку, и выполняется перебор цифр:
3.7. Очки за повторяющиеся числа 101
а) если текущая цифра совпадает с предыдущей (prev_digit), то увеличивается переменная count;
б) если текущая цифра отличается от предыдущей цифры, то:
в) если count больше 1, то переменная score увеличивается
на 10 (count–2). Получается оценка, основанная на количестве повторяющихся цифр;
г) переменной count присваивается 1 для новой цифры;
д) переменной prev_digit присваивается текущая цифра для проверки наличия повторяющейся последовательности.
6. Если повторяющиеся цифры последние в числе, то к оценке score
прибавляется 2×10 (count – 2). Это дает дополнительные очки за повторяющиеся цифры.
7. Полученная оценка возвращается.
В листинге 3.7 приводится код на Python, вычисляющий оценку за повторяющиеся числа.
Листинг 3.7. Оценка за повторяющиеся числа
1 def duplicate_digit_score(n):
2
score = 0
3
# Инициализировать prev_digit значением None
4
count = 1
5
prev_digit = None
6
7
'''
8
обход цифр в
9
числе n
10
'''
11
for digit in str(n):
12
'''
13
Сравнить текущую цифру
14
с предыдущей
15
'''
16
if prev_digit == digit:
17
# Увеличить счетчик повторяющихся цифр
18
count += 1
19
else:
20
'''
21
если предыдущая цифра повторялась несколько раз,
22
то вычислить оценку
23
'''
if count > 1:
# Вычислить оценку за повторяющиеся цифры
score += 10 ** (count − 2)
# Сбросить счетчик для новой цифры
count = 1
'''
Обновить prev_digit
для следующей итерации
'''
prev_digit = digit
'''
Вычислить оценку для повторяющихся цифр
в конце числа
'''
if count > 1:
'''
Удвоить оценку
за повторяющиеся цифры в конце
'''
score += 2 * 10 ** (count − 2)
return score
3.8. Первое меньшее число
Пусть есть массив, заполненный положительными целыми числами.
В этой задаче вы должны для каждого числа найти первое меньшее число
в массиве, и если меньшего числа нет, то число должно остаться неизменным. Например, рассмотрим массив array = [2, 77, 13, 1]. Первое число равно 2, и слева от него нет никакого другого числа, поэтому рассматривается часть массива справа. Справа есть число 1, которое меньше 2, поэтому
[2, 77, 13, 1] → [1]. Следующее число равно 77. Слева от него имеется число 2, а справа – число 1. Число 1 меньше, но 2 – это первое меньшее число,
поэтому [2, 77, 13, 1] → [1, 2]. Следующее число – 13, и первое меньшее
число – 1, поэтому [2, 77, 13, 1] → [1, 2, 1]. Следующее число – 1. Меньше его
нет чисел в массиве, поэтому оно перекочевывает в результат: [1, 2, 1, 1].
Ваша задача: написать функцию, которая принимает массив положительных целых чисел и возвращает массив чисел, каждый элемент которого является первым числом, меньше соответствующего числа во входном
массиве.
В табл. 3.8 показаны ожидаемые результаты для некоторых входных
данных.
3.8. Первое меньшее число 103
Таблица 3.8. Некоторые ожидаемые результаты для задачи
выбора первых меньших чисел
Array
Ожидаемый результат
[8, 6, 16, 1921, 17]
[6, 6, 6, 16, 16]
[2, 3, 4, 871]
[2, 2, 3, 4]
[1,77,7, 770, 700, 11]
[1, 1, 1, 7, 11, 7]
[6, 8, 9, 888, 1401, 1402]
[6, 6, 8, 9, 888, 1401]
Алгоритм
В алгоритме предусмотрены вложенные циклы, перебирающие все элементы входного массива и окружающих его элементов. Алгоритм находит
первый меньший элемент для каждого элемента входного массива, сравнивая элемент из входного массива с соседними элементами слева и справа от него. Если любой из элементов слева или справа меньше текущего,
то он выбирается как первый меньший элемент. Алгоритм также обрабатывает случаи, когда для текущего элемента в массиве нет меньшего элемента.
В листинге 3.8 приводится код на Python, отыскивающий первые меньшие числа.
Листинг 3.8. Поиск первых меньших чисел
1 def Nearest_first_smaller_number(array):
2
n = len(array)
3
nearest_smaller = []
4
5
# Цикл по элементам входного массива
6
for x, current_element in enumerate(array):
7
8
'''
9
Цикл по элементам
10
слева и справа от текущего
11
'''
12
for y in range(1, n):
13
14
'''
15
Получить элемент слева
16
от текущего (или выбрать
17
текущий элемент, если слева нет элементов)
104
Глава 3. Числа
18
'''
19
if x >= y:
20
left = array[x − y]
21
22
else:
23
left = current_element
24
25
'''
26
Получить элемент справа
27
от текущего (или выбрать
28
текущий элемент, если справа нет элементов)
29
'''
30
31
if x + y < n:
32
right = array[x + y]
33
else:
34
current_element
35
36
'''
37
Если слева или справа есть элемент,
38
который меньше текущего,
39
то добавить его
40
в список nearest_smaller
41
'''
42
if left < current_element \
43
or right < current_element:
44
nearest_smaller.append \
45
(left if left < right else right)
46
break
47
48
'''
49
Если нет элементов слева
50
или справа меньше текущего,
51
то добавить текущий элемент
52
в список nearest_smaller
53
'''
54
else :
55
nearest_smaller.append(current_element)
56
57 return nearest_smaller
3.9. Первый объект, предшествующий k меньшим объектам 105
3.9. Первый объект, предшествующий
k меньшим объектам
В этой задаче дается список объектов, и вы должны найти и вернуть объект, которому предшествует как минимум k меньших объектов. Если такого элемента нет, то функция должна вернуть значение None. Например,
рассмотрим items = [2, 1, 9, 14] и k = 2. Какому числу предшествуют как
минимум k меньших чисел? Так как числу 9 предшествуют числа 1 и 2,
то 9 является ответом. Если items = [4, 2, 1, 9, 14] и k = 2, то ответ снова равен 9, поскольку по условию задачи искомому числу должно предшествовать не меньше k меньших чисел. В качестве другого примера рассмотрим
массив строк: items = [«cobol», «ruby», «c++», «python», «c++», «php»] и k = 2.
Какой строке предшествуют хотя бы k меньших строк? Для начала нужно
определить длины строк, а затем выполнить те же операции, что и в предыдущем примере. Ответом на вопрос во втором примере будет строка
«python», так как ее длина равна шести и перед ней стоят более короткие
строки «c++», «cobol» и «ruby».
В табл. 3.9 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.9. Некоторые ожидаемые результаты для задачи поиска
первого объекта, предшествующего k меньшим объектам
Items, k
Ожидаемый результат
[4,2, 1, 9, 14], 3
9
[2, 3, 4, 871], 4
None
[700, 3, 900, 400, 1100], 2
900
['cobol','ruby','c++','python','c','php'], 2
'python'
Алгоритм
Алгоритм просматривает каждый элемент в списке items и проверяет,
имеются ли перед ним хотя бы k меньших элементов. Для этого алгоритм
создает подсписок всех элементов перед текущим элементом, которые
меньше его. Это делается с использованием генератора списков. После
создания подсписка его длина сравнивается с k. Если длина больше или
равна k, то алгоритм возвращает текущий элемент как первый в списке,
которому предшествует не менее k меньших элементов. Если такого элемента не существует, то алгоритм возвращает None.
В листинге 3.9 приводится код на Python, отыскивающий первый объект, которому предшествует не менее k меньших объектов.
106
Глава 3. Числа
Листинг 3.9. Поиск первого объекта, которому предшествует не менее k меньших
объектов
1 def first_preceded_by_k_smaller_number(items, k=1):
2
'''
3
Цикл по элементам в списке items
4
и их индексам.
5
'''
6
for i, current_number in enumerate(items):
7
8
'''
9
Создать список элементов слева от текущего,
10
которые меньше его.
11
'''
12
smaller_numbers = \
13
[n for n in items[:i] if n < current_number]
14
15
'''
16
Если имеется не меньше k меньших элементов,
17
предшествующих текущему, то вернуть текущий элемент.
18
'''
19
if len(smaller_numbers) >= k:
20
return current_number
21
22
'''
23
Если нет элемента, удовлетворяющего
24
условиям, то вернуть None.
25
'''
26
return None
3.10. Поиск n‑го члена последовательности
Калкина–Уилфа
Дерево Калкина–Уилфа – это корневое двоичное дерево, вершины которого находятся во взаимно однозначном соответствии с положительными
рациональными числами. Корню дерева соответствует число 1, и для любого рационального числа a/b его левый дочерний элемент соответствует
числу a/(a+b), а правый дочерний элемент – числу (a+b)/b. Каждое рациональное число встречается в дереве ровно один раз. При выполнении обхода дерева Калкина–Уилфа по уровням генерируется последовательность
рациональных чисел, известная как последовательность Калкина–Уилфа.
Ваша задача: определить функцию, которая принимает положительное
3.10. Поиск n‑го члена последовательности Калкина–Уилфа 107
целое число n и возвращает n‑й член последовательности Калкина–Уил
фа, который является рациональным числом. Рассмотрим следующий
пример. Если n = 10, то результатом функции должно быть число. Процесс
поиска ответа описан ниже.
В табл. 3.10 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.10. Некоторые ожидаемые результаты для задачи
поиска первого объекта, предшествующего k меньшим объектам
n
Ожидаемый результат
11
5/2
2022
32/45
1993
59/43
24
2/7
10
3/5
Алгоритм
Для решения задачи используется поиск в ширину (Breadth-First Search,
BFS) – алгоритм обхода графа, генерирующий последовательность Калкина–Уилфа до n‑го члена. Для хранения узлов последовательности используется структура данных, называемая очередью. Алгоритм генерирует каждый член последовательности, вычисляя левые и правые дочерние
узлы текущего узла и добавляя их в очередь. В конце возвращается n‑й
член последовательности. Вот подробное описание шагов алгоритма.
1.
2.
3.
4.
5.
Принимается целое положительное число n.
Значение n уменьшается на 1.
Создается пустая очередь queue.
В очередь добавляется корневой узел (1, 1).
Затем запускается цикл, выполняющий следующие шаги n раз:
а) из очереди извлекается следующий узел, и его числитель и знаменатель присваиваются переменным parent_num и parent_denom
соответственно;
б) вычисляется левый дочерний элемент текущего узла установкой
его числителя равным parent_num, а знаменателя – равным parent_
num + parent_denom;
в) вычисляется правый дочерний элемент текущего узла установкой его числителя равным parent_num + parent_denom, а знаменателя – равным parent_num;
108
Глава 3. Числа
г) левый и правый дочерние узлы добавляются в очередь queue.
6. Из очереди извлекается последний элемент, и его числитель и знаменатель присваиваются переменным final_num и final_denom соответст
венно.
7. Если знаменатель последнего узла равен 1, то возвращается его числитель как целое число.
В листинге 3.10 приводится код на Python, отыскивающий n‑й член последовательности Калкина–Уилфа.
Листинг 3.10. Поиск n‑го члена последовательности Калкина–Уилфа
1 def nth_term_calkin_wilf(n):
2
# Функция, проверяющая отсутствие элементов в очереди
3
def is_empty(q):
4
return len(q) == 0
5
6
# Функция, добавляющая элемент в очередь
7
def enqueue(q, item):
8
q.append(item)
9
return q
10
11
# Функция, извлекающая элемент из очереди
12
def dequeue(q):
13
if not is_empty(q):
14
return q.pop(0)
15
16
'''
17
Создать очередь с корневым узлом
18
(1/1) и уменьшить n на 1
19
'''
20
n −= 1
21
queue = []
22
queue = enqueue(queue, (1 , 1))
23
24
'''
25
Цикл генерирования последовательности Калкина–Уилфа
26
до n-го члена с использованием алгоритма BFS
27
'''
28
for _ in range(n):
29
# Извлечь следующий узел из очереди
3.11. Поиск и обращение восходящих подмассивов 109
parent_num, parent_denom = dequeue(queue)
'''
Вычислить левый и правый
дочерние узлы
'''
left_child_num = parent_num
left_child_denom = parent_num + parent_denom
right_child_num = parent_num + parent_denom
right_child_denom = parent_denom
'''
Добавить в очередь левый и правый
дочерние элементы
'''
queue = enqueue\
(queue, (left_child_num, left_child_denom))
queue = enqueue\
(queue, (right_child_num, right_child_denom))
# Извлечь из очереди последний элемент
final_num, final_denom = dequeue(queue)
# Вернуть n-й член последовательности Калкина-Уилфа
if final_denom == 1:
return final_num
else:
return str(final_num) + '/' + str(final_denom)
3.11. Поиск и обращение восходящих
подмассивов
В этой задаче дается массив положительных целых чисел и требуется найти обратные возрастающие подмассивы. Каждый подсписок должен содержать только строго увеличивающиеся элементы. Например, для входного
массива [5, 7, 220, 33, 2, 6, 8, 1, 45] на первом этапе образуются подмассивы:
[5, 7, 220], [33], [2, 6, 8], [1, 45], а на следующем этапе содержимое подмассивов переворачивается в обратном порядке: [220, 7, 5], [33], [8, 6, 2], [45, 1].
Затем перевернутые подмассивы объединяются в исходном порядке. Следовательно, [5, 7, 220, 33, 2, 6, 8, 1, 45] → [220, 7, 5, 33, 8, 6, 2, 45, 1].
В табл. 3.11 показаны ожидаемые результаты для некоторых входных
данных.
110
Глава 3. Числа
Таблица 3.11. Некоторые ожидаемые результаты для задачи обращения
восходящих подмассивов
Arrays
Ожидаемый результат
[6, 3, 2]
[6, 3, 2]
[5, 7, 220, 33, 2, 6, 8, 1, 45]
[220, 7, 5, 33, 8, 6, 2, 45, 1]
[1, 5, 7, 9, 90, 13, 11, 23]
[90, 9, 7, 5, 1, 13, 23, 11]
[44, 33, 57, 36, 38, 900]
[44, 57, 33, 900, 38, 36]
Алгоритм
В алгоритме используется метод двух указателей, где указатель i указывает на начало подсписка, а указатель j используется для поиска конца
восходящего подсписка. Отыскав восходящий подмассив, программа «вырезает» подмассив, располагает элементы подсписка в обратном порядке и добавляет его в итоговый список. Затем она передвигает указатель i
в начало следующего подмассива, и процесс повторяется до тех пор, пока
не будет достигнут конец списка.
В листинге 3.11 приводится код на Python, обращающий восходящие
подмассивы.
Листинг 3.11. Поиск и обращение восходящих подмассивов
1 def reverse_ascending_subarrays(List_Numbers):
2
'''
3
Создать пустой список для хранения
4
восходящих подсписков
5
'''
6
ascending_subarray = []
7
# Установить начальный индекс в 0
8
i=0
9
# Цикл по списку
10
while i < len(List_Numbers):
11
# Установить j в текущий индекс
12
j = i
13
# Извлечь восходящий подмассив
14
while j < len(List_Numbers) − 1 \
15
and List_Numbers[j] < List_Numbers[j + 1]:
16
j += 1
17
'''
18
Обратить и добавить подсписок
19
в список с результатом
20
'''
3.12. Наименьшие целые степени 111
21
22
23
24
25
ascending_subarray.extend\
(List_Numbers[i:j + 1][::−1])
# Установить начальный индекс в начало следующего подмассива
i = j + 1
return ascending_subarray
3.12. Наименьшие целые степени
Большие целые степени могут усложнить вычисления с точки зрения
времени и потребляемого объема памяти. Цель этой задачи: найти наименьшие положительные целые числа x и y, такие, что ax и by находятся
в пределах определенного допуска друг друга. В данном контексте под
«допуском» понимается максимально допустимая разность между двумя
целочисленными степенями a и b. Ваша задача: написать функцию, которая принимает a, b и tolerance и возвращает наименьшие положительные
целые числа x и y.
В табл. 3.12 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.12. Некоторые ожидаемые результаты
для поиска наименьших целых степеней
a, b, tolerance
Ожидаемый результат
12, 16, 10
(19, 17)
32, 40, 99
(248, 233)
43, 33, 73
(66, 71)
Алгоритм
Для решения этой задачи мы используем «жадный» подход. Алгоритм
пытается найти наименьшую пару положительных целых чисел x и y, соответствующих заданному допуску. Для этого он последовательно увеличивает значения x и y, пока разность между степенями ax и bx не станет
меньше или равна заданному допуску. Этот не гарантирует получение оптимального решения, но находит достаточно хорошее решение за разумное время.
1. Принимаются целые числа a и b.
2. Переменным x и y присваивается 1.
3. Переменным a_pow и b_pow присваиваются значения a и b соответственно.
4. Запускается бесконечный цикл:
112
Глава 3. Числа
а) если a_pow больше, чем b_pow, то допуск tolerance сравнивается
с результатом деления b_pow на разность между a_pow и b_pow;
б) если допуск меньше, то возвращаются x и y;
в) иначе y увеличивается на 1 и b_pow умножается на b;
г) если a_pow меньше, чем b_pow, то допуск tolerance сравнивается
с результатом деления a_pow на разность между b_pow и a_pow;
д) если допуск меньше, то возвращаются x и y;
е) в противном случае x увеличивается на 1 и a_pow умножается на a;
ж) если a_pow и b_pow равны, то возвращаются x и y.
В листинге 3.12 приводится код на Python, отыскивающий наименьшие
целые степени.
Листинг 3.12. Поиск наименьших целых степеней
1 def smallest_integer_powers(a, b, tolerance=100):
2
x, y = 1, 1
3
a_pow, b_pow = a, b
4
5
while True:
6
if a_pow > b_pow:
7
if tolerance array[j + 1]:
13
array[j], array[j + 1] = \
14
array[j + 1], array[j]
15
flag = False
16
if flag:
17
return array
18
# Словарь для хранения отрицательных элементов
19
neg = {}
20
for i in range(len(array)):
21
# если текущий элемент отрицательный
22
if array[i] < 0:
23
'''
24
добавить индекс:значение в
25
словарьneg
26
'''
27
neg[i] = array[i]
28
# Временно удалить отрицательные элементы
29
array = [i for i in array if i >= 0]
30
# Отсортировать положительные числа
31
array = bubblesort(array)
32
# Цикл по словарю
33
for i, v in neg.items():
34
'''
35
Вставить отрицательные числа
36
в соответствующие индексы
37
'''
38
array.insert(i , v)
39
return array
124
Глава 3. Числа
3.18. Сортировка: сначала числа, потом
символы
В этом задании дается список списков. Структура исходного списка должна сохраняться, но содержимое вложенных списков должно быть отсортировано так, чтобы первыми следовали числа, а затем символы. И числа,
и символы должны сортироваться в порядке возрастания.
Ваша задача: написать функцию, которая принимает список списков,
состоящих из чисел и символов, и возвращает список с той же структурой,
но сортирует содержимое вложенных списков так, что сначала следуют
числа, а затем символы – и те, и другие в порядке возрастания.
В табл. 3.18 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.18. Некоторые ожидаемые результаты для задачи сортировки чисел
и символов
NestedList
Алгоритм
Алгоритм сначала объединяет вложенные списки в один плоский список, затем отделяет числа от символов, сортирует числа и символы с помощью пузырьковой сортировки и, наконец, объединяет их обратно в отсортированный список списков с исходной структурой.
В листинге 3.18 приводится код на Python, сортирующий числа и символы.
Листинг 3.18. Сортировка чисел и символов
1 def number_then_character(NestedList):
2
# Функция, реализующая пузырьковую сортировку
3
def bubblesort(lst):
4
for i in range(len(lst)):
5
flag = True
6
# Цикл по элементам массива
7
for j in range(len(lst) - i - 1):
8
if lst[j] > lst[j + 1]:
'''
Сравнить два соседних числа
и поменять их местами при необходимости
'''
lst[j], lst[j + 1] = lst[j + 1], lst[j]
flag = False
if flag:
# Если перестановка не выполнялась, значит, список отсортирован
return lst
# Объединить вложенные списки в один плоский список
flattedlist = [i for lst in NestedList for i in lst]
# Сохранить размеры списков
sizes = []
# Выполнить обход коллекции и сохранить размеры
for lst in NestedList:
sizes.append(len(lst))
# числа: Извлечь числа (int/float)
numbers = \
[n for n in flattedlist if isinstance(n, (int, float))]
# символы: Извлечь символы
characters = \
[str(l) for l in flattedlist if str(l).isalpha()]
# Отсортировать числа
numbers = bubblesort(numbers)
# Отсортировать символы
characters = bubblesort(characters)
# Объединить два отсортированных массива
flattedlist = numbers + characters
# Для хранения конечного результата
sortedlist = []
for s in sizes:
# Создать массив с размером s
sortedlist.append(flattedlist[:s])
'''
Обновить плоский список после вставки
предыдущих элементов в отсортированный список'''
flattedlist = flattedlist[s:]
return sortedlist
3.19. Сортировка дат
Целью этого задания является сортировка списка дат в формате DD-MMYYYY_HH: ММ в порядке возрастания или убывания. Критериями сорти-
126
Глава 3. Числа
ровки являются год, месяц, день, час и минута. Ваша задача: написать
функцию, которая принимает список дат и времени (в виде строк) и направление сортировки и возвращает отсортированный список дат и времени.
В табл. 3.19 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.19. Некоторые ожидаемые результаты для задачи сортировки дат
times, sort_types
Алгоритм
Алгоритм преобразует строки с датами и временем в объекты даты
и времени и сортирует их с использованием алгоритма пузырьковой сор
тировки. Затем объекты даты и времени преобразуются в строки.
В листинге 3.19 приводится код на Python, сортирующий даты.
Листинг 3.19. Сортировка дат
1 import datetime
2 def bubble_sort(arr):
3
for i in range(len(arr) - 1):
4
for j in range(0, (len(arr) - i) - 1):
5
if arr[j] > arr[j + 1]:
6
# Поменять местами, если необходимо
7
arr[j], arr[j + 1] = arr[j + 1], arr[j]
8
return arr
9 def sort_dates(times, sort_types):
10
time_objects = []
11
sorted_dates=[]
12
# Цикл по элементам списка
13
wanted_date = "%d−%m−%Y_%H:%M"
14
for t in times:
15
time_objects.append(
datetime.datetime.strptime(t, wanted_date))
# Сортировать даты с помощью алгоритма пузырьковой сортировки
time_objects = bubble_sort(time_objects)
if sort_types.lower() == 'asc':
for t in time_objects:
# Преобразовать даты в строки
sorted_dates.append(
(datetime.datetime.strftime(t, wanted_date)))
return sorted_dates
elif sort_types.lower() == 'dsc':
'''
Так как изначально даты отсортированы в порядке возрастания,
выполнить обход списка в обратном направлении.
'''
for t in time_objects[::-1]:
# Преобразовать даты в строки
sorted_dates.append(
(datetime.datetime.strftime(t, wanted_date)))
return sorted_dates
3.20. Сортировка по алфавиту и длине
Целью этого задания является сортировка слов в заданной строке сначала
по алфавиту, а затем по длине.
Ваша задача: написать функцию, которая принимает строку и возвращает строку, в которой слова отсортированы по алфавиту и длине.
В табл. 3.20 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.20. Некоторые ожидаемые результаты для задачи сортировки слов
в строке по алфавиту и длине
Sentence
Ожидаемый результат
'Year of the Tiger, is it fog'
'Tiger, Year fog the it of is'
'Python is one of the most used languages' 'languages Python most used the one of is'
'FIFA World Cup Qatar'
'Qatar World FIFA Cup'
'for if while def range else set'
'range while else def set for if'
128
Глава 3. Числа
Алгоритм
Алгоритм принимает строку с предложением, разбивает ее на слова, сор
тирует их в алфавитном порядке, используя алгоритм пузырьковой сор
тировки, а затем повторно сортирует их по длине. Для этого выполняется
обход слов в отсортированном списке, и длина каждого слова сравнивается
с длинами предшествующих слов. Если слово длиннее предшествующего,
они меняются местами. Наконец, отсортированные слова объединяются
в одну строку и возвращаются.
В листинге 3.20 приводится код на Python, сортирующий слова по алфавиту и длине.
Листинг 3.20. Сортировка слов по алфавиту и длине
1 def bubble_sort(arr):
2
for i in range(len(arr) - 1):
3
for j in range(0, (len(arr) - i) - 1):
4
if arr[j] > arr[j + 1]:
5
# Поменять местами, если необходимо
6
arr[j], arr[j + 1] = arr[j + 1], arr[j]
7
return arr
8 def sorted_by_alphabetical_and_length(sentence):
9
words = sentence.split()
10
# Отсортировать в алфавитном порядке
11
words = bubble_sort(words)
12
for word in range(0, len(words)):
13
for i in range(0, word):
14
# Поменять местами, если необходимо
15
if len(words[word]) > len(words[i]):
16
temp = words[i]
17
words[i] = words[word]
18
words[word] = temp
19
20
'''
21
Добавить отсортированные слова в sorted_sentence
22
(в строку)
23
'''
24
sorted_sentence = ""
25
for item in range(0, len(words)):
26
sorted_sentence += words[item] + ' '
27
return sorted_sentence
3.21. Сортировка чисел по количеству цифр 129
3.21. Сортировка чисел по количеству цифр
Стандартная операция сравнения чисел говорит нам, что число 101 больше числа 9. Однако в контексте сортировки по значениям цифр число
9 больше, чем 101. Целью этой задачи является сортировка массива чисел по количеству составляющих их цифр. Например, рассмотрим массив
array = [81181972, 8111972], и пусть a = 81181972 и b = 8111972. Сравнение
начинается с наибольшей цифры, в данном случае это 9. Оба числа имеют
по одной цифре 9, поэтому сравнивается следующая по величине цифра –
цифра 8. В a две восьмерки, а в b – одна, поэтому считается, что a больше. В общем случае сравнение выполняется следующим образом: если
в a и b имеется одинаковое количество цифр с одним и тем же значением,
то проверяется следующая цифра, меньшая по величине. Так продолжается до тех пор, пока не будет найдено отличие или пока не будут исчерпаны
все цифры в числах.
Ваша задача: написать функцию, которая принимает массив положительных целых чисел и возвращает массив, отсортированный по коли
честву цифр.
В табл. 3.21 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 3.21. Некоторые ожидаемые результаты для задачи сортировки чисел
по количеству цифр
Array
Ожидаемый результат
[81181972, 9, 123198776, 23, 456, 1]
[1, 23, 456, 9, 123198776, 81181972]
[1, 2, 3, 11, 9, 77, 66, 87, 111]
[1, 11, 111, 2, 3, 66, 77, 87, 9]
[39, 456, 0, 7, 3, 599]
[0, 3, 456, 7, 39, 599]
[]
[]
Алгоритм
Стратегия «разделяй и властвуй» – это метод решения задач, предполагающий деление сложной задачи на более мелкие, более управляемые
подзадачи и решение каждой подзадачи отдельно. Алгоритм сортировки
слиянием как раз основан на стратегии «разделяй и властвуй». Он многократно делит заданный список на подсписки, пока в каждом подсписке
не останется только один элемент. Эти подсписки затем объединяются
вместе, образуя отсортированный список. Алгоритм (сортировки слиянием) сначала рекурсивно делит входной массив на две половины, пока
не будет достигнут базовый вариант с одним элементом или пустой массив. Затем он определяет, какой из двух элементов должен следовать пер-
130
Глава 3. Числа
вым, основываясь на количестве их цифр. Наконец, два отсортированных
подмассива объединяются в порядке сортировки.
В листинге 3.21 приводится код на Python, сортирующий числа по количеству цифр.
Листинг 3.21. Сортировка чисел по количеству цифр
1 def sort_by_digit_count(arr):
2
"""
3
Сортирует массив положительных целых чисел
4
по количеству цифр.
5
"""
6
# Применить алгоритм сортировки слиянием
7
if len(arr) > 1:
8
# Поиск середины массива
9
mid = len(arr) // 2
10
11
# Деление массива на две половины
12
L = arr[:mid]
13
R = arr[mid:]
14
15
# Сортировка первой половины
16
L = sort_by_digit_count(L)
17
18
# Сортировка второй половины
19
R = sort_by_digit_count(R)
20
21
# Объединить две отсортированные половины
22
i, j, k = 0, 0, 0
23
while i < len(L) and j < len(R):
24
if max_(L[i], R[j]) == R[j]:
25
arr [k] = L[ i ]
26
i += 1
27
else:
28
arr[k] = R[j]
29
j += 1
30
k += 1
31
32
'''Проверить, есть ли в первой половине
33
элемент, который должен стоять левее
34
'''
35
while i < len(L):
36
arr[k] = L[i]
3.21. Сортировка чисел по количеству цифр 131
37
i += 1
38
k += 1
39
40
'''Проверить, есть ли в правой половине
41
элемент, который должен стоять левее
42
'''
43
while j < len(R):
44
arr[k] = R[j]
45
j += 1
46
k += 1
47
48
return arr
49
50
51 def max_(a, b):
52
"""
53
Принимает два положительных целых числа, a и b,
54
и возвращает то, в котором присутствует больше цифр
55
с бóльшим значением. В случае равенства
56
возвращается большее число.
57
58
"""
59
a, b = str(a), str(b)
60
for i in range(9, -1, -1):
61
if a.count(str(i)) > b.count(str(i)):
62
return int(a)
63
elif a.count(str(i)) < b.count(str(i)):
64
return int (b)
65
return max(int(a), int(b))
Глава
4
Строки
В этой главе рассматриваются 13 задач, которые сопровождаются примерами решения на Python. Вот эти задачи:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
Шифрование текста блинчиком.
Перестановка гласных в обратном порядке.
Форма слова из текстового корпуса.
Высота слова из текстового корпуса.
Объединение соседних цветов по заданным правилам.
Вторая машина Маккаллоха.
Слово Чампернауна.
Объединение заданных строк в новую строку на основе некоторых
правил.
Расшифровка слов.
Автокорректор слов.
Правильная форма глагола в испанском языке.
Выбор слов с одним и тем же набором букв.
Выбор слов из текстового корпуса, соответствующих шаблону.
4.1. Шифрование текста блинчиком
Задача шифрования текста блинчиком заключается в переворачивании
подстрок в заданном тексте t в порядке индексов 2, 3, …, n, где n – длина t.
Например, для текста t = «python» шифрование производится следующим
образом: сначала переворачивается подстрока, заканчивающаяся вторым
символом (y), «python» → «ypthon». Затем переворачивается подстрока,
заканчивающаяся третьим символом (t): «ypthon» → «tpyhon». Далее переворачивается подстрока, заканчивающаяся четвертым символом (h):
«tpyhon» → «hypton». И так далее до n‑го символа: «hypton» → «otpyhn» →
«nhypto».
4.1. Шифрование текста блинчиком 133
Ваша задача: написать функцию, которая принимает строку и применяет к ней шифрование блинчиком.
В табл. 4.1 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.1. Некоторые ожидаемые результаты для задачи шифрования текста
блинчиком
t
Ожидаемый результат
'python'
'nhypto'
'Deep Learning has revolutionized Pattern
Recognition'
'niigcRnetPdzniuoe a nnaLpeDe
erighsrvltoie atr eonto'
'Challenging Programming'
'gimroPginlaChlegn rgamn'
'x = 2x + 1 (9 * 56y)'
')6 (2=x x+19*5y'
Алгоритм
Алгоритм принимает строку с исходным текстом и возвращает новую
строку – зашифрованную версию исходной строки. Он перебирает каждый
индекс строки и переворачивает подстроку в исходной строке до этого
индекса, а затем объединяет перевернутую подстроку с остальной частью
исходной строки (т. е. с подстрокой после индекса). Этот процесс повторяется для каждого индекса строки, и в конце получается полностью зашифрованная строка.
В листинге 4.1 приводится код на Python, выполняющий шифрование
текста блинчиком.
Листинг 4.1. Шифрование текста блинчиком
1 # Функция, переворачивающая строку с помощью цикла for
2 def reverse_string(s):
3
reversed_s = ''
4
# Цикл по индексам в s в обратном порядке
5
for i in range(len(s)-1, -1, -1):
6
'''
7
Добавить символ с текущим индексом
8
в reversed_s
9
'''
10
reversed_s += s[i]
11
# Вернуть перевернутую строку
12
return reversed_s
13
14 # Функция шифрования блинчиком
134
Глава 4. Строки
15 def pancake_scramble_into_texts(t):
16
for i in range(len(t)):
17
# Перевернуть подстроку до индекса i включительно
18
Reversed_String = reverse_string(t[:i + 1])
19
# Взять остаток исходной строки
20
Orginal_String = t[i +1:]
21
# Объединить перевернутую подстроку с остатком исходной строки
22
t = Reversed_String + Orginal_String
23
# Вернуть зашифрованную строку
24
return t
4.2. Перестановка гласных в обратном
порядке
В этом задании дается текст и нужно создать новый текст, в котором гласные переставлены в обратном порядке. Кроме того, если символ с определенным индексом в исходном тексте имеет верхний регистр, соответствующий символ в новой строке тоже должен быть в верхнем регистре.
Например, если исходный текст s = «Other», тогда в результате должен
получиться текст o = «Ethor». В этой задаче рассматриваются гласные
«aeiouAEIOU».
Для некоторых входов ожидаемые результаты показаны в табл. 5.2.
В табл. 4.2 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.2. Некоторые ожидаемые результаты для задачи перестановки гласных
в обратном порядке
t
Ожидаемый результат
'Other'
'Ethor'
'Deep Learning has revolutionized Pattern
Recognition'
Алгоритм
Для перестановки гласных в строке алгоритм выполняет обход символов входной строки с дополнительными итерациями по индексам гласных
букв. В частности, алгоритм сначала извлекает все гласные буквы и их индексы из входной строки, используя генератор списков, который фильт
рует символы по принадлежности к набору гласных. Затем он перебирает
индексы в обратном порядке и собирает гласные в список. Наконец, про-
4.3. Форма слова из текстового корпуса 135
грамма перебирает исходные позиции гласных во входной строке и заменяет их соответствующими гласными из перевернутого списка, сохраняя
при этом формат прописных/строчных букв в каждой позиции.
В листинге 4.2 приводится код на Python, выполняющий перестановку
гласных в обратном порядке.
Листинг 4.2. Перестановка гласных в обратном порядке
1 def reverse_vowels_into_texts(s ) :
2
# Множество гласных
3
vowels = set ( "aeiouAEIOU" )
4
chars = list(s)
5
vowel_indices = \
6
[i for i in range(len(chars)) if chars[i] in vowels]
7
8
# Извлечь все гласные по их индексам
9
reversed_vowels = []
10
for i in range(len(vowel_indices) - 1, -1, -1):
11
reversed_vowels.append(chars[vowel_indices[i]])
12
13
'''
14
Заменить гласные в исходном тексте,
15
выполнив перестановку в обратном порядке
16
'''
17
j = 0
18
for i in vowel_indices:
19
if chars[i].isupper():
20
chars[i] = reversed_vowels[j].upper()
21
else:
22
chars[i] = reversed_vowels[j].lower()
23
j += 1
24
25
return ''.join(chars)
4.3. Форма слова из текстового корпуса
Форма заданного слова w длиной m – это список l, состоящий из m – 1 значений +1, –1 и 0. Число, добавляемое в результирующий список l, зависит
от алфавитного порядка: 'a' < 'b' < 'c' < 'd' < 'e' < 'f' < 'g' < 'h' < 'i' < 'j' < 'k' < 'l' <
'm' < 'n' < 'o' < 'p' < 'q'' < 's' < 't' < 'u' < 'v' < 'w' < 'x' < 'y' < 'z'. Для каждой пары
α и β если α < β, то shape = 1, если α > β, то shape = –1 и если α = β, то shape = 0.
Например, пусть дано слово word = optimum, для определения его формы
выполняются следующие шаги: o < p, соответственно, shape = [1] → p < t,
136
Глава 4. Строки
соответственно, shape = [1, 1] → t > i, соответственно, shape = [1, 1, –1] →
i < m, соответственно, shape = [1, 1, –1, 1] → m < u, соответственно, shape =
[1, 1, –1, 1, 1] → u > m, соответственно, shape = [1, 1, –1, 1, 1, –1]. В этом задании требуется найти все слова, формы которых совпадают с заданной.
Напишите функцию, которая принимает список слов (корпус текста)
и эталонную форму и возвращает список слов, форма которых совпадает с заданной.
В табл. 4.3 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.3. Некоторые ожидаемые результаты для задачи формы слова
из текстового корпуса
Words, shape
Алгоритм
Алгоритм определяет форму слова на основе алфавитного порядка составляющих его символов и использует эту форму для фильтрации списка
слов. Правила реализуются с помощью операторов. Для этого используется оператор if-else.
В листинге 4.3 приводится код на Python, вычисляющий и возвращающий все слова с формой, совпадающей с заданной.
Листинг 4.3. Вычисление форм слов и возврат тех из них, формы которых
совпадают с заданной
1 def Word_Shape_from_a_Text_Corpus(words, shape):
2
output = []
3
# Выполнить обход списка слов
4
for i in words:
5
'''
6
Выбрать слова, форма которых
7
совпадает с заданной
8
'''
9
if len(i) == len(shape)+1:
10
if word_shape(i) == shape:
11
output.append(i)
12
return output
4.4. Высота слова из текстового корпуса 137
13 def word_shape(word) :
14
# Создать массив
15
shape = ([None] * (len(word) - 1))
16
for i in range((len(shape))):
17
'''
18
Функция ord принимает символ и
19
возвращает целое число (код юникода), на основе
20
которого определяется алфавитный порядок.
21
'''
22
'''
23
Определить форму данного слова,
24
используя заданные критерии
25
'''
26
a = ord(word[i])
27
b = ord(word[i + 1])
28
if a < b:
29
shape[i] = 1
30
elif a == b:
31
shape[i] = 0
32
elif a > b:
33
shape[ i ] = -1
34
return shape
4.4. Высота слова из текстового корпуса
Под длиной слова понимается количество содержащихся в нем символов,
а под высотой – количество значимых подслов, которые можно получить
из него. Слово, не имеющее собственного значения, имеет нулевую высоту, тогда как слово, которое имеет смысл и не может быть разделено на два
значимых подслова, имеет высоту, равную единице.
Высота слов, которые можно разбить на подслова, равна наибольшей
высоте его подслов плюс один. Например, слово «roqm» не имеет собственного значения и, следовательно, имеет нулевую высоту. С другой
стороны, слово «chukker» нельзя разделить на два значимых подслова,
поэтому его высота равна единице. Наконец, такое слово, как «enterprise»,
можно рекурсивно разбить на подслова до получения бессмысленных
слов, и его высота будет определяться количеством его подслов. Ваша задача: написать функцию, которая принимает список слов words и одно
слово word и возвращает высоту слова word, определяемую поиском подслов в words.
В табл. 4.4 показаны ожидаемые результаты для некоторых входных
данных.
138
Глава 4. Строки
Таблица 4.4. Некоторые ожидаемые результаты для задачи определения
высоты слова по словам в текстовом корпусе
Words, word
Ожидаемый результат
['A', 'chukker', 'corpus', 'text'], wjobnv
0
['A', 'chukker', 'corpus', 'text'], chukker
1
Важно отметить, что полная высота слова определяется по словам в текстовом корпусе.
Алгоритм
Алгоритм рекурсивно вычисляет высоту слова, разбивая его на более
мелкие части, рекурсивно вычисляя высоты этих частей и комбинируя
высоты частей, получает высоту исходного слова. Чтобы избежать избыточных вычислений и повысить производительность, используется мемоизация. Ниже подробно описаны шаги, выполняемые алгоритмом.
1. Принимается три входных параметра: words – список слов в текстовом корпусе, word – слово, высоту которого необходимо вычислить,
и memo – словарь, используемый для запоминания ранее вычисленных высот.
2. Если параметр memo не указан, то создается новый пустой словарь.
3. Если высота текущего слова уже вычислена и хранится в memo, то возвращается запомненное значение.
4. Для поиска данного слова в списке слов используется алгоритм двоичного поиска. Если слово найдено в списке, возвращается его индекс; в противном случае возвращается –1.
5. Если слово отсутствует в списке words, его высота принимается равной 0, возвращается 0 и алгоритм завершается.
6. Для хранения всех возможных способов деления слова на две части
и проверки наличия обеих частей в списке слов используется список validList.
7. Цикл перебирает все возможные позиции разделения слова word,
от позиции 1 до длины слова минус 1. Для каждой позиции извлекаются левая и правая части слова.
8. Если в списке words обнаруживаются левая и правая части, то они добавляются в список validList.
9. Если допустимых разбиений не обнаружено, высота слова принимается равной 1 и возвращается 1.
10. Для хранения высот всех допустимых разделений создается список
hs.
4.4. Высота слова из текстового корпуса 139
11. Для каждого допустимого разделения (ls, rs) высота левой и правой
частей вычисляется рекурсивно. Если высота какой-то части уже вычислена и хранится в memo, то используется запомненное значение;
в противном случае выполняется рекурсивный вызов для вычисления высоты. Высоты обеих частей складываются, и прибавляется 1
(исходное слово имеет смысл), чтобы получить высоту текущего разделения.
12. По завершении возвращается максимальная высота из всех допус
тимых разделений, хранящихся в memo.
В листинге 4.4 приводится код на Python, вычисляющий высоту слова.
Листинг 4.4. Вычисление высоты слова
'''
Эта функция реализует двоичный поиск
значения в отсортированном списке
'''
'''
Двоичный поиск − популярный алгоритм, используемый для
поиска элементов в упорядоченном списке.
'''
'''
В процессе работы функция последовательно делит интервал поиска
пополам, пока не будет найдено искомое значение или
пока интервал поиска не опустеет.
'''
def binary_search(lst, x):
left = 0
right = len(lst) - 1
while left 1:
'''
Создать новый список для хранения результатов
комбинирования соседних элементов.
'''
TemparrayColors = ([None] * (len(colors) - 1))
'''
Цикл по парам соседних цветов
во входном списке.
'''
for i in range(len(TemparrayColors)):
'''
Проверить, присутствует ли результат комбинирования
текущей пары цветов в словаре cache.
'''
if (colors[i], colors[i + 1]) in cache:
# Если присутствует, вернуть его.
TemparrayColors[i] = \
cache[(colors[i], colors[i + 1])]
else:
'''
Если нет, то вызвать функцию combine(),
чтобы получить результат, сохранить его в cache
и использовать.
'''
result = combine(colors[i], colors[i + 1])
cache[(colors[i], colors[i + 1])] = result
TemparrayColors[i] = result
'''
Заменить входной список новым
списком с комбинированными цветами.
'''
colors = TemparrayColors
# Вернуть окончательный результат.
return colors[0]
4.6. Вторая машина Маккаллоха
В этом задании рассматривается пример эзотерического языка программирования, который поможет вам улучшить ваши навыки программирования на Python. Эзотерический язык программирования, также известный как эзоланг, – это язык, предназначенный для проверки сложных
и нетрадиционных идей. Он не предназначен для практического исполь-
4.6. Вторая машина Маккаллоха 145
зования и служит исключительно развлекательным целям. Система перезаписи строк Маккаллоха использует цифры от 0 до 9 и применяет к ним
определенные правила. В этом контексте массив X представляет строки
со значениями в диапазоне от 0 до n – 1, а массив Y вычисляется на основе X и состоит из значений в диапазоне от 1 до n – 1.
1.
2.
3.
4.
Если X [0] = 2, то в Y возвращается оставшаяся часть массива X.
Если X [0] = 3, то в Y возвращается X + 2 + X.
Если X [0] = 4, то в Y возвращается X [:: – 1].
Если X [0] = 5, то в Y возвращается X + X.
Ваша задача: написать функцию, которая принимает строку X и возвращает результат, полученный на основе упомянутых правил.
В табл. 4.6 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.6. Некоторые ожидаемые результаты для задачи
перезаписи строк
X
Ожидаемый результат
'2999'
'999'
'329'
'929'
'101'
None
'322097845'
'209784522097845'
Алгоритм
Алгоритм перезаписи заданной строки цифр в соответствии с определенными правилами принимает строку X и на основе ее первой цифры
выбирает правило для применения к цифрам. Затем этот процесс рекурсивно повторяется до тех пор, пока в строке не останется цифр или пока
не встретится цифра, для которой нет правила.
В листинге 4.6 приводится код на Python, решающий задачу перезаписи
заданной строки цифр.
Листинг 4.6. Перезапись заданной строки цифр
1
2
3
4
5
6
# Функция, удаляющая первую цифру
def remove_first_digit(X):
return X[1:]
'''
Функция, разрезающая строку и
вставляющая '2' в середину
'''
def slice_and_append_2(X):
return mcculloch(X[1:]) + '2' + mcculloch(X[1:])
# Функция, обращающая строку
def reverse(X):
return mcculloch(X[1:])[::−1]
# Функция, удваивающая строку
def double(X):
return mcculloch(X[1:]) + mcculloch(X[1:])
def mcculloch(X) :
'''
Словарь, отображающий первую
цифру в соответствующую функцию
'''
functions = {
'2' : remove_first_digit,
'3' : slice_and_append_2,
'4' : reverse,
'5' : double,
}
# Если первая цифра в X имеется в словаре
if X[0] in functions:
'''
Вызвать соответствующую функцию
для оставшихся цифр в X
'''
return functions[X[0]](X)
4.7. Слово Чампернауна
Слово Чампернауна – это длинная строка, не содержащая разделителей-запятых. Оно состоит из последовательности чисел начиная с единицы и увеличивающихся на единицу. Цель этой задачи – вернуть цифру, соответствующую данному индексу. Важно отметить, что эту задачу
невозможно решить с помощью обычного метода, такого как list.index, изза ограничений во времени и пространстве. Для решения данной задачи
следует написать функцию, которая принимает положительное целое число n, представляющее желаемый индекс, и возвращает соответствующую
цифру. Например, в седьмой позиции (счет начинается с 0) в последова-
4.7. Слово Чампернауна 147
тельности «1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …» находится цифра 8.
В табл. 4.7 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.7. Некоторые ожидаемые результаты для задачи
получения слова Чампернауна
X
Ожидаемый результат
12**214
'9'
7
'8'
717897987691852588770047
'2'
3111111198765431001
'1'
При решении задачи количество цифр в каждой последовательности
определяется по следующей таблице.
Номер
последовательности
Диапазон
Число слов
Число цифр в каждой
последовательности
1
1–9
9
9
2
10–99
90
180
3
100–999
900
2700
4
1000–9999
9000
36 000
Алгоритм
1. Принимается один входной параметр: n (номер искомой цифры n‑я
цифра).
2. Инициализируются переменные d (цифры), p_i (передаваемые индексы), p_n (передаваемые числа) и w (количество слов) значениями
0 и 9 соответственно.
3. Пока n больше или равно p_i + w * (d + 1), увеличивать d на 1, обновлять p_i до p_i + w * (d + 1), p_n до p_n + w и w до w * 10.
4. Вычисляется индекс p как (n – p_i)//(d + 1).
5. Вычисляется искомое число как p_n + p + 1.
6. Полученное число преобразуется в строку, и выбирается символ
по индексу (n – p_i) % (d + 1).
7. Возвращается n‑я цифра как результат работы алгоритма.
В листинге 4.7 приводится код на Python, решающий задачу получения
слова Чампернауна.
148
Глава 4. Строки
Листинг 4.7. Получение слова Чампернауна
1 def Champernowne_Word(n):
2
d = 0
3
p_i = 0
4
p_n = 0
5
w = 9
6
7
while n >= p_i + w * (d + 1):
8
p_i += w * (d + 1)
9
p_n += w
10
d += 1
11
# Переход к очередной последовательности
12
w *= 10
13
14
p = (n - p_i) // (d + 1)
15
16
'''
17
Преобразовать число в строку и получить
18
цифру по искомому индексу
19
'''
20
21
num = str (p_n + p + 1)
22
return num[(n - p_i) % (d + 1)]
4.8. Объединение строк
Пусть v = {aeiou} – множество гласных, а X и Y – первое и второе слова соответственно. Если в слове X имеется хотя бы одна гласная из множества v,
то считается, что оно имеет как минимум одну группу гласных. Если в X
имеется две гласные, разделенные согласной, то они образуют две группы гласных, а если гласные следуют друг за другом, то все они относятся
к одной группе. Например, в слове pythonist две группы гласных (обратите
внимание, что y не принадлежит множеству v, поэтому она не учитывается
при подсчете групп), а в слове keep – одна. Задача заключается в создании новой строки на основе двух имеющихся. Вот правила создания новой
строки:
1. Если в X одна группа гласных, то сохраняются только символы перед гласной, и эта часть X объединяется с Y так, что первые согласные в Y перед первой гласной удаляются. Например, если X = 'go'
и Y = 'meaning', то на выходе получится строка 'geaning'.
4.8. Объединение строк 149
2. Если в X имеется более одной группы гласных, то сохраняются все
символы, предшествующие второй гласной, и эта часть X объединяется с Y так, что первые согласные в Y перед первой гласной удаляются. Например, если X = 'python' и Y ='visual', то на выходе получится 'pythisual'.
Напишите функцию, которая принимает две строки, X и Y, и возвращает
новую строку, составленную из X и Y, следуя приведенным выше правилам.
В табл. 4.8 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.8. Некоторые ожидаемые результаты для задачи
объединения заданных строк в новую строку
X, Y
Ожидаемый результат
'go', 'meaning'
'geaning'
'python', 'visual'
'pythisual'
'elliot', 'bill'
'ill'
'ross', 'jules'
'rules'
Алгоритм
Алгоритм принимает две входные строки, first_word и second_word, и объ
единяет их в одну строку. Объединение осуществляется путем выбора соответствующих сегментов из каждой входной строки. На первом шаге алгоритм определяет последовательные гласные в каждой входной строке. Для
этого он просматривает каждый символ в обеих входных строках и проверяет, является ли он гласной. Если символ является гласной, то алгоритм
проверяет, был ли и предыдущий символ гласной. Если да, то индекс текущей гласной добавляется в подсписок предыдущих гласных. В противном
случае для текущей гласной создается новый подсписок. После того как
для каждой входной строки будут определены группы последовательных
гласных, алгоритм определяет, какие сегменты входных строк следует
сохранить в объединенной строке. Если первая входная строка не содержит последовательных гласных, то сохраняется вся строка. Если первая
входная строка содержит только одну группу последовательных гласных,
то алгоритм сохраняет все ее содержимое до первой гласной. В противном
случае алгоритм сохраняет все в первой входной строке до предпоследней
группы гласных. Сегмент второй входной строки, который необходимо сохранить в объединенной строке, всегда начинается с первой гласной второй входной строки. Наконец, алгоритм объединяет выбранные сегменты
двух входных строк и возвращает результат.
150
Глава 4. Строки
В листинге 4.8 приводится код на Python, решающий задачу объединения строк.
Листинг 4.8. Объединение строк
1 def combine_strings_into_one(first_word, second_word):
2
vowels = 'aeiou'
3
4
'''
5
Извлечь последовательные гласные из первого слова
6
'''
7
first_vowel_groups = []
8
for i in range(len(first_word)):
9
if first_word[i] in vowels:
10
'''
11
Если предыдущий символ − гласная,
12
то добавить индекс в предыдущий подсписок
13
'''
14
if i > 0 and first_word[i - 1] in vowels:
15
first_vowel_groups[-1].append(i)
16
'''
17
Иначе создать новый подсписок
18
для текущей гласной
19
'''
20
else:
21
first_vowel_groups.append([i])
22
23
'''
24
Извлечь последовательные гласные
25
из второго слова
26
'''
27
second_vowel_groups = []
28
for i in range(len(second_word)):
29
if second_word[i] in vowels:
30
'''
31
Если предыдущий символ − гласная,
32
то добавить индекс в
33
предыдущий подсписок
34
'''
35
if i > 0 and second_word[i - 1] in vowels:
36
second_vowel_groups[−1].append(i)
37
'''
38
Иначе создать новый подсписок
для текущей гласной
'''
else:
second_vowel_groups.append([i])
# Определить сохраняемый сегмент в первом слове
'''
Если в первом слове нет последовательных гласных,
то сохранить все слово целиком
'''
if len(first_vowel_groups) == 0:
fw_segment = first_word
'''
Если в слове только одна группа гласных,
то сохранить все буквы
до первой гласной
'''
elif len(first_vowel_groups) == 1:
fw_segment = first_word[:first_vowel_groups[0][0]]
'''
Иначе сохранить все буквы
до второй с конца
группы гласных
'''
else:
fw_segment = first_word[:first_vowel_groups[−2][0]]
'''
Определить сохраняемый сегмент
во втором слове, который начинается
с первой гласной во втором слове
'''
sw_segment = second_word[second_vowel_groups[0][0]:]
return fw_segment + sw_segment
4.9. Расшифровка слов
Английские слова можно произвольно зашифровать, не влияя на их читабельность, при условии что первая и последняя буквы остаются одинаковыми, а длина слова остается неизменной. Цель этого задания – расшифровать заданное слово и определить похожие слова из предоставленного
списка. Ваша задача: написать функцию, которая принимает строку word
152
Глава 4. Строки
и список слов words и возвращает список слов из words, которые соответствуют следующим критериям:
1. Слово имеет ту же длину, что и word, и первая и последняя буквы
в слове совпадают с первой и последней буквами в word.
2. Порядок сортировки остается прежним.
В табл. 4.9 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.9. Некоторые ожидаемые результаты для задачи расшифровки слов
Words, word
Алгоритм
Пусть дана строка word. Чтобы расшифровать слово в этой строке, выполняются следующие шаги.
1. Создается пустой массив res для хранения похожих слов.
2. Из списка words последовательно выбирается каждое слово w.
3. Для каждого слова w проверяется совпадение его длины с длиной word.
4. Если проверка прошла успешно, то проверяется совпадение первых
и последних букв в w и word.
5. Если и эта проверка прошла успешно, то w добавляется в список res.
6. Шаги 3–5 повторяются для всех слов в words.
7. Возвращается полученный список res.
В листинге 4.9 приводится код на Python, решающий задачу расшифровки слов.
Листинг 4.9. Расшифровка слов
1 def bubble_sort(arr):
2
for i in range(len(arr) - 1):
3
for j in range(0, (len(arr) - i) - 1):
4
if arr[j] > arr[j + 1]:
5
# Поменять элементы местами
6
arr[j], arr[j + 1] = arr[j + 1], arr[j]
7
return arr
4.10. Автокорректор слов 153
8 def Unscrambling_the_given_words(words, word):
9
res=[]
10
for w in words:
11
'''
12
С помощью инструкции continue текущее слово w
13
пропускается, и выполняется переход к следующему слову.
14
'''
15
if len(w) != len(word):
16
continue
17
elif w[0] != word[0] or w[-1] != word[-1]:
18
continue
19
# При желании можно использовать любой другой алгоритм сортировки
20
if bubble_sort(list(word)) == bubble_sort(list(w)):
21
res .append(w)
22
return res
4.10. Автокорректор слов
Существует несколько методов автоматического исправления орфографических ошибок в словах. Один из наиболее распространенных основан на вычислении расстояния между словами. Этот метод предполагает
замену букв в слове ближайшими на клавиатуре. Например, если предполагаемое слово «car», а входное слово «csr», то букву «s», следует заменить буквой «a», которая находится рядом с «s» на клавиатуре, поэтому «csr» → «car». Эта задача требует вычисления всех расстояний между
ключевыми словами в списке и данным словом с последующей заменой
входного слова словом из списка, имеющим минимальное расстояние
до заданного. Ваша задача: написать функцию, которая принимает проверяемое слово word и список слов words и возвращает слово w из списка
words, имеющее минимальное расстояние от заданного.
В табл. 4.10 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.10. Некоторые ожидаемые результаты для задачи автокоррекции слов
Words, word
Алгоритм
Пусть даны строка word и список слов words. Для каждого слова w в words
алгоритм проверяет, имеют ли w и word одинаковую длину. Если это так,
154
Глава 4. Строки
то алгоритм вычисляет расстояние на клавиатуре QWERTY для каждой
пары символов в w и word, сохраняет расстояния в массив storage и вычисляет сумму расстояний. Эта сумма присваивается слову w. Процесс повторяется для всех слов в words. Наконец, алгоритм возвращает слово из words,
которое имеет минимальное расстояние до данного слова word.
В листинге 4.10 приводится код на Python, решающий задачу автокоррекции слов.
Листинг 4.10. Автокоррекция слов
def keyword_distance():
# Порядок букв на типичной клавиатуре
top = {c: (0, i) for (i, c) in enumerate("qwertyuiop")}
mid = {c: (1, i) for (i, c) in enumerate("asdfghjkl")}
bot = {c: (2, i) for (i, c) in enumerate( "zxcvbnm")}
# Обновить словарь, передав несколько аргументов
keys = dict(top, **mid, **bot)
dist = dict()
lows = "abcdefghijklmnopqrstuvwxyz"
# Вычислить расстояние
for cc1 in lows:
for cc2 in lows:
(r1, c1) = keys[cc1]
(r2, c2) = keys[cc2]
dist[(cc1, cc2)] = \
(abs(r2 − r1) + abs(c2 − c1)) ** 2
return dist
dist = keyword_distance()
# Вызов keyword_distance
'''
При использовании этой функции нет нужды
каждый раз вычислять расстояние между парами.
'''
def ds(c1, c2):
return dist [(c1, c2)]
def autocorrectr_word(words,word):
'''
Извлечь слово той же
длины, что и входное слово
'''
'''
strip: удаляет начальные пробелы
'''
4.11. Правильная форма глагола в испанском языке 155
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
'''
dict.fromkeys: присваивает значение каждому
объекту в последовательности
'''
dists = dict.fromkeys\
([x.strip() for x in words if len(x) == len(word)], 0)
for w in dists.keys():
'''
Сохранить расстояние между
текущим и заданным словами
'''
storage = []
for i in range(len(word)):
storage.append(ds(w[i], word[i]))
dists[w] = sum(storage)
return min(dists, key=dists.get)
4.11. Правильная форма глагола
в испанском языке
В этом задании требуется найти правильные формы глагола в испанском
языке. Ваша задача: написать функцию, которая принимает глагол, лицо
и время и возвращает правильную форму глагола в испанском языке.
В табл. 4.11 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.11. Некоторые ожидаемые результаты для задачи
определения правильной формы глагола в испанском языке
Verb, subject, tense
Ожидаемый результат
'ganar', 'ustedes', 'pretérito'
'ganaron'
'escribir', 'ellos', 'imperfecto'
'escribían'
'tomar', 'nosotros', 'futuro'
'tomaremos'
Агоритм
В испанском языке есть три типа правильных глаголов. Следовательно, необходимо рассмотреть три условия и определить правильную
форму глагола с учетом изменения по лицам и временам. Для этой цели
используется словарь Python. Ключами в словаре служат лица, а значениями – окончания, которые следует добавить к данному глаголу. Проще говоря, отыскав лицо, остается только добавить окончание к заданному слову.
156
Глава 4. Строки
В листинге 4.11 приводится код на Python, решающий задачу определения правильной формы глагола в испанском языке.
Листинг 4.11. Определение правильной формы глагола в испанском языке
1 def Correct_verb_form_in_Spanish(verb, subject, tense):
2
'''
3
Словарь для хранения окончаний,
4
которые должны добавляться к глаголам.
5
Роль ключей в di играют лица, а роль
6
значений − окончания для добавления
7
к глаголам
8
'''
9
di = {}
10
# Правильные глаголы первой формы
11
if verb[-2::] == 'ar':
12
# Если указано настоящее время
13
if tense == 'presente':
14
di = {'yo': 'o', 'tú': 'as',
15
'él': 'a', 'ella': 'a',
16
'usted': 'a',
17
'nosotros': 'amos',
18
'nosotras': 'amos',
19
'vosotros': 'áis',
20
'vosotras': 'áis',
21
'ellos': 'an',
22
'ellas': 'an',
23
'ustedes': 'an'
24
}
25
26
elif tense == 'pretérito' :
27
di = {'yo': 'é', 'tú': 'aste',
28
'él': 'ó', 'ella': 'ó',
29
'usted': 'ó',
30
'nosotros': 'amos',
31
'nosotras': 'amos',
32
'vosotros': 'asteis',
33
'vosotras': 'asteis',
34
'ellos': 'aron',
35
'ellas': 'aron',
36
'ustedes': 'aron'
37
}
4.11. Правильная форма глагола в испанском языке 157
'ellas': 'ían',
'ustedes': 'ían'
}
'''
Если задано будущее время, то
форма глагола не имеет значения
'''
if tense == 'futuro':
di = {'yo': 'é', 'tú': 'ás',
'él': 'á', 'ella': 'á',
'usted': 'á',
'nosotros': 'emos',
'nosotras': 'emos',
'vosotros': 'éis',
'vosotras': 'éis',
'ellos': 'án', 'ellas': 'án',
'ustedes': 'án'
}
'''
Если задано будущее время, то
последние две буквы в глаголе удалять не надо.
'''
return verb + di[subject]
'''
Если задано не будущее время, то
надо удалить две последние буквы в глаголе.
'''
return verb[:len(verb) - 2:] + di[subject]
4.12. Выбор слов с одним и тем же
набором букв
Подстрока – это часть оригинальной строки, сохраняющая те же символы в том же порядке, а производная перестановка – это строка, в которой
порядок букв не обязательно совпадает с исходной строкой. Например,
«tho» – это подстрока «python», а «thypno» – это производная перестановка
от «python». Ваша задача: написать функцию, которая принимает список
букв letter и список слов words и возвращает все слова из words, содержащие
только буквы, имеющиеся в letter.
В табл. 4.12 показаны ожидаемые результаты для некоторых входных
данных.
160
Глава 4. Строки
Таблица 4.12. Некоторые ожидаемые результаты для задачи выбора слов с одним
и тем же набором букв
Words, letter
Алгоритм
Алгоритм использует комбинацию вложенных циклов и операций
со строками для поиска слов, включающих один и тот же набор букв. Он
перебирает каждое слово во входном списке и проверяет длину слова,
сравнивая с длиной строки с искомыми буквами. Если длина слова больше
или равна длине строки с буквами, то слово преобразуется в список символов, а затем запускается другой цикл, проверяющий присутствие в слове
каждой искомой буквы. Если в слове найдены все буквы, то оно добавляется в результирующий список. В завершение алгоритм возвращает этот
список.
В листинге 4.12 приводится код на Python, решающий задачу выбора
слов с одним и тем же набором букв.
Листинг 4.12. Выбор слов с одним и тем же набором букв
1 def subsequent_letters(words, letters):
2
'''Получить длину letters − списка
3
искомых букв
4
'''
5
len_let = len(letters)
6
'''
7
Создать пустой список
8
для хранения результата
9
'''
10
ST = []
11
12
# Цикл по словам во входном списке
13
for term in words:
14
'''
15
Длина рассматриваемого слова должна быть
16
не меньше длины строки с искомыми символами
17
'''
18
if len(term) >= len(letters):
19
# Преобразовать слово в список символов
4.13. Выбор слов из текстового корпуса, соответствующих шаблону 161
indterm = list(term)
'''
Инициализировать счетчик и индекс для
отслеживания найденных букв
'''
counter = 0
CurrentIndex = -1
'''
цикл по искомым буквам
'''
for let in letters:
'''
Проверить присутствие искомой буквы среди
оставшихся букв в слове
'''
if let in indterm[CurrentIndex + 1:]:
'''
Если буква найдена,
то обновить индекс и счетчик
'''
indexlet = \
indterm.index(let, CurrentIndex + 1)
CurrentIndex = indexlet
counter += 1
'''
Если найдены все буквы, то
добавить слово в список
результатов и прервать цикл
'''
if counter == len_let:
ST.append(term)
break
# Вернуть список с найденными словами
return ST
4.13. Выбор слов из текстового корпуса,
соответствующих шаблону
В этом задании дается шаблон строки и нужно найти все слова, включающие этот шаблон. Например, если p = ***b*ls – заданный шаблон, то слова
162
Глава 4. Строки
'jumbals' и 'verbals' будут соответствовать этому шаблону (т. е. включать
его). Ваша задача: написать функцию, которая принимает строковый шаб
лон и возвращает все слова, содержащие его.
В табл. 4.13 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 4.13. Некоторые ожидаемые результаты для задачи выбора слов из текстового корпуса, соответствующих шаблону
Words, pattern
Алгоритм
Пусть words – это список заданных слов, а pattern – шаблон искомой
строки. Алгоритм проверяет каждое слово word в списке words на соответствие шаблону pattern, для этого он проверяет, все ли буквы, имеющиеся
в шаблоне pattern, присутствуют в слове word в той же последовательности
и в той же кодировке, и если да, то сохраняет слово word в массив result.
В листинге 4.13 приводится код на Python, решающий задачу выбора
слов из текстового корпуса, соответствующих шаблону.
Листинг 4.13. Выбор слов из текстового корпуса, соответствующих шаблону
1 def encode(word, pattern):
2
'''
3
Символ * имеет код 42
4
'''
5
encoding_pattern = list(pattern.encode())
6
encoding_word = list(word.encode())
7
pattern_filter = \
8
[x for x in encoding_pattern if x != 42]
9
encoded_word = []
10
'''
11
Достаточно, чтобы в слове присутствовали те же буквы, что и в шаблоне.
12
И не важно, какие другие буквы присутствуют.
13
'''
14
for int_ in encoding_word:
15
if int_ in pattern_filter:
16
encoded_word.append(int_)
17
else:
18
encoded_word.append(42)
19
return encoding_pattern , encoded_word
4.13. Выбор слов из текстового корпуса, соответствующих шаблону 163
20
21 def possible_words(words, pattern):
22
'''
23
Проверяет каждое слово на соответствие шаблону, и
24
если оно соответствует, то добавляет
25
слово в результирующий список.
26
'''
27
result = []
28
pattern_encoding = encode('', pattern)[0]
29
for word in words:
30
'''
31
Чтобы избежать проверки всех слов,
32
проверять только слова, имеющие ту же длину,
33
что и шаблон.
34
'''
35
if len(word) == len(pattern):
36
word_encoding = encode(word, pattern)[1]
37
if word_encoding == pattern_encoding:
38
result.append(word)
39
return result
Глава
5
Игры
В этой главе рассматриваются 14 игровых задач, которые сопровождаются
примерами решения на Python. Вот эти задачи:
1. Определение выигрышной карты.
2. Подсчет карт каждой масти в игре бридж.
3. Получение сокращенного представления карт в раздаче в игре
«Контрактный бридж».
4. Наборы карт одинаковой формы в карточной игре.
5. Подсчет количества раундов обработки чисел в порядке возрастания.
6. Достижение стабильного состояния в распределении конфет.
7. Игра вари.
8. Количество безопасных полей на шахматной доске с ладьями.
9. Количество безопасных полей на шахматной доске со слонами.
10. Достижимость поля для коня в многомерных шахматах.
11. Захват максимального количества шашек на шахматной доске.
12. Количество безопасных полей для размещения дружественных фигур на шахматной доске.
13. Количество очков в игре в кости «Скала».
14. Наилучший результат из нескольких бросков в игре в кости «Скала».
5.1. Определение выигрышной карты
Среди карточных игр есть игра с четырьмя игроками, в которой каждому
игроку сдается одна карта и затем они по очереди вскрывают свои карты.
В игре может назначаться или не назначаться козырная масть: «трефы»,
«пики», «червы» или «бубны». Достоинства карт определяются в порядке
убывания так: «туз» > «король» > «дама» > «валет» > 10 > 9 > 8 > 7 > 6 > 5 > 4 >
3 > 2 > 1. Победитель в игре определяется по следующим правилам:
5.1. Определение выигрышной карты 165
1. Если в игре есть козыри, то выигрывает игрок, имеющий козырь
с наибольшим достоинством.
2. Если в игре нет козырей, то выигрывает игрок, имеющий карту
с наивысшим достоинством и с мастью, совпадающей с мастью карты, которая была вскрыта первой.
Например, если игрокам сданы карты [(тройка, трефы), (король, пики),
(дама, трефы), (валет, червы)] и козырями являются трефы, то выигрывает
игрок с картой (дама, трефы) как обладающий козырной картой наибольшего достоинства.
Другой пример: игрокам сданы карты [(четверка, бубны), (туз, трефы),
(четверка, пики), (король, трефы)] и в игре нет козырей. В таком случае
выигрывает игрок с картой (четверка, бубны), потому что у других игроков
карты другой масти и они не могут побить первую карту.
Ваша задача: написать функцию, которая принимает список карт в раздаче и возвращает выигравшую карту.
В табл. 5.1 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.1. Некоторые ожидаемые результаты для задачи определения
выигрышной карты
Cards, trump
Алгоритм
Для каждой масти – пики (spades), червы (hearts), бубны (diamonds)
и трефы (clubs) – программа сохраняет соответствующие ранги и сортирует их в соответствии с правилами, используя алгоритм пузырьковой сор
тировки. На следующем этапе программа выбирает карту с самым высоким рангом на основе следующих критериев: если козырная карта указана
на входе, то выбирается первая козырная карта с самым высоким рангом.
Если козырная карта не указана, то выбирается первая карта с самым высоким рангом.
В листинге 5.1 приводится код на Python, определяющий выигрышную
карту.
166
Глава 5. Игры
Листинг 5.1. Определение выигрышной карты
1 def bubble_sort(arr):
2
for i in range(len(arr) - 1):
3
for j in range(0, (len(arr) - i ) - 1):
4
if arr[j] > arr[j + 1]:
5
# Поменять местами, если необходимо
6
arr[j], arr[j + 1] = arr[j + 1], arr[j]
7
return arr
8 def Winner_in_Card_Game(cards, trump=None):
9
names = [x[1] for x in cards]
10
'''
11
Массивы для определения рангов, если
12
козыри определены.
13
'''
14
spades = []
15
hearts = []
16
diamonds = []
17
clubs = []
18
'''
19
dicnames служит для поиска ранга
20
по числовому значению
21
'''
22
dicnames = {1: 'one' , 2: 'two' , 3: 'three', 4: 'four',
23
5: 'five', 6: 'six', 7: 'seven',
24
8: 'eight', 9: 'nine', 10: 'ten', 50: 'ace',
25
40: 'king', 30: 'queen', 20: 'jack'}
26
for item in cards :
27
if item[1] == 'spades':
28
if item[0] == 'ace':
29
spades.append(50)
30
elif item[0] == 'king':
31
spades.append(40)
32
elif item[0] == 'queen':
33
spades.append(30)
34
elif item[0] == 'jack':
35
spades.append(20)
36
elif item[0] == 'one':
37
spades.append(1)
38
elif item[0] == 'two':
39
spades.append(2)
40
elif item[0] == 'three':
41
spades.append(3)
elif item[0] == 'three':
clubs.append(3)
elif item[0] == 'four':
clubs.append(4)
elif item[0] == 'five':
clubs.append(5)
elif item[0] == 'six':
clubs.append(6)
elif item[0] == 'seven':
clubs.append(7)
elif item[0] == 'eight':
clubs.append(8)
elif item[0] == 'nine':
clubs.append(9)
elif item[0] == 'ten':
clubs.append(10)
bubble_sort(spades)
bubble_sort(hearts)
bubble_sort(diamonds)
bubble_sort(clubs)
'''
Функция eval вычисляет выражение.
Проще говоря,
она принимает строку и возвращает
результат.
t = eval('9') даст t = 9, где t - целое число.
t = eval('2*x+1'даст t = 13
'''
# Использовать правила для определения победителя
'''
eval(cards[0][1]) вернет
значение 'spades', или 'hearts', или 'diamonds',
или 'clubs', [-1] вернет
наибольший ранг, потому что массив
отсортирован по возрастанию.
'''
if trump not in names:
return dicnames[eval(cards[0][1])[−1]], cards[0][1]
# Если козырь задан
elif trump in names:
'''
eval(trump) вернет значение
'spades', или 'hearts', или 'diamonds', или 'clubs',
170
Глава 5. Игры
171
172
173
174
[-1] вернет наибольший ранг,
потому что массив отсортирован по возрастанию.
'''
return dicnames[eval(trump)[−1]], trump
5.2. Подсчет карт каждой масти в игре бридж
В карточной игре бридж каждому игроку сдается по тринадцать карт.
В этом задании необходимо подсчитать и вернуть количество карт каждой
масти в порядке {«пики», «червы», «бубны», «трефы»}. Напишите функцию, которая принимает тринадцать карт и возвращает количество карт
каждой масти в порядке {«пики», «червы», «бубны», «трефы»}.
В табл. 5.2 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.2. Некоторые ожидаемые результаты для задачи подсчета карт каждой
масти в игре бридж
Cards
Алгоритм
Чтобы выполнить задание, нужно просто обойти в цикле все сданные
карты и подсчитать количество карт каждой масти в порядке: «пики»,
«червы», «бубны» и «трефы».
В листинге 5.2 приводится код на Python, выполняющий подсчет карт
каждой масти.
Листинг 5.2. Подсчет карт каждой масти
5.3. Получение сокращенного представления карт в раздаче в игре «Контрактный бридж» 171
12
return countinglist
5.3. Получение сокращенного представления
карт в раздаче в игре «Контрактный бридж»
В игре «Контрактный бридж» (или просто бридж) каждому игроку раздается по тринадцать карт. Достоинства этих карт можно сократить для создания более понятного визуального представления. Цель состоит в том,
чтобы найти соответствующие сокращения для каждого достоинства, причем порядок карт всегда следующий: пики (spades), червы (hearts), бубны (diamonds) и трефы (clubs). Для обозначения достоинств используются
следующие символы: «A» обозначает туза (от англ. «ace» – «туз»), «K» – короля (от англ. «king» – «король»), «Q» – даму (от англ. «queen» – «королева»,
или «дама»), «J» – валета (от англ. «jack» – «валет»), и числа обозначают
все остальные достоинства. Ваша задача: написать функцию, которая принимает список из тринадцати карт и возвращает его сокращенную форму
в порядке «AQKJx», где «x» представляет числа, причем числа не требуется
упорядочивать по их величине, а если карты какой-то масти отсутствуют
в раздаче, то в соответствующую позицию должен быть помещен знак «–».
В табл. 5.3 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.3. Некоторые ожидаемые результаты для задачи получения сокращенной
формы представления карт в игре «Контрактный бридж»
Cards
Алгоритм
Алгоритм сначала кодирует достоинства карт каждой масти в виде числовых значений, где тузу присваивается наименьшее значение (0), а числовому достоинству «х» (независимо от его фактической величины) – самое
высокое значение (4). Затем вызывается алгоритм пузырьковой сортировки, чтобы отсортировать карты каждой масти в порядке возрастания их
закодированного значения. И в заключение закодированные значения заменяются соответствующими сокращенными именами карт: «A» для туза,
«K» для «короля» и т. д.
В листинге 5.3 приводится код на Python, получающий сокращенное
представление карт в раздаче.
172
Глава 5. Игры
Листинг 5.3. Получение сокращенного представления карт в раздаче
1 def bubble_sort(arr):
2
for i in range(len(arr) - 1):
3
for j in range(0, (len(arr) - i ) - 1):
4
if arr[j] > arr[j + 1]:
5
# Поменять местами, если необходимо
6
arr[j], arr[j + 1] = arr[j + 1], arr[j]
7
return arr
8 def contract_bridge_game(hand):
9
10
spades = []
11
hearts = []
12
diamonds = []
13
clubs = []
14
'''
15
Закодировать достоинства карт
16
для сортировки на следующем шаге.
17
'''
18
for item in hand:
19
if item[1] == 'spades':
20
if item[0] == 'ace':
21
spades.append('0')
22
elif item[0] == 'king':
23
spades.append('1')
24
elif item[0] == 'queen':
25
spades.append('2')
26
elif item[0] == 'jack':
27
spades.append('3')
28
else:
29
spades.append('4')
30
elif item[1] == 'hearts':
31
if item[0] == 'ace':
32
hearts.append('0')
33
elif item[0] == 'king':
34
hearts.append('1')
35
elif item[0] == 'queen':
36
hearts.append('2')
37
elif item[0] == 'jack':
38
hearts.append('3')
39
else:
40
hearts.append('4')
41
elif item[1] == 'diamonds':
42
if item[0] == 'ace':
5.3. Получение сокращенного представления карт в раздаче в игре «Контрактный бридж» 173
5.4. Наборы карт одинаковой формы
в карточной игре
В этой задаче предлагается считать два набора карт как имеющие одинаковую форму, если они содержат одинаковое количество карт одинаковой масти, пусть и в разном порядке. Например, наборы [6, 3, 2, 2] и [2, 3,
6, 2] имеют одинаковую форму. Ваша задача: написать функцию, которая
принимает список наборов карт и возвращает список кортежей одинаковой формы, при этом содержимое кортежей должно быть отсортировано
по убыванию, а список кортежей – по возрастанию.
В табл. 5.4 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.4. Некоторые ожидаемые результаты для задачи определения наборов
карт одинаковой формы
Cards
[('two', 'hearts'), ('nine', 'spades'), ('two', 'clubs'), ('eight', 'diamonds'),
('queen', 'diamonds'), ('ace', 'clubs'), ('six', 'diamonds'), ('queen', 'hearts'),
('three', 'hearts'), ('queen', 'clubs'), ('ten', 'spades'), ('nine', 'clubs'),
('six', 'spades')], [('five', 'diamonds'), ('jack', 'hearts'), ('three', 'spades'),
('king', 'clubs'), ('two', 'spades'), ('king', 'spades'), ('jack', 'spades'),
('jack', 'diamonds'), ('seven', 'clubs'), ('nine', 'hearts'), ('two', 'hearts'),
('king', 'hearts'), ('eight', 'hearts')], [('queen', 'clubs'), ('jack', 'clubs'),
('two', 'diamonds'), ('nine', 'spades'), ('six', 'clubs'), ('ace', 'clubs'),
('ten', 'diamonds'), ('nine', 'diamonds'), ('three', 'clubs'), ('five', 'hearts'),
('eight', 'spades'), ('six', 'spades'), ('eight', 'hearts')], [('seven', 'spades'),
('ten', 'spades'), ('two', 'hearts'), ('two', 'clubs'), ('jack', 'spades'),
('five', 'spades'), ('queen', 'clubs'), ('king', 'hearts'), ('king', 'clubs'),
('seven', 'diamonds'), ('eight', 'clubs'), ('queen', 'spades'), ('four', 'spades')]]
Алгоритм
Методом линейного поиска определяются масти и вставляются в массив. Затем к массиву применяются сортировки в нужном порядке.
В листинге 5.4 приводится код на Python, определяющий наборы карт
одинаковой формы.
Листинг 5.4. Определение наборов карт одинаковой формы
1 def insertion_sort_descending(arr):
2
for i in range(1, len(arr)):
3
key = arr[i]
4
j= i - 1
5.4. Наборы карт одинаковой формы в карточной игре 175
5
while j >= 0 and key > arr[j]:
6
arr[j + 1] = arr[j]
7
j -= 1
8
arr[j + 1] = key
9
return arr
10 def bubble_sort(arr):
11
for i in range(len(arr) - 1):
12
for j in range(0, (len(arr) - i) - 1):
13
if arr[j] > arr[j + 1]:
14
# Поменять местами,если необходимо
15
arr[j], arr[j + 1] = arr[j + 1], arr[j]
16
return arr
17 def hand_shape_distribution(hands):
18
arr = []
19
arr1 = []
20
for i in range(len(hands)):
21
hand_list = [0, 0, 0, 0]
22
# Подсчет числа вхождений
23
for j in hands[i]:
24
if j[1] == 'spades':
25
hand_list[0] += 1
26
elif j[1] == 'hearts':
27
hand_list[1] += 1
28
elif j[1] == 'diamonds':
29
hand_list[2] += 1
30
elif j[1] == 'clubs':
31
hand_list[3] += 1
32
hand_list = insertion_sort_descending(hand_list)
33
arr.append(hand_list)
34
for i in arr:
35
arr1.append([i, arr.count(i)])
36
# Удалить наборы с отличающейся формой
37
temp_list = []
38
for i in arr1:
39
if i not in temp_list:
40
temp_list.append(i)
41
arr1 = temp_list
42
# Преобразовать в кортеж
43
for j in range(len(arr1)):
44
arr1[j][0] = tuple(arr1[j][0])
45
arr1[j] = tuple(arr1[j])
46
# Отсортировать по возрастанию
47
arr1 = bubble_sort(arr1)
48
return arr1
176
Глава 5. Игры
5.5. Подсчет количества раундов обработки
чисел в порядке возрастания
В этом задании дается массив чисел, возможно несортированный. Массив
заполнен числами от 0 до n – 1. Цель этого задания – подсчитать количество раундов перестановки чисел, необходимых для упорядочения их
в порядке возрастания. В первом раунде обрабатываются числа в порядке возрастания. В последующих раундах обрабатываются числа, которые
не были обработаны в предыдущих раундах, и снова в порядке возрастания. Этот процесс повторяется до тех пор, пока не будут обработаны все
числа в порядке возрастания. Для примера рассмотрим список l = [0, 4, 3, 5,
2, 1]. В первом раунде обрабатываются числа 0 и 1 в порядке возрастания,
во втором раунде – только 2, в третьем раунде – 3 и в четвертом раунде –
4 и 5. Следовательно, для обработки данного списка l в порядке возрастания требуется четыре раунда. Ваша задача: написать функцию, которая
принимает перестановку чисел от 0 до n – 1 и возвращает количество раундов.
В табл. 5.5 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.5. Некоторые ожидаемые результаты для задачи подсчета
раундов обработки чисел в порядке возрастания
Perm
Ожидаемый результат
[0, 1, 5, 4, 2, 3]
3
[0, 1, 2, 4, 3, 5]
2
[4, 11, 2, 8, 6, 9, 5, 3, 0, 10, 1, 12, 7]
6
[0, 1, 4, 3, 2]
3
Алгоритм
Для решения этой задачи используется метод обратной перестановки.
Пусть perm – исходный массив, а inverseperm – массив того же размера, что
и perm, заполненный нулями. Массив inverseperm используется для инверсии заданной перестановки. Для каждого i в perm инструкция inverseperm
[perm [i]] = i инвертирует перестановки. Для подсчета числа раундов определяется счетчик rounds. Первоначально переменной rounds присваивается значение 1, так как всегда существует последовательность чисел
в порядке возрастания, мощность которой равна хотя бы единице. Пусть
n – мощность inverseperm, для k = от 1 до n, если inverseperm [k] < inverseperm
[k – 1], это означает, что k находится слева от k – 1 и количество раундов
должно быть увеличено на единицу.
5.6. Достижение стабильного состояния в распределении конфет 177
В листинге 5.5 приводится код на Python, подсчитывающий количество
раундов для обхода заданной перестановки в порядке возрастания.
Листинг 5.5. Подсчет раундов обработки чисел в порядке возрастания
1 def Number_round_counter(perm):
2
'''
3
perm − это массив с числами
4
от 0 до n - 1
5
'''
6
# Для хранения количества раундов
7
rounds = 1
8
'''
9
Создать массив того же
10
размера, что и массив perm
11
'''
12
inverse_perm = [0] ∗ len(perm)
13
for i in range(len(perm)):
14
'''
15
Инверсия массива perm
16
'''
17
inverse_perm[perm[i]] = i
18
for k in range(1, len(inverse_perm)):
19
'''
20
В массиве inverse_perm,
21
если очередной элемент меньше
22
предыдущего,
23
это означает, что он должен
24
находиться левее предыдущего
25
числа в массиве perm, соответственно,
26
переменную round нужно увеличить на единицу.
27
'''
28
if inverse_perm[k] < inverse_perm[k - 1]:
29
rounds += 1
30
return rounds
5.6. Достижение стабильного состояния
в распределении конфет
Группа детей сидит за круглым столом, и перед ними лежат конфеты. Все
конфеты совершенно одинаковые. Игра начинается с того, что воспитатель звонит в колокольчик. После звонка каждый ребенок, у которого есть
хотя бы две конфеты, должен отдать одну конфету ребенку слева и одну
178
Глава 5. Игры
конфету ребенку справа. Дети, у которых одна конфета или нет конфет,
ничего не должны делать. Согласно принципу Дирихле, если конфет больше, чем детей, то такое деление конфет никогда не завершится. Ваша задача: написать функцию, которая принимает исходное распределение
конфет и возвращает количество шагов, необходимых для достижения
стабильного состояния.
В табл. 5.6 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.6. Некоторые ожидаемые результаты для задачи подсчета
шагов для достижения стабильного состояния в распределении конфет
Candies
Ожидаемый результат
[0, 0, 0, 3]
1
[2, 0, 0, 1]
2
[2, 0, 0, 0, 0, 0, 4, 0, 1]
8
[0, 4, 0, 0, 0, 3, 0, 1, 0, 0]
4
Алгоритм
Алгоритм рекурсивно применяет набор правил ко входному списку
конфет candies, пока не будет достигнуто стабильное состояние, когда
у каждого ребенка окажется не более одной конфеты. В каждой итерации
алгоритм идентифицирует элемент массива, в котором имеются две или
более конфет, и перекладывает по одной конфете в соседние элементы.
Этот процесс повторяется до тех пор, пока во всех элементах будет не более одной конфеты, после чего алгоритм завершает работу и возвращает
количество шагов, потребовавшихся для достижения этого состояния. Вот
подробное описание шагов алгоритма.
1. Принимается два параметра: candies – список целых чисел, представляющий количество конфет, которые есть у каждого ребенка,
и states (необязательный параметр) – целое число, представляющее
количество шагов, потребовавшихся программе для достижения текущего состояния (по умолчанию имеет значение 0).
2. Проверяется, достигнут ли базовый случай. Если количество детей,
имеющих 0 или 1 конфету, равно общему количеству детей, то возвращается количество шагов.
3. Создается копия списка candies для текущего шага.
4. Выполняется обход элементов в списке candies.
5. Проверяется, есть ли у текущего ребенка хотя бы две конфеты. Если
да, то из соответствующего элемента удаляются две конфеты и в со-
5.6. Достижение стабильного состояния в распределении конфет 179
седние элементы добавляется по одной конфете (т. е. передаются детям слева и справа).
6. Вышеуказанные шаги продолжают выполняться рекурсивно с обновленным списком candies и увеличенным значением states.
7. По достижении базового случая возвращается конечное значение states.
В листинге 5.6 приводится код на Python, подсчитывающий количество
шагов для достижения стабильного состояния в распределении конфет.
Листинг 5.6. Подсчет количества шагов для достижения стабильного состояния
в распределении конфет
1 def candy_share(candies, states = 0):
2
'''
3
Возвращает количество
4
шагов, потребовавшихся программе
5
для достижения стабильного состояния.
6
'''
7
# Базовый случай: все дети имеют не более одной конфеты
8
if candies.count(0) + candies.count(1) == len(candies):
9
return states
10
11
# Создать копию списка candies для текущего шага
12
previous_state = candies.copy()
13
14
'''
15
Применить правила
16
игры к каждому ребенку
17
'''
18
for i in range(len(candies)):
19
'''
20
Передавать конфеты соседям
21
должны только дети, имеющие
22
две или более
23
конфет
24
'''
25
if previous_state[i] >= 2:
26
# Уменьшить число конфет у текущего ребенка
27
candies[i] -= 2
28
29
# И передать их соседям слева и справа
30
candies[(i - 1) % len(candies)] += 1
180
31
32
33
34
Глава 5. Игры
candies[(i + 1) % len(candies)] += 1
# Выполнить рекурсивный вызов с обновленными параметрами candies и states
return candy_share(candies, states + 1)
5.7. Игра вари
Вари (оваре) 1 – африканская настольная игра со множеством вариаций, самая популярная, пожалуй, из семейства игр манкала. В игре используется
игровая доска с двумя рядами лунок. Игроки могут «засевать» и «захватывать» семена в лунках. В этом задании дается доска с 2n лунками (домами).
Первый ряд с n лунками принадлежит первому игроку, а второй – второму.
Первоначально в каждой лунке находится определенное количество семян
и их нужно собрать. Если в лунке находятся 2 или 3 семени, то их можно
захватить. Рассмотрим раунд игры на примере. Пусть дана доска board =
[0, 2, 1, 2] и дом house = 1. Нужно вывести массив, отражающий изменения
после сбора семян. Первая фаза – сбор урожая и посев – начинается с позиции house + 1 и продолжается до индекса board [house] (т. е. выполняется
столько шагов, сколько семян в лунке board [house + 1]). Значение board
[house] обнуляется (из лунки извлекаются два зерна), поэтому board = [0, 0,
1, 2]. Далее одно зерно засевается во второй элемент (напомню, что счет
начинается с 0), поэтому board = [0, 0, 2, 2], и еще одно зерно засевается
в третий элемент, поэтому board = [0, 0, 2, 3]. Вторая и третья лунки содержат 2 и 3 зерна соответственно, поэтому они захватываются. В результате
на выходе получается массив board = [0, 0, 0, 0] и игра завершается.
Ваша задача: написать функцию, которая принимает доску и возвращает массив, показывающий изменения после сбора урожая и посева.
В табл. 5.7 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.7. Некоторые ожидаемые результаты для задачи
определения состояния игровой доски в африканской игре вари
1
Board, house
Ожидаемый результат
[2, 1, 2, 0], 1
[2, 0, 0, 0]
[1, 4, 5, 6], 1
[2, 0, 7, 7]
[7, 7, 7, 68, 0, 1, 0], 3
[18, 18, 18, 0, 0, 1, 1]
[2, 0, 7, 7], 1
[2, 0, 7, 7]
Подробное описание правил игры вы найдете в Википедии: https://ru.wikipedia.org/wiki/Вари_ (игра). –
Прим. перев.
5.7. Игра вари 181
Алгоритм
Алгоритм использует циклы while и for для обхода игровой доски, посева семян в дома и захвата семян противника, если это возможно.
1. Принимается список board, представляющий текущее состояние
игровой доски, и целое число house, представляющее индекс лунки –
дом, – откуда начинаются сбор урожая и посев.
2. Определяется индекс last_index последнего дома на доске вычитанием 1 из длины списка board.
3. Количество семян в выбранном доме сохраняется в переменной seeds_to_sow.
4. В переменную current_index (текущий индекс) записывается индекс
дома, следующего за выбранным.
5. Количество семян в выбранном доме устанавливается равным 0.
6. Пока значение seed_to_sow больше 0, выполняются следующие действия:
а) если текущий индекс (current_index) выходит за пределы последнего индекса, то выполняется переход к первому индексу;
б) если текущий индекс равен индексу дома, откуда были извлечены семена для посева, то этот индекс пропускается;
в) в текущий дом добавляется одно семя;
г) количество семян для посева (seed_to_sow) уменьшается на единицу;
д) выполняется переход к следующему дому увеличением текущего
индекса (current_index) на единицу;
е) по достижении последнего дома в своем ряду происходит переход к последнему дому в ряду противника и движение продолжается от конца к началу ряда;
ж) для каждого дома в ряду противника выполняются следующие
действия:
i) если в доме 2 или 3 семени, то они захватываются и их количество в доме устанавливается равным нулю;
ii) если семян в доме противника больше, то они не захватываются.
7. Возвращается обновленный список board.
В листинге 5.7 приводится код на Python, определяющий состояние
игровой доски в африканской игре вари.
182
Глава 5. Игры
Листинг 5.7. Определение состояния игровой доски в африканской игре вари
1 def oware_game(board, house):
2
# Определить последний индекс массива board
3
last_index = len(board) − 1
4
# Сохранить количество семян в выбранном доме
5
seeds_to_sow = board[house]
6
# Запомнить индекс следующего дома как текущий
7
current_index = house + 1
8
# Обнулить количество семян в выбранном доме
9
board[house] = 0
10
# Выполнить посев семян в последующие дома
11
while seeds_to_sow > 0:
12
'''
13
Если текущий индекс
14
превысил последний индекс,
15
то вернуться к первому индексу
16
'''
17
if current_index > last_index:
18
current_index = 0
19
# Пропустить начальный дом, откуда были взяты семена для посева
20
if current_index == house:
21
current_index += 1
22
# Добавить одно семя в текущий дом
23
board[current_index] += 1
24
# Уменьшить число семян для посева на единицу
25
seeds_to_sow -= 1
26
# Перейти к следующему дому
27
current_index += 1
28
29
# Захватить семена противника, если возможно
30
end_index = current_index − 1
31
if end_index >= len(board) / 2:
32
for i in range(end_index, len(board) // 2 - 1, -1):
33
'''
34
Если в доме противника 2 или 3 семени,
35
то захватить их и обнулить
36
количество семян в доме
37
'''
38
if board[i] in (2, 3):
39
board[i] = 0
40
'''
41
Если семян больше, то
5.8. Количество безопасных полей на шахматной доске с ладьями 183
5.8. Количество безопасных полей
на шахматной доске с ладьями
Ладья – это шахматная фигура, и позиция каждой ладьи представлена
парой (горизонталь, вертикаль), где горизонтали и вертикали пронумерованы от 0 до n – 1. Ладьи могут атаковать фигуры, стоящие на одной
с ними горизонтали или вертикали. Цель этой задачи – определить набор безопасных полей на шахматной доске, где ни одна ладья не сможет
атаковать их. Напишите функцию, которая принимает координаты ладей
в виде списка кортежей и размер шахматной доски и возвращает коли
чество безопасных полей.
В табл. 5.8 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.8. Некоторые ожидаемые результаты для задачи определения
безопасных полей на шахматной доске с ладьями
n, rooks
Ожидаемый результат
10, [(2, 3), (4, 4)]
64
91, [(1,1), (4,4), (3, 5), (0, 7)]
7569
20, [(1,0), (3,6), (11, 5), (1, 2)]
272
7, [(0,2), (3,9), (3, 4)]
20
Алгоритм
Пусть rooks – список ладей, а n – размер шахматной доски. Для каждого i в rooks алгоритм сохраняет i[0] в массиве Unsaferow и i[1] в массиве Unsafecol. На следующем шаге он получает количество безопасных горизонталей и вертикалей как safedrow = n – len(set(Unsaferow)) и safecol =
n – len(set (Unsafecol)) соответственно. На последнем шаге подсчитывается
число безопасных полей как safedrow * safecol.
В листинге 5.8 приводится код на Python, вычисляющий количество
безопасных полей на шахматной доске.
184
Глава 5. Игры
Листинг 5.8. Определение количества безопасных полей на шахматной доске
с ладьями
1 def Safe_Squares_Rooks_of_Chessboard(n, rooks):
2
Unsafe_squares_in_rows = []
3
Unsafe_squares_in_columns = []
4
for i in rooks:
5
Unsafe_squares_in_rows.append(i[0])
6
Unsafe_squares_in_columns.append(i[1])
7
# Чтобы исключить повторяющиеся числа, используется множество
8
safed_rows = n - len(set(Unsafe_squares_in_rows))
9
# Чтобы исключить повторяющиеся числа, используется множество
10
safed_columns = n - len(set(Unsafe_squares_in_columns))
11
# Получить количество безопасных полей
12
safe = safed_rows * safed_columns
13
return safe
5.9. Количество безопасных полей
на шахматной доске со слонами
Дано: шахматная доска n×n с несколькими слонами на ней, где горизонтали и вертикали пронумерованы от 0 до n – 1. Слоны могут двигаться только
по диагонали. Слоны могут атаковать фигуры, стоящие на одной с ними
диагонали. Напишите функцию, которая в качестве входных данных принимает координаты слонов в виде списка кортежей и размер шахматной
доски и возвращает количество безопасных полей.
В табл. 5.9 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.9. Некоторые ожидаемые результаты для задачи определения
безопасных полей на шахматной доске со слонами
n, bishops
Ожидаемый результат
10, [(2, 3), (4,4)]
68
91, [(1,1), (4,4), (3, 5), (0, 7)]
8002
20, [(1,0), (3,6), (11, 5), (1, 2)]
307
7, [(0,2), (3,9), (3, 4)]
29
Алгоритм
Алгоритм принимает размер шахматной доски n и список bishops координат слонов на доске. Он вычисляет количество безопасных полей на дос
5.9. Количество безопасных полей на шахматной доске со слонами 185
ке, то есть количество полей, которые не заняты слонами или не находятся
под угрозой атаки со стороны слона. Алгоритм сначала инициализирует
переменную safe_squares значением 0, которая затем будет использоваться для подсчета количества безопасных полей. Далее он создает два мно
жества: diagonal1 и diagonal2 – для хранения полей на каждой диагонали,
находящейся под угрозой атаки.
Для каждого слона на доске алгоритм вычисляет индексы полей на двух
диагоналях, где расставлены слоны, и добавляет их в соответствующие
множества diagonal1 и diagonal2. Наконец, алгоритм перебирает все поля
на доске и проверяет, занято ли каждое поле слоном на той же диагонали
или находится под угрозой. Если поле не занято и не находится под угрозой атаки слоном, то количество безопасных полей увеличивается на 1.
На выходе алгоритм возвращает количество безопасных полей.
В листинге 5.9 приводится код на Python, вычисляющий количество
безопасных полей на шахматной доске со слонами.
Листинг 5.9. Определение количества безопасных полей на шахматной доске
со слонами
1 def Safe_Squares_not_Threaten_with_Bishops(n, bishops):
2
safe_squares = 0
3
4
# Для сохранения полей на каждой диагонали
5
# множество полей на первой диагонали, находящихся под угрозой
6
diagonal1 = set()
7
# множество полей на второй диагонали, находящихся под угрозой
8
diagonal2 = set()
9
# Обойти список слонов и обновить множества, представляющие диагонали
10
11
for bishop in bishops:
12
# добавить поле в diagonal1
13
diagonal1.add(bishop[0] + bishop[1])
14
# добавить поле в diagonal2
15
diagonal2.add(bishop[0] - bishop[1])
16
17
# Подсчитать количество безопасных полей
18
for i in range(n):
19
for j in range(n):
20
if i + j not in diagonal1 \
21
and i - j not in diagonal2:
22
# увеличить счетчик безопасных полей
23
safe_squares += 1
24
return safe_squares
186
Глава 5. Игры
5.10. Достижимость поля для коня
в многомерных шахматах
Обычная шахматная доска имеет два измерения, но ее можно расширить
до k измерений. На двумерной шахматной доске конь может перемещаться на одно из восьми полей на плоской доске, а на многомерной шахматной доске он может перемещаться в поля в других измерениях. Цель этой
задачи – определить, сможет ли конь, для которого определено количест
во полей, пересекаемых в каждом направлении, достичь заданного поля
на шахматной доске, исходя из начальных и конечных координат. Координаты представлены кортежами отрицательных или неотрицательных
целых чисел. Например, для коня, который выполняет шаги (2, 1, 7) в трех
измерениях, нужно определить, сможет ли конь прыгнуть из поля с координатами (3, 5, 9) в поле с координатами (8, 11, 13).
В табл. 5.10 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.10. Некоторые ожидаемые результаты для задачи определения
достижимости поля для коня в многомерных шахматах
Knight, start, end
Ожидаемый результат
(2, 1, 7), (3, 5, 9), (8, 11, 13)
False
(3, 4, 2), (3, 5, 9), (1, 7, 9)
False
(2, 1), (12, 10), (11, 12)
True
(10, 5, 1), (20, 11, 16), (10, 12, 11)
True
Алгоритм
Алгоритм вычитает каждое значение в кортеже start из каждого значения в кортеже end и сохраняет абсолютные значения. Для нашего примера
абсолютные разности |3–8 |, |5–11 | и |9–13 | равны (5, 6, 4) соответственно. Структура хода коня должна в точности соответствовать результатам
вычитания. Следовательно, поскольку (2, 1, 7) не совпадает с полученным
результатом (5, 6, 4), можно сделать вывод, что поле (8, 11, 13) недостижимо для коня, находящегося в поле (3, 5, 9) и выполняющего перемещение (2, 1, 7) по каждому из измерений. Следует отметить, что если c является результатом вычитания, то c необходимо отсортировать в порядке
убывания. Напишите функцию, которая принимает структуру хода коня,
начальную и конечную координаты и возвращает True, если конь сможет
прыгнуть из поля start в поле end, в противном случае возвращает False.
Вот подробное описание шагов алгоритма.
5.10. Достижимость поля для коня в многомерных шахматах 187
1. Принимается три аргумента: структура хода knight, начало start
и конец end. Возвращает True, если конь может прыгнуть из поля start
в поле end, и False в противном случае.
2. Создается пустой список с именем list_numbers.
3. Выполняется обход элементов в start и end позиции и вычисляется
абсолютная разность соответствующих элементов.
4. Эти разности добавляются в list_numbers.
5. Список list_numbers сортируется в порядке убывания с использованием bubble_sort.
6. Выполняется обход элементов в списке knight. Если какой-то элемент
в knight отсутствует в list_numbers, то это означает, что конь не может
достичь конечного поля. В этом случае функция возвращает False.
7. Если элементы в knight присутствуют в list_numbers, то это означает,
что конь может достичь целевого поля. В этом случае функция возвращает True.
В листинге 5.10 приводится код на Python, определяющий достижимость
поля для коня в многомерных шахматах.
Листинг 5.10. Определение достижимости поля для коня в многомерных шахматах
'''
Выполняет пузырьковую сортировку входного массива
и возвращает массив, отсортированный в порядке убывания
'''
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] < arr[j + 1]:
'''
Поменять два элемента местами,
если они стоят в неправильном порядке
'''
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
'''
Определяет, сможет ли конь прыгнуть
в заданную позицию на k-мерной шахматной доске
'''
def reaching_knight_jump(knight, start, end):
'''
# Создать пустой список для хранения разностей
координат между начальной и конечной позициями
'''
list_numbers = []
for i in range(len(start)):
'''
# Вычислить абсолютные разности между
элементами start и end
и добавить их в list_numbers
'''
list_numbers.append(abs(start[i] - end[i]))
# Отсортировать список разностей в порядке убывания
list_numbers = bubble_sort(list_numbers)
for num in knight:
'''
Если какой-то элемент в knight
отсутствует в list_numbers,
значит, конь не сможет
прыгнуть в указанную позицию
'''
if num not in list_numbers:
return False
'''
Иначе вернуть True и тем самым показать,
что конь сможет прыгнуть в указанное поле
'''
return True
5.11. Захват максимального количества шашек
на шахматной доске
Среди настольных игр на шахматной доске n×n с черными и белыми полями широко известна игра в шашки. Она предполагает взятие фигур противника. Игроки поочередно делают ходы, перемещая шашки насоседнее
поле по диагонали, причем фигуры всегда должны оставаться на белых
полях и не могут двигаться назад. Если две фигуры разного цвета соседствуют по диагонали, то игрок, кому выпал черед делать следующий ход,
может перепрыгнуть через фигуру противника и взять ее, при условии что
позади фигуры противника есть свободное белое поле. Если у игрока есть
возможность взять фигуру противника, он должен это сделать, а если есть
возможность последовательно взять несколько фигур, то игрок должен
взять их все. Игрок, потерявший все фигуры, считается проигравшим. Цель
5.11. Захват максимального количества шашек на шахматной доске 189
этого задания состоит в том, чтобы взять максимальное количество фигур
противника за один ход. Ход со взятием фигуры противника, находящейся по соседству на диагонали, может выполняться только в направлениях
(1, 1), (1, –1), (–1, 1) и (–1, –1). Ваша задача: написать функцию, которая
принимает размер шахматной доски, координату фигуры, выполняющей
ход, и координаты фигур противника и возвращает количество фигур, взятых за один ход.
В табл. 5.11 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 5.11. Некоторые ожидаемые результаты для задачи определения
максимального количества шашек на шахматной доске, которые можно взять
из текущей позиции
n, x, y, pieces
Алгоритм
Алгоритм принимает размер шахматной доски n, координаты x и y фигуры, выполняющей ход, множество pieces c координатами фигур противника и возвращает количество взятых фигур. Для исследования всех
возможных ходов из текущего состояния алгоритм использует поиск
в ширину. Он инициализирует множество visited посещенных полей, чтобы отслеживать поля, посещавшиеся во время поиска в ширину, и очередь
queue, содержащую начальное состояние. Он также инициализирует текущее максимальное число взятых фигур. Затем алгоритм входит в цикл
while и удаляет следующее возможное состояние из очереди. Он обновляет текущее максимальное количество фигур, взятых в этом состоянии.
Для каждого возможного направления движения по диагонали алгоритм
вычисляет новую позицию и позицию взятой фигуры. Если алгоритм находит новое состояние со взятой фигурой, он создает новое множество фигур без взятой фигуры и проверяет, посещалось ли уже это состояние. Если
нет, то алгоритм добавляет новое состояние в множество посещавшихся
состояний в очередь queue. Поиск производится до тех пор, пока очередь
не опустеет, после чего возвращается текущее максимальное количество
взятых фигур.
В листинге 5.11 приводится код на Python, определяющий максимальное количество шашек на шахматной доске, которые можно взять из текущей позиции.
190
Глава 5. Игры
Листинг 5.11. Определение максимального количества шашек на шахматной доске,
которые можно взять из текущей позиции
'''
Эта функция добавляет элемент
в конец очереди
'''
def enqueue(queue, item):
queue.append(item)
'''
Эта функция удаляет и возвращает
первый элемент из очереди
'''
def dequeue(queue) :
return queue.pop(0)
'''
Эта функция проверяет наличие элементов в очереди
'''
def is_empty(queue) :
return len(queue) == 0
'''
Эта функция отыскивает максимальное число
фигур, которые можно взять
'''
'''
одной шашкой, находящейся в позиции (x, y)
на шахматной доске n x n,
'''
'''
принимает позиции фигур противника
в множестве pieces
'''
'''
и количество уже взятых
фигур в множестве removed.
'''
def Capturing_Max_Checkers(n, x, y, pieces, removed = 0):
'''
Для отслеживания возможных состояний
используется множество visited
5.11. Захват максимального количества шашек на шахматной доске 191
'''
visited = set ()
'''
Поиск начинается с начальной позиции,
находящейся в очереди queue
'''
queue = [(x, y, pieces, removed)]
'''
Инициализировать текущий максимум
количеством уже взятых
фигур
'''
current_max = removed
'''
Продолжать поиск в ширину,
пока очередь не опустеет
'''
while not is_empty(queue):
'''
Извлечь из очереди очередное состояние
'''
x, y, pieces, removed = dequeue(queue)
'''
Обновить текущий максимум
максимальным количеством
фигур, взятых
к настоящему моменту
'''
current_max = max(current_max, removed)
# Для каждой возможной диагонали
for dx, dy in [(1, 1), (-1, 1), (1, -1), (-1, -1)]:
'''
Вычислить новую позицию фигуры
после выполнения хода
'''
new_x, new_y = x + 2 * dx, y + 2 * dy
jump_x, jump_y = x + dx, y + dy
'''
Если новая позиция оказалась за пределами доски,
то пропустить это направление
elif animals[current_animal_index] in ["tac", "god"]:
'''
инициализировать нулем количество
кошек правее в списке
'''
num_cats = 0
'''
инициализировать нулем количество
собак правее в списке
'''
num_dogs = 0
'''
начать проверку животных
в списке, находящихся правее текущего
'''
next_animal_index=\
current_animal_index + 1
'''
подсчитать количество кошек и собак,
находящихся правее в списке
'''
while next_animal_index < len(animals):
if animals[next_animal_index]=="cat" \
or animals[next_animal_index]=="tac":
num_cats += 1
elif animals[next_animal_index]=="dog" \
or animals[next_animal_index]=="god" :
num_dogs += 1
next_animal_index += 1
'''
Если после текущего животного
собак больше, чем кошек,
то увеличить счетчик рычащих животных
'''
if num_dogs > num_cats:
num_growlers += 1
# Перейти к следующему животному
current_animal_index += 1
# Вернуть общее количество рычащих животных
return num_growlers
208
Глава 6. Счет
6.3. Подсчет количества способов выражения
вежливого числа
В теории чисел положительные целые числа, которые можно выразить
в виде суммы двух или более последовательных чисел, называются вежливыми числами. С другой стороны, положительные целые числа, которые нельзя выразить подобным образом, называются невежливыми. Важно отметить, что вежливые и невежливые числа относятся к категории
натуральных чисел. Целью этой задачи является подсчитать количество
способов, которыми вежливое число можно выразить в виде суммы последовательных положительных целых чисел. Например, число 42 можно
выразить как
а)
б)
в)
г)
А число 3 – как 2 + 1 и 3. Ваша задача: написать функцию, которая принимает положительное целое число n и возвращает количество способов,
которыми это число можно выразить в виде суммы последовательных положительных целых чисел.
В табл. 6.3 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 6.3. Некоторые ожидаемые результаты для задачи
подсчета количества способов выражения вежливого числа
n
Ожидаемый результат
3
2
96000
8
2
1
42
4
Алгоритм
Алгоритм подсчитывает количество делителей числа n, что эквивалентно количеству способов, которыми n можно выразить в виде суммы последовательных положительных целых чисел.
1. Принимается положительное целое число.
2. Инициализируется переменная NumberofPolites значением 0.
6.4. Подсчет вхождений каждой цифры 209
3. В цикле выполняется перебор чисел в диапазоне от 1 до n + 1.
4. Для каждого целого числа i в цикле:
а) проверяется нечетность i и делится ли n на i;
б) если оба условия выполняются, то переменная NumberofPolites,
представляющая количество нечетных делителей, увеличивается на 1.
5. NumberofPolites возвращается как результат.
В листинге 6.3 приводится код на Python, решающий задачу подсчета
количества способов выражения вежливого числа.
Листинг 6.3. Подсчет количества способов выражения вежливого числа
1 def count_consecutive_summers(n):
2
NumberofPolites = 0
3
for i in range(1, n + 1):
4
if n % i == 0 and i % 2 == 1:
5
NumberofPolites += 1
6
return NumberofPolites
6.4. Подсчет вхождений каждой цифры
Дана строка, содержащая только цифры «0123456789». Требуется подсчитать количество вхождений подряд каждой цифры и представить эту информацию в виде «количество–цифра». Например, для входной строки
«222274444499966» результатом будет строка «4217543926». Она означает:
«четыре двойки, одна семерка, пять четверок, три девятки и две шестерки».
Ваша задача: написать функцию, которая принимает строку цифр и возвращает строку с цифрами в исходной строке и количеством вхождений
подряд каждой цифры.
В табл. 6.4 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 6.4. Некоторые ожидаемые результаты для задачи
подсчета вхождений каждой цифры
Digits
Ожидаемый результат
'7779981'
'37291811'
'1333334'
'115314'
'2115131114'
'12211511133114'
'37291811'
'13171219111821'
210
Глава 6. Счет
Алгоритм
Алгоритм принимает строку с цифрами и выполняет итерации, подсчитывая количество одинаковых цифр, следующих подряд, в переменной
count. Когда встречается другая цифра, он добавляет количество вхождений и саму цифру в список с именем orders и сбрасывает счетчик в 1.
В завершение он возвращает представление исходной строки, полученное
в orders.
В листинге 6.4 приводится код на Python, решающий задачу подсчета
количества вхождений каждой цифры.
Листинг 6.4. Подсчет количества вхождений каждой цифры
1 def Count_occurrence_of_each_digit(digits):
2
orders = []
3
count = 1
4
previous_digit = digits [0]
5
6
'''
7
Цикл по цифрам в исходной строке
8
с подсчетом вхождений каждой цифры
9
'''
10
for current_digit in digits[1:]:
11
if current_digit == previous_digit:
12
count += 1
13
else:
14
'''
15
Добавить количество вхождений цифры
16
и ее саму в результат
17
'''
18
orders.append(str(count))
19
orders.append(previous_digit)
20
count = 1
21
previous_digit = current_digit
22
23
'''
24
Добавить счетчик и последнюю цифру
25
в результат
26
'''
27
orders.append(str(count))
28
orders.append(previous_digit)
29
return ''.join(orders)
6.5. Подсчет количества максимальных слоев на двумерной плоскости 211
6.5. Подсчет количества максимальных слоев
на двумерной плоскости
Точка на двумерной плоскости с координатами (x1, y1) доминирует над точкой (x2, y2), если x1 > x2 и y1 > y2. Если над точкой не доминирует никакая другая
точка, то она считается максимальной, причем на двумерной плоскости
может иметься произвольное количество точек, образующих максимальный слой. Цель этого задания: подсчитать количество максимальных слоев. Например, пусть дан список точек points = [(1, 5), (3, 10), (2, 1), (9, 2)]
и для него нужно подсчитать количество максимальных слоев. Входные
данные просматриваются слева направо, точка (1, 5) не является максимальной, потому что над ней доминирует точка (3, 10), т. е. 3 > 1 и 10 > 5.
Следующая рассматриваемая точка – точка (3, 10), это максимальная точка, потому что над ней не доминирует никакая другая точка: для пары (1, 5)
и (3, 10) 1 не больше 3 и 5 не больше 10, для пары (2, 1) и (3, 10) 2 не больше 3 и 1 не больше 10, и для пары (9, 2) и (3, 10) 9 больше 3, но 2 не больше 10.
Следующей рассматривается точка (2, 1), и она не является максимальной,
потому что над ней доминирует точка (3, 10). Следующая точка – (9, 2) – является максимальной, потому что над ней, как и над (3, 10), не доминирует
никакая другая точка. Следовательно, в списке points = [(1, 5), (3, 10), (2, 1),
(9, 2)] есть два максимальных слоя, один из них образован точкой (10, 3),
а другой – точкой (9, 2). Ваша задача: написать функцию, которая принимает список точек и возвращает количество максимальных слоев.
В табл. 6.5 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 6.5. Некоторые ожидаемые результаты для задачи подсчета
количества максимальных слоев на двумерной плоскости
Points
Ожидаемый результат
[(7, 1), (6, 9)]
1
[(11, 4), (1, 1), (11, 1)]
2
[(1, 5), (3, 10), (2, 1), (9, 2)]
2
[(796, 1024), (11, 13), (19, 221), (700, 3)]
3
Алгоритм
Алгоритм принимает список точек points и подсчитывает количество
максимальных слоев. Он циклически перебирает точки в списке и проверяет, является ли каждая точка максимальной (т. е. нет ли других точек
с большими координатами x и y). Если точка максимальна, она добавляется в список максимальных точек. После выявления всех максимальных
212
Глава 6. Счет
точек функция увеличивает счетчик layerCounter и удаляет максимальные
точки из исходного списка. Цикл продолжается до тех пор, пока в списке
не останется точек и не будет получено окончательное количество слоев.
В листинге 6.5 приводится код на Python, подсчитывающий количество
максимальных слоев.
Листинг 6.5. Подсчет количества максимальных слоев
1 def count_maximal_layers_in_points(points_list):
2
# Инициализировать счетчик слоев значением 0
3
layer_count = 0
4
5
# Цикл, пока points_list не опустеет
6
while points_list:
7
# Отыскать все максимальные точки в списке
8
maximal_points = []
9
for point in points_list:
10
is_maximal = True
11
for other_point in points_list:
12
if other_point[0] > point[0] \
13
and other_point[1] > point[1]:
14
is_maximal = False
15
break
16
if is_maximal:
17
maximal_points.append(point)
18
19
'''
20
Увеличить layer_count на 1,
21
если есть хотя бы одна максимальная точка
22
'''
23
if maximal_points:
24
layer_count += 1
25
26
'''
27
Удалить все максимальные точки
28
из исходного списка
29
'''
30
for point in maximal_points:
31
points_list.remove(point )
32
33
# Вернуть количество максимальных слоев
34
return layer_count
6.6. Подсчет количества доминирующих чисел 213
6.6. Подсчет количества доминирующих чисел
Число в списке считается доминирующим, если числа справа от него меньше. Цель этого задания – найти количество доминирующих чисел в заданном списке. Согласно определению, последний элемент списка всегда
является доминирующим. Например, рассмотрим список items = [–492,
124, 113, –38, –28, –15]. Мы видим, что число 124 является доминирующим,
потому что оно больше, чем 113, –38, –28 и –15. Элемент 113 тоже является доминирующим, потому что он больше, чем –38, –28 и –15. Наконец,
последний элемент –15 тоже является доминирующим. Следовательно,
количество доминирующих чисел в этом списке равно трем. Если на вход
подается пустой список, то должно быть возвращено число 0.
В табл. 6.6 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 6.6. Некоторые ожидаемые результаты для задачи подсчета
количества доминирующих чисел
items
Ожидаемый результат
[-492, 124, 113,–38,–28,–15]
3
[77, 1, 2,–4, 13, 7, 9, 1]
4
[13, 7, 9, 1, 77, 1, 2,–4]
3
[77, 1, 2,–4, 13, 77, 7, 9, 1]
3
Алгоритм
1. Принимается список целых чисел.
2. Если список пустой, то возвращается 0.
3. Переменная max_num инициализируется значением «отрицательной бесконечности», а переменная dominator_count – значением 0.
4. Цикл по элементам списка в обратном порядке.
5. Для каждого числа в списке проверяется, больше ли оно max_num.
6. Если больше, то в max_num записывается значение текущего элемента и dominator_count увеличивается на 1.
7. После перебора всех элементов списка возвращается dominator_
count.
В листинге 6.6 приводится код на Python, подсчитывающий количество
доминирующих чисел.
214
Глава 6. Счет
Листинг 6.6. Подсчет количества доминирующих чисел
# Перевернуть список
def reverse_list(lst):
'''
создать пустой список для
сохранения элементов в обратном порядке
'''
reversed_lst = []
'''Цикл по элементам
в обратном порядке
'''
for i in range(len(lst) - 1, -1, -1):
reversed_lst.append(lst[i])
# Вернуть перевернутый список
return reversed_lst
"""
Подсчитывает количество доминирующих чисел
в заданном списке целых чисел.
"""
def Counting_Dominator_Numbers(items):
# Если список пуст, то вернуть 0
if not items:
return 0
'''
В языке -inf представляет отрицательную бесконечность.
'''
max_num = float('-inf')
# Инициализировать счетчик доминирующих чисел
dominator_count = 0
# Цикл по перевернутому списку элементов
for num in reverse_list(items):
'''
если текущее число больше максимального,
встреченного до сих пор
'''
if num > max_num:
# Сохранить его как текущее максимальное
max_num = num
# Увеличить счетчик доминирующих чисел
dominator_count += 1
6.7. Подсчет количества троек чисел 215
42
43
# Вернуть количество доминирующих чисел
return dominator_count
6.7. Подсчет количества троек чисел
Пусть items – список чисел такой, что элементы этого списка в позициях i < j < k составляют тройку, если items [i] == items [j] == items [k] и j – i == k – j.
Например, подсчитаем количество троек в списке items = [42, 9, 42, 42, 42,
103]. В 0‑й, 2‑й и 4‑й позициях находятся числа 42, 42 и 42 соответственно,
при этом 2 – 0 = 4 – 2, т. е. 2 = 2. Числа в этих позициях образуют тройку.
Другая тройка образуется числами в 2‑й, 3‑й и 4‑й позициях, потому что
3 – 2 = 4 – 3, т. е. 1 = 1. Таким образом, в рассматриваемом списке имеются
две тройки. Ваша задача: написать функцию, которая принимает список
положительных и отрицательных целых чисел и возвращает количество
троек в нем.
В табл. 6.7 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 6.7. Некоторые ожидаемые результаты для задачи подсчета троек
items
Алгоритм
Пусть функция TroikaCounter – это функция, подсчитывающая коли
чество троек в списке items. Для проверки условия j – i == k – j она проверяет состояние items [i] == items [j] == items [2 * j – i] для каждого i в диапазоне от 0 до |items| и для каждого j в диапазоне от i + 1 до |items|. Если
условие items [i] == items [j] == items [2 * j – i] выполняется и числа во всех
трех позициях одинаковые (третья позиция определяется выражением
(2 * j – i)), то счетчик TroikaCounter увеличивается на единицу. В завершение функция возвращает TroikaCounter как количество троек.
В листинге 6.7 приводится код на Python, подсчитывающий количество
троек в списке.
Листинг 6.7. Подсчет количества троек в списке
1 def TroikaCounter(items):
2
TroikaCounter = 0
216
3
4
5
6
7
8
9
10
11
Глава 6. Счет
for i in range(len(items)):
for j in range(i + 1, len(items)):
k = 2 * j - i
if k > (len(items) - 1):
pass
else:
if items[i] == items[j] == items[k]:
TroikaCounter += 1
return TroikaCounter
6.8. Подсчет пар пересекающихся кругов
На двумерной плоскости существуют круги (x1, y1, r1) и (x2, y2, r2), где (x, y) –
это координаты центра круга, а r – радиус. Если для них выполняется неравенство Пифагора (x2 – x1) ** 2 + (y2 – y1) ** 2 0:
30
top_frequency_items.append(item)
31
top_frequency_dict[item] -= 1
32
return top_frequency_items
7.4. Когда две лягушки встретятся в одном
квадрате
Две лягушки, находясь в разных местах, начинают прыгать каждая в своем
направлении. Информация о каждой лягушке представлена кортежем (sx,
sy, dx, dy), где (sx, sy) обозначает начальные координаты, а (dx, dy) – постоянный вектор, определяющий направление и расстояние для каждого последующего прыжка. Проще говоря, обе лягушки представлены как Frog1
(sx1, sy1, dx1, dy1) и Frog2 (sx1, sy1, dx1, dy1). В этом задании нужно найти
время, когда обе лягушки окажутся в одном и том же квадрате. Напишите
функцию, которая принимает два кортежа, описывающих лягушек, и возвращает время, когда обе лягушки окажутся в одном квадрате. Если лягушки никогда не окажутся в одном квадрате одновременно, то функция
должна вернуть None.
В табл. 7.4 показаны ожидаемые результаты для некоторых входных
данных.
7.4. Когда две лягушки встретятся в одном квадрате 225
Таблица 7.4. Некоторые ожидаемые результаты для задачи определения
времени встречи двух лягушек
Frog1, frog2
Ожидаемый результат
(562,–276,–10, 5), (49,–333,–1, 6)
57
(-3525,–877, 4, 1), (-4405, 2643, 5,–3)
880
(2726,–3200,–6, 7), (-2290, 2272, 5,–5)
456
(1591,–1442,–10, 9), (-329,–962, 2, 6)
160
Алгоритм
Алгоритм принимает два аргумента, frog1 и frog2, представляющих начальные координаты и векторы движения двух лягушек. Алгоритм использует эту информацию, чтобы определить время встречи лягушек.
В листинге 7.5 приводится код на Python, определяющий время встречи
двух лягушек.
Листинг 7.5. Определение времени встречи двух лягушек
1 def Collision_time_of_frogs(frog1, frog2):
2
'''
3
На основе frog1(sx1,sy1, dx1, dy1) и
4
frog2(sx1, sy1, dx1, dy1) заполнить
5
переменные с исходными данными.
6
'''
7
sx1 = frog1[0]
8
sx2 = frog2[0]
9
sy1 = frog1[1]
10
sy2 = frog2[1]
11
dx1 = frog1[2]
12
dx2 = frog2[2]
13
dy1 = frog1[3]
14
dy2 = frog2[3]
15
16
tx=0
17
ty=0
18
'''
19
1:
20
Если компоненты векторов движения равны нулю
21
(dx1==dx2==0 и dy1==dy2==0), то это означает,
22
что лягушки вообще не движутся:
23
Если при этом лягушки первоначально находятся
в одной точке, то нужно вернуть
ноль, т. е. время до встречи равно нулю,
так как лягушки уже встретились, не начав движения.
Иначе, если лягушки находятся в разных точках,
они никогда не встретятся, и нужно вернуть
None.
'''
if dx1 == dx2 == 0 and dy1 == dy2 == 0:
if sx1 == sx2 and sy1 == sy2:
t = 0
return t
else:
t = None
return t
'''
2:
Если векторы движения определяют смещение вдоль
оси y и (dx1 == dx2 == 0), то вычислить
позицию y точки встречи:
Если ty недробное число
и положительное, то вернуть ty.
Иначе, если предыдущие условия не выполняются,
вернуть None.
'''
if dx1 == dx2 == 0:
ty = (sy2 - sy1) / (dy1 - dy2)
if int(ty) == ty and ty > 0:
t = int(ty)
else:
t = None
return t
'''
3:
Если векторы движения определяют смещение вдоль
оси x и (dy1 == dy2 == 0),
позицию x точки встречи:
7.4. Когда две лягушки встретятся в одном квадрате 227
Если tx недробное число
и положительное,
то вернуть tx.
Иначе, если предыдущие условия не выполняются,
вернуть None.
'''
if dy1 == dy2 == 0:
tx = (sx2 - sx1) / (dx1 - dx2)
if int(tx) == tx and tx > 0:
t = int(tx)
else:
t = None
return t
'''
4:
Если dx1 != dx2 (не равны):
1: Если dy1 != dy2, то вычисляются tx и ty.
1.2: Если tx и ty равны и имеют
недробные положительные значения,
то вернуть tx, иначе вернуть None.
2: Если dy1 = dy2, то вычисляется tx.
2.1: Если tx недробное и положительное число,
то вернуть tx,
иначе вернуть None.
'''
if dx1 != dx2:
if dy1 != dy2:
tx = (sx2 - sx1) / (dx1 - dx2)
ty = (sy2 - sy1) / (dy1 - dy2)
if tx == ty and int(tx) == tx and tx > 0:
t=int(tx)
else:
t = None
return t
elif dy1 == dy2:
tx = (sx2 - sx1) / (dx1 - dx2)
if int(tx) == tx and tx > 0 and sy1 == sy2:
t = int(tx)
else:
t = None
return t
'''
5:
Если dx1 == dx2 (равны)
1: Если dy1 != dy2, то вычислить ty.
1.1: Если ty недробное и
положительное число, то
вернуть tx, иначе
вернуть None.
2: Если dy1 == dy2, то вернуть None.
'''
if dx1 == dx2:
if dy1 != dy2:
ty = (sy2 - sy1) / (dy1 - dy2)
if int(ty) == ty and ty > 0 and sx1 == sx2:
t = int(ty)
else:
t = None
return t
elif dy1 == dy2:
t=None
return t
return t
7.5. Определение позиции числа
в массиве Витхофа
Массив Витхофа – это двумерная таблица, которая характеризуется первой
строкой, содержащей последовательность Фибоначчи (1, 2, 3, 5, …). Массив
можно определить следующим образом: пусть pr обозначает предыдущую
строку, cr обозначает текущую строку, а a и b – первый и второй элементы pr соответственно. Первый элемент следующей строки (исключая первую строку) определяется как наименьшее число, которое не встречается
ни в одной из предыдущих строк, и обозначается как c. Второй элемент
следующей строки определяется на основе следующих двух условий:
1) если c – a = 2, то значение второго элемента равно b + 3;
2) если c – a ≠ 2, то значение второго элемента равно b + 5.
b + 3
x=
b + 5
если c – a == 2 (равно 2)
если c – a != 2 (не равно 2)
.
(7.1)
7.5. Определение позиции числа в массиве Витхофа 229
Значение каждого следующего элемента определяется подобно числам
в последовательности Фибоначчи – как сумма двух предыдущих элементов. Например, пусть x1, x2 и x3 обозначают первую, вторую и третью строки массива Витхоффа.
х1 = 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
х2 = 4, 7, 11, 18, 29, 47, 76, 123, 199,
х3 = 6, 10, 16, 26, 42, 68, 110, 178, 288.
Согласно правилам, первый элемент x2 равен 4 – наименьшему числу, которого нет в x1. Чтобы определить второй элемент в x2, используем
a = 1 и b = 2 из x1 и c = 4 из x2. Вычисляем c – a: 4–1 = 3. Поскольку 3 ≠ 2,
используем формулу b + 5 и получаем 7 – значение для второго элемента
в x2. После получения первых двух элементов в x2 мы можем продолжить
эту последовательность, используя алгоритм Фибоначчи. Например, третий элемент получается сложением 7 и 4 – двух предыдущих элементов,
в результате получается 11. Используя аналогичный подход, можно получить x3 из x2. Цель этой задачи – найти позицию (индекс) заданного числа n в виде кортежа (строка, столбец). Ваша задача: написать функцию, которая принимает положительное целое число n и возвращает его позицию
в виде кортежа (строка, столбец) в массиве Витхофа.
В табл. 7.5 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 7.5. Некоторые ожидаемые результаты для задачи
поиска позиции числа в массиве Витхофа
n
Ожидаемый результат
1042
(8, 8)
13
(0, 5)
127
(48, 0)
20022
(4726, 1)
Алгоритм
Пусть n – заданное искомое число. Алгоритм начинается с инициализации переменных и множеств. Затем он перебирает максимально допустимое количество столбцов (n + 1) и генерирует два числа в текущей строке
на основе меньшего и большего чисел из предыдущей строки. Меньшее
число выбирается в качестве отправной точки, и алгоритм выполняет итерации до тех пор, пока не будет найдено непосещенное число. Затем на основе формулы 7.1 вычисляется следующее число. Далее алгоритм проверяет, присутствует ли искомое число в текущей строке и, если присутствует,
230
Глава 7. Разные задачи
возвращает найденную позицию. Если число отсутствует, то алгоритм
добавляет два новых числа в множество посещенных чисел, проверяет
остальную часть строки на наличие целевого числа и переходит к следующей строке. Этот процесс повторяется до тех пор, пока не будет достигнуто
максимальное количество столбцов.
В листинге 7.6 приводится код на Python, определяющий позицию искомого числа в массиве Витхофа.
Листинг 7.6. Определение позиции числа в массиве Витхофа
1 def Positioning_in_Wythoff_Array(n):
2
# Инициализировать переменные и множества
3
visited_numbers = set([])
4
current_row = 0
5
smaller_number, larger_number = -1, -1
6
7
'''
8
Цикл по максимально возможному
9
количеству столбцов
10
'''
11
for _ in range(n + 1):
12
13
if len(visited_numbers) == 0:
14
previous_number, last_number = 1, 2
15
else:
16
'''
17
Выбрать меньшее число
18
в качестве отправной точки
19
'''
20
current_number = smaller_number
21
# Выполнять цикл, пока не будет встречено непосещавшееся число
22
23
while True:
24
if current_number not in visited_numbers:
25
26
# Вычислить следующее число в строке
27
if current_number - smaller_number == 2:
28
next_number = larger_number + 3
29
else:
30
next_number = larger_number + 5
31
32
'''
33
Вернуть два числа
7.5. Определение позиции числа в массиве Витхофа 231
для следующей строки
'''
previous_number, last_number =\
current_number, next_number
break
'''
Увеличить current_number
и повторить попытку
'''
current_number += 1
'''
Обновить переменные
для следующей итерации
'''
smaller_number, larger_number =\
previous_number, last_number
'''
Проверить присутствие
целевого числа в текущей строке
'''
if n == previous_number:
return (current_row, 0)
elif n == last_number:
return (current_row, 1)
'''
Добавить два числа
в множество посещенных чисел
'''
visited_numbers.add(previous_number)
visited_numbers.add(last_number)
'''
Проверить наличие искомого
числа в оставшейся части строки
'''
column_number = 2
while last_number
