Решение трудных и увлекательных задач на Python

Хабиб Изадха, Рашид Бехзадидуст
Решение  
трудных и увлекательных 
задач на Python

Challenging Programming 
in Python: A Problem 
Solving Perspective
Habib Izadkhah · Rashid Behzadidoost

Москва, 2024
Хабиб Изадха, Рашид Бехзадидуст
Решение трудных  
и увлекательных задач 
на Python

УДК   004.438Python
ББК   32.973.22 
И32
И32   Изадха Х., Бехзадидуст Р.
Решение трудных и увлекательных задач на Python / пер. с англ. 
А. Н. Киселева. – М.: ДМК Пресс, 2024. – 240 с.: ил.
            ISBN 978-5-93700-280-8
Цель данной книги – укрепить навыки логического рассуждения и развить творческое мышление, представив и решив 90 не самых простых задач 
на Python. Задачи изложены доходчиво и сжато, снабжены алгоритмами и 
комментариями, что помогает читателям следить за процессом их решения 
и понимать его суть. 
Издание предназначено читателям с базовыми знаниями языка Python, 
которые стремятся вывести свои способности на новый уровень. Книга будет 
полезна студентам, преподавателям, разработчикам, а также участникам 
соревнований по программированию.
First published in English under the title Challenging Programming in Python: 
A Problem Solving Perspective by Habib Izadkhah and Rashid Behzadidoost, edition: 1. 
Copyright © Habib Izadkhah, Rashid Behzadidoost, under exclusive license to Springer 
Nature Switzerland AG, 2024. This edition has been translated and published under 
licence from Springer Nature Switzerland AG. Springer Nature Switzerland AG takes no 
responsibility and shall not be made liable for the accuracy of the translation.
Все права защищены. Любая часть этой книги не может быть воспроизведена 
в какой бы то ни было форме и какими бы то ни было средствами без письменного 
разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку 
вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи 
с этим издательство не несет ответственности за возможные ошибки, связанные с 
использованием книги.
ISBN 978-3-03139-998-5 (англ.)                             © Springer Nature Switzerland AG, 2024 
ISBN  978-5-93700-280-8 (рус.)                              © Оформление, перевод на русский язык,
	
	
         издание, ДМК Пресс, 2024

Оглавление
Предисловие....................................................................................................................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.
Тебриз, Иран                                               Хабиб Изадха, Рашид Бехзадидуст