Задача про ферзей
Проведя анализ поставленной задачи, для её решения будем использовать метод ветвей и границ. Все перебираемые варианты следует разбить на классы (блоки), сделать оценку для всех решений из одного класса, и если она больше ранее полученной, то отбросить все варианты из этого класса. Первую матрицу заполняем «нулями», которые показывают, что шахматное поле пустое и «минус единицами», которые… Читать ещё >
Задача про ферзей (реферат, курсовая, диплом, контрольная)
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ «ПОЛОЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет информационных технологий Кафедра технологий программирования
РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА
по предмету «Структуры и алгоритмы обработки данных»
Тема: «Задача про ферзей»
Проверил: С. В. Кухта Выполнила: студентка гр. 09-ИТ-3
Е.Л. Радченко Новополоцк 2010
1. Анализ задания и постановка задачи
1.1 Задание расчётно-графической работы
1.2 Проектирование программы
2. Реализация программы
3. Тестирование программы Список используемой литературы рascal программа ферзь
1. Анализ задания и постановка задачи
1.1 Задание расчетно-графической работы:
Имеется клеточное поле размером N*M, в некоторых позициях которого расставлено К чёрных фигур. Необходимо расставить минимальное количество белых ферзей, чтобы пробивались все свободные позиции поля.
1.2 Проектирование программы Заданием расчётно-графической работы является создание программы, которая обеспечит расстановку ферзей таким образом, что будут пробиваться все свободные позиции.
Средой программирования выбран Pascal ABC.NET.
Проведя анализ поставленной задачи, для её решения будем использовать метод ветвей и границ. Все перебираемые варианты следует разбить на классы (блоки), сделать оценку для всех решений из одного класса, и если она больше ранее полученной, то отбросить все варианты из этого класса.
Алгоритм данной задачи следующий:
Задаются две матрицы: первая (главная или основная) матрица, на которой будут расставляться фигуры и вторая (побочная) — на которой будут производиться расчёты.
Первую матрицу заполняем «нулями», которые показывают, что шахматное поле пустое и «минус единицами», которые показывают, в каких позициях расставлены черные фигуры. Задание размеров матрицы и само заполнение матрицы происходит в результате считывания данных из текстового файла.
Далее делается проверка на пробиваемость клеток (подсчёт количества пробиваемых позиций) с каждой свободной позиции поля и значения которых записывается во вторую матрицу. В этой матрице производится поиск и максимального числа и координаты данной клетки. После того, как найдена клетка с наибольшей пробиваемостью, запомнив её позицию, в главное и побочное поле ставится ферзь. Производится очистка матрицы от лишних (ненужных) значений.
Поставив на главное поле ферзя, помечаем все его пробиваемые позиции «единицами». Далее производится проверка на оставшиеся пустые клетки.
Если все клетки помечены, т. е. их значения равны «единицам», то это значит, что поле полностью пробивается и расставлено минимальное количество ферзей — цель данной задачи достигнута и задача решена.
Если же помечены не все клетки, то проходим ещё раз по алгоритму (циклу), пока все клетки поля не станут помеченными. Для этого делается проверка на количество оставшихся «нулей» и далее производится подсчёт пробивания пустых клеток только с этих позиций. Следуя по алгоритму, находим минимальное количество ферзей и расставляем на шахматную доску.
2. Реализация программы В результате считывания данных из текстового файла, задаётся матрица размером N*M, где в неё расставляются K чёрныx фигур с координатами (y, x).
В данной программе используются следующие процедуры:
Procedure Zapolnenie_PobPolya — процедура заполнения подсчётов во вторую матрицу. При использовании данной процедуры также использовалась процедура proxod (y, x, l, field);
Procedure proxod (y, x: integer; var l: integer; var field: TField) (листинг 1) — процедура подсчёта пробиваний свободных клеток с определенной позиции ;
Листинг 1 — Procedure proxod (y, x, l, field);
Procedure proxod (y, x: integer; var l: integer; var field: TField);
var y1, x1:integer;
begin
l:=0;
{proverka probivaniya po vertikali i gorizontali}
y1:=y-1;
while (field[y1,x]=0) or (field[y1,x]=1) do begin
field[y1,x]: =1;
inc (l); dec (y1);
end;
y1:=y+1;
while (field[y1,x]=0) or (field[y1,x]=1) do begin
field[y1,x]: =1;
inc (l); inc (y1);
end;
x1:=x-1;
while (field[y, x1]=0) or (field[y, x1]=1) do begin
field[y, x1]: =1;
inc (l); dec (x1);
end;
x1:=x+1;
while (field[y, x1]=0) or (field[y, x1]=1) do begin
field[y, x1]: =1;
inc (l); inc (x1);
end;
{proverka probivaniya po diagonalyam}
y1:=y-1; x1:=x-1;
while (field[y1,x1]=0) or (field[y1,x1]=1) do begin
field[y1,x1]: =1;
inc (l);dec (y1); dec (x1);
end;
y1:=y+1; x1:=x-1;
while (field[y1,x1]=0) or (field[y1,x1]=1) do begin
field[y1,x1]: =1;
inc (l);inc (y1); dec (x1);
end;
y1:=y-1; x1:=x+1;
while (field[y1,x1]=0) or (field[y1,x1]=1) do begin
field[y1,x1]: =1;
inc (l);dec (y1); inc (x1);
end;
y1:=y+1; x1:=x+1;
while (field[y1,x1]=0) or (field[y1,x1]=1) do begin
field[y1,x1]: =1;
inc (l);inc (y1); inc (x1);
end;
end;
Procedure Poisk_Max (bfield:TField) — процедура поиска клетки с максимальным пробиванием и вставка ферзя;
Procedure Ochistka (листинг 2) — процедура очистки полей от расчётов;
Листинг 2 — Procedure Ochistka;
Procedure Ochistka;
var y, x: integer;
begin
{ochistka polei ot informacii o probivanii}
for y:=1 to N do begin
for x:=1 to M do begin
if ((bfield[y, x]<>0)and (bfield[y, x]<>-1)and (bfield[y, x]<>-2)) then
bfield[y, x]: =0;
if ((field[y, x]<>-1)and (field[y, x]<>-2)) then
field[y, x]: =0;
end;
end;
end;
Procedure Posstanovka — процедура расстановки пометок (единиц) в пробиваемые позиции;
Procedure Proverka (var st: boolean) — процедура проверки на оставшиеся пустые клетки (равные нулю).
Если при проверке st=true, то алгоритм закончен и производится вывод на экран (в виде матрицы). Если при проверке выдается false, то идет Procedure Peremena (листинг 3);
Листинг 3 — Peremena;
Procedure Peremena; //preobrazovanie matrici dlya dalneishih raschetov
var x, y, y1, x1: integer;
Begin
for y:=1 to N do
for x:=1 to M do begin
if field[y, x]=0 then
field[y, x]: =2;
end;
for y:=1 to N do begin
for x:=1 to M do
if field[y, x]=2 then begin
l:=0;y1:=y;x1:=x;
proxodXY (y1,x1,l, field); //podschet probivaemih znachenui
bfield[y, x]: =l;
end;
end;
End;
И далее переходим обратно к процедуре Poisk_Max (bfield). Идем по циклу до тех пор, пока все клетки не станут помеченными, т. е. пробиваемыми.
3. Тестирование программы В ходе тестирования программы обнаружились некоторые погрешности в расстановке минимального количества ферзей. После некоторых исправлений (вставки нескольких проверок) в процедуре Poisk_Max (bfield:TField), все погрешности были исправлены. Теперь данная программа работает нормально.
Список используемой литературы
1. Кормен Т., Лейзер Ч. Алгоритмы. Построение и анализ.
2. Зубов B.C. «Справочник программиста. Базовые методы решения графовых задач и сортировки»
3. Окулов «Программирование в алгоритмах»
4. Справка Pascal.ABC.NET