С++ мастер-класс. 85 нетривиальных npoeiaoB, решений и задач

12 3 4 5 6 7 8

9 10 О 11

13 14 15 12

12 3 4 5 6 7 8

9 10 15 11

13 14 О 12

12 3 4 5 6 7 8

9 10 15 11

13 О 14 12

12 3 4 5 6 7 8 9 10 15 11 О 13 14 12

12 3 4 5 6 7 8 О 10 15 11

9 13 14 12

12 3 4 5 6 7 8

10 О 15 11

9 13 14 12

12 3 4 5 6 7 8

10 15 О 11

9 13 14 12

12 3 4 5 6 7 8

10 15 11 О

9 13 14 12

12 3 4 5 6 7 8

10 15 11 12

9 13 14 О

12 3 4 5 6 7 8

10 15 11 12 9 13 О 14

12 3 4 5 6 7 8 10 15 11 12 9 О 13 14

12 3 4 5 6 7 8 10 О 11 12 9 15 13 14

12 3 4 5 6 7 8 О 10 11 12 9 15 13 14

12 3 4 5 6 7 8 9 10 11 12 О 15 13 14

12 3 4 5 6 7 8 9 10 11 12 15 О 13 14

12 3 4 5 6 7 8 9 10 И 12 15 13 О 14

12 3 4 5 6 7 8 9 10 11 12 15 13 14 О

670 вершин рассмотрено

Глава 4. Рекурсия и перебор с возвратами. Эвристический поиск 4.3.2. Игры со сдвигающимися блоками

Hq)a в 15 - не единственная головоломка, в которой требуется передвигать блоки внутри прямоугольной коробки. Сняв ограничения на форму отдельных блоков и немного переформулировав цель задачи, можно получить множество превосходных головоломок, давно ставших классикой жанра настольных игр.

Рассмотрим, например, головоломку Moving Day (рис. 4.19). Цель головоломки - передвинуть блок с роялем, изначально находящийся в верхнем левом углу коробки, в левый нижний угол. Как и в игре в 15 , для манёвров у вас имеется небольшое свободное пространство, однако использовать его грамотно теперь гораздо сложнее.

Всробще цель большинства игр со сдвигающимися блоками состоит в перемещении какого-либо блока в заранее определённое место на доске. Например, в головоломке Gridloc #1 (рис. 4.20) требуется передвинуть блок с автомобилем из левого верхнего угла доски в правый нижний угол.

Рис 4.19. Головоломка Moiring Day

Первое задание заключается в программировании интерфейса, при помощи которого человек мог бы загружать и решать любую головоломку со сдвигающимися блоками. Головоломку удобно хранить в виде текстового файла, в котором каждый блок кодируется набором латинскР1Х букв, а пустое пространство - нулями. Например, задаче Moving Day будет соответствовать матрица:

ААВВ ААСС DEOO FGHH

Рис 4.20. Головоломка Cridkx U1

ГЛАВА 5. ВИЗУАЛИЗАЦИЯ И АНИМАЦИЯ

Где-то в файле необходимо также указать главный блок (то есть блок, перемещение которого и составляет головоломку) и расположение целевой области в игровой доске. Для задачи Moving Day эта информация кодируется двумя строками:

Здесь указано, что целью головоломки является перемещение блока, закодированного буквами А, в область, верхний левый угол которой задаётся координатами (3,1) (третья строка, первый столбец).

Второе, более амбициозное, задание состоит в реализации алгоритма, автоматически решающего любую загруженную головоломку.

Ещё лет двадцать назад компьютеры называли электронно-вычислительными машинами. Современный компьютер представляет собой нечто большее, чем просто усовершенствованный программируемый калькулятор. Изучая программирование, нельзя обойти стороной его мультимедийные возможности, к которым относятся визуализация и анимация. В данной главе мы рассмотрим визуализацию, в частности, на примерах физической модели ( Планетарная система ) и нотной азбуки ( Буквы и звуки ). Анимация реализуется в видеоиграх ( Космическая дуэль ) и в различного рода заставках ( Скринсейвер ). С визуализацией также связан интересный алгоритм черепашьей графики ( Черепашья графика ).

5.1. ПЛАНЕТАРНАЯ СИСТЕМА. УНИВЕРСАЛЬНАЯ ДЕМОНСТРАЦИОННАЯ АСТРОНОМИЧЕСКАЯ МОДЕЛЬ

Должно быть, вам приходилось видеть разного рода симпатичные анимиро-ванные схемы, иллюстрирующие движение планет Солнечной системы. Я предлагаю запрограммировать универсальную модель, пригодную для визуализации любой планетарной системы, состоящей из небесных тел, вращающихся друг около друга.

Входные данные программы записаны в текстовом файле. Каждая строка описывает одну планету с помощью пяти значений:

ID BASEID P RAD ORB RAD SPEED

Каждый элемент строки, кроме SPEED, является целым числом. Элемент SPEED представляет собой число вещественное.

Элемент ID - это уникальный идентификатор планеты. Планета с идентификатором О является центром системы: у неё могут быть спутники, но сама она не может быть спутником какой-либо другой планеты.

Глава 5. Визуализация и анимация

BASEID - это идентификатор базовой планеты, спутником которой является текзщ1ая (описываемая) планета.

PRAD - радиус планеты (в пикселях).

ORBRAD - радиус орбиты планеты (в пикселях). Орбита считается круговой.

SPEED - угловая скорость планеты (градусов в секунду). Идеально точной скорости работы программы не требуется. В частности, можно обновлять экран десять раз в секунду, считая, что графический вывод происходит мгновенно.

Значения BASEID, ORBRAD и SPEED для центральной планеты системы игнорируются.

Программа должна считать входной файл и вывести анимированную схему планетарной системы. Неподвижная центральная планета помещается в центр экрана.

5.2. ЧЕРЕПАШЬЯ ГРАФИКА - НЕСТАНДАРТНАЯ МОДЕЛЬ РИСОВАНИЯ

Нередко задача становится гораздо проще, если взглянуть на неё под иным углом зрения. Рассмотрим, например, такую обычную операцию как вычерчивание различных фигур на экране компьютера. Как правило, графическая библиотека поставляет функции вроде провести отрезок , нарисовать окружность , закрасить область и тому подобные. Если требуется начертить треугольник, квадрат или какую-либо сложную фигуру, состоящую из набора отрезков, удобство таких функций под сомнение не ставится. Однако ситуация меняется, как только встаёт необходимость изобразить, например, одну из показанных на рис. 5.1 спиралей.

Рис 5.1. Спирали для рисования черепашкой

5 Зах. Т72