Павел Довгалюк БАЗОВЬIЕ АЛГОРИТМЬI Реализаци~ на Python и С++ на примере 1<Лассичес1<их игр Санкт-Петербург « БХВ-Петербург» УДК 32.9 .2 Д58 Довгалюк П. М. Д58 Базовые алгоритмы. Реализация на Python и С++ на примере классических игр. - СПб.: БХВ-Петербург, 2025. - 400 с.: ил. В книге дается базовая алгоритмическая подготовка, классические алгоритмы разобраны одновременно на двух языках - С++ и Python на примере широко из вестных и интуитивно понятных компьютерных игр. Наглядно излагается реализа ция циклов, перебора, рекурсии, эвристики, рассматривается работа с деревьями решений на примере шахмат, предлагается знакомство с прямоугольными коорди натами, дается введение в самообучающиеся алгоритмы. Книга ориентирована как на начинающих программистов, так и на читателей, планирующих перейти на С++ или Python как на второй язык. Примеры, рассмотренные в книге, помогут сделать первые шаги на пути к профессиональному программированию игр. Для программистов -018.2 Группа ПОДГОТОВКИ издания: Руководитель проекта Олег Сивченко Зав.редакцией Людмw,а Гауль Редактор Анна Брезман Компьютерная верстка Павла Довгалюка Корректор Анна Брезман Дизайн обложки Зои Канторович Формат 7Ох100 1 /,е. Печать офсетная. Усл. печ. л. 32,25. экз. Заказ № 14510. "БХВ-Петербург", 191036, Санкт-Петербург, Гончарная ул., 20. Отпечатано с готового оригинал-макета ООО "Принт-М", 142300, М.О., г. Чехов, ул. Полиграфистов, д. 1 © ООО "БХВ ", 2025 ©Оформление.ООО "БХВ-Петербург", 2025 Все игры и головоломки в книге Сложность программы Можно сразу начинать набирать программу на компьютере. *** Нужно сначала прочитать главу, где описана игра. ***** Потребуется изучить большую часть книги. Тип игры •++• Игра для одного человека. Игра <<Бросание кубика>> Программа-имитатор бросков игрального кубика Программа решает головоломку. Человек играет против компьютера. Игра <<Отгадай число>> ................................. 29 Программа загадывает число и предлагает игроку отгадать его Игра <<23 спичкю> *+• Кто возьмёт последнюю спичку со стола, тот проиграл Игра <<Хаммурапю> Игра-симулятор жизни правителя аграрной страны Игра <> Или <<двадцать одно>>, одна из самых популярных *** карточных игр Все игры и головоломки в книге Игра << Ферзя в угол>> Кто заведёт в угол ферзя, тот выиграл Игра << Чудовища>> ••** ••** •••• Игрок пытается найти чудовищ, спрятавшихся на болоте Игра <<Крестики-ноликю> Всем известная детская игра, но теперь в неё играет компьютер Числовые ребусы с буквами ......................... 124 Программа разгадывает арифметический ребус, где цифры заменены буквами Игра <<Быки и коровы>> Компьютер отгадывает задуманное число, получая подсказки о совпадении цифр Игра <<Морской бой>> .................................. 154 Нужно первым потопить спрятанные на поле корабли противника Игра <<Реверсю> ......................................... 190 Настольная игра, где нужно захватить игровое поле, перекрашивая фишки соперника Головоломка <<8 ферзей>> они не били друг друга Игра <<Крестики-ноликю> 4х4 ...................... 227 Усложнённый вариант классических Как расставить 8 ферзей на шахматной доске, чтобы крестиков-ноликов Головоломка <<Лабиринт>> Компьютер ищет выход из лабиринта Все игры и головоломки в книге Игра <<8>> .................................................. 264 Поиск порядка перемещения фишек в модификации знаменитой головоломки <<Пятнадцать>> Игра <<Солитер>> 1ddd,: Фишки прыгают друг через друга, чтобы съесть. Нужно, чтобы осталась только одна Игра <<Калах>> jd( Игра с камушками на доске, где нужно захватить их больше, чем соперник Игра <<Мини-шахматы>> Шахматы на поле 5 х 5 Игра <<Угадай животное>> jd( Программа пытается отгадать задуманное животное, задавая вопросы. Если не получилось отгадать, она добавляет правильный ответ в свою базу знаний Игра <<6 пешею> Программа знает только правила игры, но не знает, как выигрывать. Чем больше она проигрывает, тем лучше играет потом 1 Введение 1.1. Для кого эта книга . 1.2. С++ или Python? . 1.3. Как читать эту книгу 2 Обзор языков с++ и Python Структура программы . 2 .1. 2.2. Вывод на экран . 2.3. Ввод данных 2.4. Ветвления 2.5. Циклы . . . . 2.6. Функции .. . Изменение переменных-параметров функции 2.7. Массивы . . . . . . . . . . . . 2.8. 2.9. Словари . . . . . . . . . . . . . . 2.10. Генерация случайных чисел .. . 2.11. Другие отличия С++ и Python. 3 Начнём с простых игр 3.1. Игра <<Бросание кубика>> Основа программы .. 3.1.1. 3.1.2. Имитируем игральный кубик 3.1.3. 3.2. Игра <<Отгадай число>> . . . . . . . . . 3.2.1. Переделываем <<Бросание кубика>> Подсказки для игрока 3.2.2. 3.3. Игра <<23 спичкю> Почти готовая игра . 3.3.1. 3.3.2. Учим компьютер играть . 3.3.3. Доделываем выбор хода . 3.3.4. Изучаем структуру игровой программы 4.1. Игра <<Хаммурапи>> 4.1.1. Функция main . 4.1.2. Инициализация переменных Главный игровой цикл . 4.1.3. 4.1.4. Вывод итогов игры . Покупка и продажа земли . 4.1.5. 4.1.6. Зерно: хлеб и семена . 4.1.7. Случайные события 4.1.8. 4.1.9. 4.2. Игра <<Вlackjack>> 4.2.1. Вывод карт на руке 4.2.2. Раздача случайных карт . 4.2.3. 4.2.4. Определение победителя . Главный игровой цикл . 4.2.5. 4.2.6. Ещё один игровой цикл 4.2.7. Программирование прямоугольных полей 5.1. Игра <<Ферзя в угол>> . 5.1.1. 5.1.2. Начало игры Ввод координат . 5.1.3. Вывод поля 5.1.4. Дорабатываем вывод поля 5.1.5. Главный игровой цикл . 5.1.6. 5.1.7. Делаем ходы Искусственный интеллект: анализ ходов 5.1.8. Искусственный интеллект: проверка позиции 5.1.9. . Искусственный интеллект: пишем код . . Задания для самостоятельной работы 5.2. Игра << Чудовища>> 5.2.1. Структура программы 5.2.2. Расставляем монстров 5.2.3. Чиним расстановку монстров 5.2.4. Ход игрока 5.2.5. Ловим чудовищ . 5.2.6. Определяем расстояние до монстров . 5.2.7. Финальная часть . . . 5.2.8. 5.3. Игра «Крестики-ноликю> Игровая позиция . . . 5.3.1. Основной цикл, вывод поля 5.3.2. 5.3.3. Ход игрока, проверка условия победы . 5.3.4. Ход компьютера . . . . . . . . . Осмысленные ходы компьютера 5.3.5. 5.3.6. Доделываем алгоритм игры . . . Поиск завершения линии . . . . 5.3.7. Проверяем все строки, столбцы и диагонали 5.3.8. Всё для игры вничью . . . . . . . 5.3.9. Полный перебор с помощью циклов Числовые ребусы с буквами 6.1. 6.1.1. Начинаем писать программу Добавляем код для перебора 6.1.2. 6.1.3. Проверяем ограничения . . . 6.1.4. Send more money! . . . . . . . 6.1.5. Игра <<Быки и коровы>> 6.2. 6.2.1. Отгадывает человек 6.2.2. Основные функции . 6.2.3. Основной цикл игры Как хранить загаданное число 6.2.4. Функция generate - генерация случайного числа 6.2.5. Функция inputGuess - ввод числа игроком . . . . 6.2.6. Функция countBullsAndCows - подсчёт <<быков>> и <<коров>> 6.2. 7. Отгадывает компьютер 6.2.8. Структура программы . . . . . . . . . . . . . . . . 6.2.9. . Стуктуры данных . . . . . . . . . . . . . . . . . . . Узнаём у пользователя число <<быков>> и <<короВ>> . Функция generate - поиск возможных ответов. . . Функция save - сохранение полученных ответов . Функция countBullsCows - подсчёт <<быков>> и «коров>> . Задания для самостоятельной работы . . . . . . . . . . . Эвристические алгоритмы 7.1. Игра <<Морской бой>> . . . 7 .1.1. Игровая позиция . . . 7.1.2. Структура программы 7.1.3. Стрельба по кораблям 7.1.4. Расстановка кораблей . . . . . . . . . . . . 7.1.5. Расстановка кораблей: заполнение клеток 7.1.6. Доработка функции стрельбы . . . Расстановка кораблей игрока . . . . 7.1. 7. 7.1.8. Расстановка кораблей компьютером 7.1.9. Снова ход игрока . . . . . . . . Случайный ход компьютера. . Условие окончания игры . Добавляем <<туман войны>> . . Вычёркиваем клетки вокруг потопленных кораблей . Добивание раненого корабля . . . . . . Эвристики для игры компьютера .. . Задания для самостоятельной работы Игра <<Реверси>> . . . . . . . . 7.2. Игровая позиция . . . . . 7.2.1. Вывод позиции на экран . 7.2.2. 7.2.3. Главный игровой цикл .. Проверка допустимости хода 7.2.4. 7.2.5. Ход игрока . . . . . . . . 7.2.6. Переворачивание фишек . 7. 2. 7. Ход компьютера . . . . . Окончание игры . . . . . 7.2.8. 7.2.9. Задаём приоритет клеткам 8 Рекурсивные алгоритмы в играх Головоломка <<8 ферзей>> 8.1. Игровая позиция . . . . . . . . 8.1.1. 8.1.2. Общий алгоритм поиска решений 8.1.3. Проверка, что один ферзь атакует другого Перебор с помощью циклов . . . . . 8.1.4. 8.1.5. Отсеиваем некорректные варианты 8 .1. 6. . . . . . . . . . Что такое рекурсия Выход из рекурсии . . . . . . . . . . 8.1.7. 8.1.8. Рекурсивный перебор всех решений 8.1.9. И снова отсеивание некорректных вариантов. Игра <<Крестики-ноликИ>> 4х4 8.2. 8.2.1. Игровая позиция ... 8.2.2. Главный игровой цикл 8.2.3. Вывод игрового поля . Ход игрока . . . . . . 8.2.4. 8.2.5. Случайный ход компьютера .