По шахматным правилам ферзь бьет все фигуры, расположенные на той же вертикали, горизонтали и диагонали. Поскольку каждая вертикаль может содержать только одного ферзя, i-того ферзя можно сразу же помещать на i-тую вертикаль. Параметр i становится индексом вертикали, а выбор позиции ограничивается восемью возможными значениями индекса горизонтали j.
Теперь необходимо выбрать представление шахматной доски. Первое, что приходит на ум — массив 8×8. Однако при выборе позиции для постановки очередного ферзя необходимо проверять, свободны ли соответствующие диагонали и горизонталь, а при таком представлении доски эта проверка будет сложной и громоздкой. Поэтому позиции ферзей имеет смысл записывать в одномерном массиве, где индекс массива — номер вертикали, а значение — номер горизонтали. Введем еще три одномерных массива логического типа, содержащих сведения о занятости каким-либо ферзем горизонтали и двух диагоналей. Поскольку для всех полей главной диагонали и всех параллельных ей постоянна разность координат i – j, а для побочной диагонали (и всех параллельных ей) постоянна сумма i + j , а также учитывая значения суммы и разности индексов для соответствующих диагоналей, представление шахматной доски будет следующим:
const
SizeCB = 8; // размер шахматной доски
PosQ : array[1..SizeCB] of integer;
NoHor : array[1..SizeCB] of Boolean;
NoRDiag: array[2..2*SizeCB] of Boolean;
NoLDiag: array[-SizeCB+1..SizeCB-1] of Boolean;
где
o PosQ[i]указывает позицию ферзя на i-той вертикали;
o NoHor[j] означает отсутствие ферзя на j-той горизонтали;
o NoRDiag[k] означает отсутствие ферзя k-той "побочной" диагонали;
o NoLDiag[k] означает отсутствие ферзя k-той"главной" диагонали.
Выход из рекурсии осуществляется по достижению одного из условий: решение найдено или все варианты испробованы. Поэтому среди параметров процедуры расстановки ферзей присутствует параметр, свидетельствующий о найденности решения. Процедура представлена в листинге 10.10.
Листинг 10.10. Восемь ферзей. Один вариант
procedure Queen(i: integer; var found: Boolean);
var
j: integer; // индекс горизонтали
l: integer;
begin
j:=0;
repeat
inc(j); found:=false;
for l:=1 to SizeCB do queens.Form1.DrawQueen(i+1,l,' ');
if NoHor[j] and NoRDiag[i+j] and NoLDiag[i-j] then begin
Создадим проект, форма которого представлена на рис. 10.6. На форме отражена ситуация, когда ферзи уже расставлены. Крестиком отмечены позиции ферзей на предыдущих уровнях рекурсии, приводящие к тупиковому случаю.
Рис. 10.6. Форма проекта Восемь ферзей (один вариант)
На форме выставлены два компонента:
o компонент StringGrid;
o кнопка Расставить.
Обработчик события Click кнопки Расставить освобождает все горизонтали и диагонали шахматной доски и вызывает процедуру расстановки ферзей Queen:
Листинг 10.11. Восемь ферзей. Расстановка ферзей
procedure TForm1.BtnTryClick(Sender: TObject);
var
i: integer;
begin
for i:=1 to SizeCB do NoHor[i]:= true; // горизонтали свободны
for i:=2 to 2*SizeCB do NoRDiag[i]:=true; //все "побочные"
// диагонали свободны
for i:=-SizeCB+1 to SizeCB-1 do NolDiag[i]:=true;
// все "главные" диагонали свободны
Queen(1,ok);
end;
Заполнение доски фигурами происходит в два этапа. Сначала в ячейки StringGrid процедура Queen вносит информацию о положении ферзей: поставленного или снятого (см. листинг 10.10), вызывая процедуру DrawQueen:
Важное обобщение задачи проб и ошибок — находить не одно, а все решения поставленной задачи. В случае задачи о восьми ферзяхтребуется найти все возможные расстановки ферзей на шахматной доске. Общая схема данного алгоритма получается из схемы, приведенной в листинге 10.9.
procedure Attemt(i: integer);
k: integer;
for k:=1 to m do begin
выбор k-того возможного хода
ifход удаченthen begin
записать ход;
if i<n then
Attemt(i+1)
нарисовать очередную расстановку ферзей ;
стереть ход;
end;
end;
end;
Так как условие окончания цикла зависит только от одной переменной, то цикл repeat заменен на цикл for и процедура содержит только один параметр. Таким образом, поиск всех возможных решений представляется более простой программой, чем поиск только одного решения. Этот алгоритм приведен в листинге 11.12.
Листинг 10.12. Восемь ферзей. Все варианты
procedure Queen8All (i: integer);
var
j: integer; // индекс горизонтали
begin
for j:=1 to SizeCB do
if NoHor[j] and NoRDiag[i+j] and NoLDiag[i-j] then begin
NoHor[j]:= true; // j-ая горизонталь опять свободна
NoRDiag[i+j]:=true; // побочная диагональ опять свободна
NoLDiag[i-j]:=true; // главная диагональ опять свободна
end
end;
Форма проекта для всех возможных расстановок ферзей показана на рис. 10.7. Из всех возможных расстановок показана последняя. В этом проекте позиции ферзей на предыдущих уровнях рекурсии не указываются.
Рис. 10.7. Восемь ферзей. Все варианты
Компоненты на форме проекта те же, что и на предыдущей форме (рис. 10.6). Обработчик события Click кнопки Расставить вызывает, после инициализации доски, процедуру Queen8All, приведенную в листинге 10.11.
Всего возможны 92 расстановки, из них только 12 принципиально различных. Остальные получаются с помощью осевой или центральной симметрий.
Среди всех решений задачи одно может считаться оптимальным, то есть таким, которое удовлетворяет некоторому, наперед заданному условию. И задача оптимального выбора — это поиск оптимального решения.
Для этого необходимо получить все возможные решения, и в процессе их получения оставлять только то, которое наилучшим образом удовлетворяет условию. Такой подход аналогичен поиску максимального элемента в последовательности: каждый последующий элемент последовательности сравнивается с максимальным из предыдущих — "локальным" максимумом, и при необходимости этот локальный максимум переприсваивается.
В качестве примера задачи оптимального выбора решим такую. Пусть есть некоторое количество предметов, характеризующихся двумя величинами: весом и ценой. Требуется найти оптимальную выборку, то есть выбрать предметы, имеющие наибольшую суммарную стоимость при предельном общем весе. Такие задачи приходится решать, собираясь в путешествие и упаковывая чемоданы или (шутка!) при ограблении ювелирного магазина.
Выборки, составляющие приемлемые решения, строятся постепенно, исследуя каждый отдельный предмет. Из рассмотрения предмета можно сделать два возможных вывода: включать предмет в выборку или не включать. Включение предмета возможно, если при добавлении этого предмета суммарный вес предметов выборки не превышает предельного веса. В противном случае добавление новых предметов в эту выборку можно прекратить. Невключение возможно, если стоимость выборки без этого предмета не меньше, чем ранее достигнутый локальный максимум стоимости.
Данные, необходимые для решения этой задачи, опишем следующим образом:
const
N=15; // количество предметов
type
TItem=record // предмет
weight: integer; // вес
cost : integer; // цена
end;
index = 1..N;
var
a: array[index] of TItem;
MaxCst, // наибольшая стоимость выборки
LimWeight, // предельный вес выборки
TotC : integer; // полная стоимость
i: index;
s, sOpt : set of index; // текущая и оптимальная выборки
В листинге 10.13 приведена процедура TryOpt, которая формирует оптимальную выборку. В этой процедуре исследуется целесообразность включения в выборку каждого предмета, она рекурсивно вызывается при переходе к следующему предмету до тех пор, пока все предметы не будут рассмотрены.
Необходимость обновления массива a связана с тем, что задавать характеристики предметов можно любым из способов:
o ввод вручную;
o случайными значениями (кнопка Заполнить случайным образом);
o замена любых значений в нужных ячейках после случайного заполнения.
В заключение необходимо заметить, что если бы решать задачу без рекурсии, то пришлось бы вычислить вес и стоимость всех возможных выборок, а число выборок для 15 предметов 215 – 1 = 32767. Ограничения, используемые в процедуре TryOpt, позволяют сократить число операций при нахождении оптимальной выборки, до £ 2000. Число рекурсивных вызовов процедуры TryOpt не превышает » 500.
Лекция 2. 1
Очереди. 1
9.3.1. Динамическая реализация очереди. 2
9.3.2. Очередь, реализованная с помощью массива. 5
где t Î [-1, 1] c да
шагом Dt = 0,2
a = 2,1 нет
нет