Павел Добряк | Python. Красивые задачи для начинающих (2024) [PDF]

Оглавление:
Предисловие ................................................................................................................... 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