В книге приведены примеры решения различных практических задач на языке Python и предложено детальное пошаговое описание процесса написания программы для каждой из них. Подобраны задачи, которые имеют несколько вариантов решений и формируют алгоритмическое мышление. Показаны основы структурного, динамического, объектно-ориентированного, функционального программирования. Приведены способы работы с функциями, алгоритмы поиска в длину, в ширину, бэктрекинга, рекурсии. Материал расположен по возрастанию сложности, код программ снабжен комментариями, разъясняющими все языковые конструкции Python.
Для начинающих программистов
Python — это красиво!
Главная причина популярности языка Python — его лаконичность, простота и выразительность. Один и тот же алгоритм на этом языке можно запрограммировать по-разному – так, что будет казаться, будто программа написана на разных языках. В этой книге приводятся алгоритмы решения задач на Python, которые автор считает красивыми — все они имеют несколько вариантов решений и формируют алгоритмическое мышление. Эти алгоритмы – часть хорошего IT-образования. Рассмотрев предложенные задачи, знакомый с основами Python читатель сможет проверить, действительно ли он умеет программировать, а изучив их решения, значительно улучшит свои алгоритмические навыки. Ценность книги состоит в том, что в ней приводится детальное пошаговое описание процесса написания программы для решения каждой поставленной задачи.
- Структурное программирование
- Динамическое программирование
- Объектно-ориентированное программирование
- Функциональное программирование
Книгу “Python. Красивые задачи для начинающих” можно купить со скидкой в интернет-магазине издательства “БХВ“.
Предисловие…………………………………………………………………………………………….. 7
На кого рассчитана эта книга?………………………………………………………………………………………………… 10
Структура книги………………………………………………………………………………………………………………………… 11
Благодарности…………………………………………………………………………………………………………………………… 12
Глава 1. Условия……………………………………………………………………………………. 13
1.1. Квадратное уравнение, комплексные корни…………………………………………………………………….. 13
Задача………………………………………………………………………………………………………………………………….. 13
1.2. Кирпич и дыра в стене………………………………………………………………………………………………………… 18
Задача………………………………………………………………………………………………………………………………….. 18
Версия 1……………………………………………………………………………………………………………………… 19
Версия 2……………………………………………………………………………………………………………………… 20
Версия 3……………………………………………………………………………………………………………………… 21
Глава 2. Структурное программирование………………………………………………. 23
2.1. Полупроходной балл………………………………………………………………………………………………………….. 23
Задача 1………………………………………………………………………………………………………………………………. 23
Версия 1……………………………………………………………………………………………………………………… 24
Версия 2……………………………………………………………………………………………………………………… 25
Задача 2………………………………………………………………………………………………………………………………. 28
Версия 3……………………………………………………………………………………………………………………… 28
Версия 4……………………………………………………………………………………………………………………… 29
Задача 3………………………………………………………………………………………………………………………………. 31
Версия 5……………………………………………………………………………………………………………………… 32
2.2. Метеостанция……………………………………………………………………………………………………………………… 33
Задача………………………………………………………………………………………………………………………………….. 33
Версия 1……………………………………………………………………………………………………………………… 34
Версия 2……………………………………………………………………………………………………………………… 37
2.3. Седловина матрицы……………………………………………………………………………………………………………. 40
Задача………………………………………………………………………………………………………………………………….. 40
2.4. Максимальный квадрат в матрице, заполненный нулями………………………………………………. 43
Задача………………………………………………………………………………………………………………………………….. 43
2.5. Чемпионат по игре в тетрис……………………………………………………………………………………………….. 46
Задача………………………………………………………………………………………………………………………………….. 46
2.6. Проверка правильности расстановки скобок…………………………………………………………………… 51
Задача………………………………………………………………………………………………………………………………….. 51
Глава 3. Функции………………………………………………………………………………….. 57
3.1. Решето Эратосфена и числа-близнецы…………………………………………………………………………….. 57
Задача………………………………………………………………………………………………………………………………….. 57
3.2. Решето Сундарама……………………………………………………………………………………………………………… 65
Задача………………………………………………………………………………………………………………………………….. 65
3.3. Лесенка………………………………………………………………………………………………………………………………… 67
Задача………………………………………………………………………………………………………………………………….. 67
3.4. Линейный и медианный фильтры………………………………………………………………………………………. 73
Задача 1………………………………………………………………………………………………………………………………. 73
Задача 2………………………………………………………………………………………………………………………………. 84
3.5. Алгоритм Евклида………………………………………………………………………………………………………………. 85
Задача………………………………………………………………………………………………………………………………….. 85
3.6. Гипероператоры…………………………………………………………………………………………………………………. 91
Задача………………………………………………………………………………………………………………………………….. 91
3.7. Ханойские башни……………………………………………………………………………………………………………… 102
Задача……………………………………………………………………………………………………………………………….. 102
3.8. Отображения списков……………………………………………………………………………………………………….. 109
Задача……………………………………………………………………………………………………………………………….. 109
Глава 4. Поиск в длину и ширину, бэктрекинг,
динамическое программирование………………………………………………………… 119
4.1. Лабиринт……………………………………………………………………………………………………………………………. 119
Задача 1…………………………………………………………………………………………………………………………….. 120
Версия 1…………………………………………………………………………………………………………………… 120
Версия 2…………………………………………………………………………………………………………………… 125
Версия 3…………………………………………………………………………………………………………………… 130
Версия 4…………………………………………………………………………………………………………………… 134
Задача 2…………………………………………………………………………………………………………………………….. 139
4.2. Задача о восьми ферзях……………………………………………………………………………………………………. 143
Задача……………………………………………………………………………………………………………………………….. 143
Версия 1…………………………………………………………………………………………………………………… 143
Версия 2…………………………………………………………………………………………………………………… 156
4.3. Поиск индекса элемента в списке……………………………………………………………………………………. 161
Задача……………………………………………………………………………………………………………………………….. 161
Версия 1…………………………………………………………………………………………………………………… 161
Версия 2…………………………………………………………………………………………………………………… 162
Версия 3…………………………………………………………………………………………………………………… 163
4.4. Сжатие строки…………………………………………………………………………………………………………………… 167
Задача……………………………………………………………………………………………………………………………….. 167
4.5. Укладка рюкзака………………………………………………………………………………………………………………. 176
Задача……………………………………………………………………………………………………………………………….. 176
4.6. Подпоследовательность максимальной длины……………………………………………………………… 180
Задача……………………………………………………………………………………………………………………………….. 181
Версия 1…………………………………………………………………………………………………………………… 181
Версия 2…………………………………………………………………………………………………………………… 184
Версия 3…………………………………………………………………………………………………………………… 186
Версия 4…………………………………………………………………………………………………………………… 191
4.7. Палиндром наибольшей длины……………………………………………………………………………………….. 199
Задача……………………………………………………………………………………………………………………………….. 199
4.8. Гиперсфера………………………………………………………………………………………………………………………… 208
Задача……………………………………………………………………………………………………………………………….. 209
Глава 5. Объектно-ориентированное программирование…………………….. 219
5.1. Графы с помощью словарей…………………………………………………………………………………………….. 219
Задача 1…………………………………………………………………………………………………………………………….. 220
Задача 2…………………………………………………………………………………………………………………………….. 220
Задача 3…………………………………………………………………………………………………………………………….. 224
Задача 4…………………………………………………………………………………………………………………………….. 225
Задача 5…………………………………………………………………………………………………………………………….. 226
Задача 6…………………………………………………………………………………………………………………………….. 227
Задача 7…………………………………………………………………………………………………………………………….. 228
Задача 8…………………………………………………………………………………………………………………………….. 228
5.2. Родословное древо……………………………………………………………………………………………………………. 230
Задача 1…………………………………………………………………………………………………………………………….. 230
Задача 2…………………………………………………………………………………………………………………………….. 238
Задача 3…………………………………………………………………………………………………………………………….. 243
5.3. Период в числовой последовательности………………………………………………………………………… 252
Задача……………………………………………………………………………………………………………………………….. 252
Версия 1…………………………………………………………………………………………………………………… 252
Версия 2…………………………………………………………………………………………………………………… 253
Версия 3…………………………………………………………………………………………………………………… 254
5.4. Треугольник Паскаля и сочетания………………………………………………………………………………….. 257
Задача 1…………………………………………………………………………………………………………………………….. 257
Задача 2…………………………………………………………………………………………………………………………….. 259
Отступление про функторы……………………………………………………………………………………. 262
5.5. Гиперкуб в многомерном пространстве………………………………………………………………………….. 266
Задача……………………………………………………………………………………………………………………………….. 266
Глава 6. Функциональное программирование……………………………………… 287
6.1. Интеграл…………………………………………………………………………………………………………………………….. 288
Задача……………………………………………………………………………………………………………………………….. 288
6.2. Отображения, сохраняющие внутреннюю структуру…………………………………………………… 298
Общая задача……………………………………………………………………………………………………………………. 298
Задача 1…………………………………………………………………………………………………………………………….. 299
Задача 2…………………………………………………………………………………………………………………………….. 302
Задача 3…………………………………………………………………………………………………………………………….. 304
6.3. Цепочки функций………………………………………………………………………………………………………………. 305
Задача……………………………………………………………………………………………………………………………….. 305
6.4. Монады……………………………………………………………………………………………………………………………… 309
Задача……………………………………………………………………………………………………………………………….. 309
6.5. Карринг……………………………………………………………………………………………………………………………… 319
Задача……………………………………………………………………………………………………………………………….. 319
6.6. Функторы…………………………………………………………………………………………………………………………… 331
Задача……………………………………………………………………………………………………………………………….. 331
Выводы по главам 3, 4 и 6……………………………………………………………………………………………………….. 342
Глава 7. Сюрреализм……………………………………………………………………………. 345
7.1. Фрактальные списки…………………………………………………………………………………………………………. 345
7.2. Фрактальный словарь………………………………………………………………………………………………………. 346
7.3. Бесконечные вызовы функции…………………………………………………………………………………………. 346
7.4. Функтор с бесконечными вызовами………………………………………………………………………………… 347
Заключение………………………………………………………………………………………….. 349
Предметный указатель…………………………………………………………………………. 351
Добряк Павел Вадимович — кандидат технических наук, преподаватель Уральского федерального университета. Проводит занятия по различным языкам программирования, базам данных, искусственному интеллекту и проектированию информационных систем. Репетитор по математике и информатике.