Реферат: Кратчайший путь передвижения короля по шахматному полю
Министерство образования и науки Российской Федерации
Агентство по образованию
Тихоокеанский государственный экономический университет
Экономический институт
«Кратчайший путь передвижения короля по шахматному полю»
Выполнил: Прудникова Л.И.
Владивосток 2009
Введение
Условие решаемой задачи дословно по заданию звучит следующимобразом: «найти кратчайший путь передвижения короля по заданному клеточномуполю, соединяющих два заданных поля доски»
Целью представленной работы является разработка приложения “Поисккратчайшего пути”, которое создает шахматную доску, находит кратчайший путьпередвижения короля и отображает его.
Перед началом вычисления пользователь должен указывать в программеследующую информацию:
— размерность поля
— установить слона на начальную позицию и указать конечную (припомощи мыши)
После этого программа должна показать кратчайший путь (пути)движения короля, выделяя его другим цветом.
Неформальная постановка задачи
Задачу ставит заказчик, а принимает разработчик. Междуразработчиком и заказчиком должен состояться диалог, цель которого выяснить,одинаково ли они понимают задачу. Диалог может длиться день, месяц… В моейситуации требуется написать программу, чтобы она могла найти кратчайший путьпередвижения короля по заданному клеточному полю, соединяющих два заданных полядоски. Причём начальная и целевая клетки указываются при помощи мыши взапущенной программе.
Формальная постановка задачи
Разработка или поиск алгоритма решения задачи
Проект программы:
Задаём размер поля n.
Проверим, чтобы король и его местоположение должны находиться наполях одного цвета.
Образуем матрицу для расчёта пути размерности n+1.
С помощью полученной матрицы во избежание выхода за шахматное полезаполним окаймляющие элементы значениями false.
Выберем все возможные клетки, когда король из начальногоместоположения и точки назначения, используя ранее полученную матрицу.
Спецификация функций программы
В появившемся при вызове программы окне вводим размерность поля.
а) если мы вводим размерность поля меньше или больше указанногодиапазона, то выводится сообщение
В главном окне отмечаем расположение короля и цели. Отметив наполе короля, мы делаем проверку, чтобы пользователь не мог отметить клетку-цельна поле, не совпадающее цвету, поля короля, а также на поле где расположен самкороль.
Тем самым указываются все случаи, которые могут возникнуть прирешении задачи на компьютере. Каждый такой случай оформляется как некотораяфункция (в смысли достижения цели)
Руководство пользователя
При разработке приложения применялся принятый в среде Delphiобъектно-ориентированный подход реализации интерфейса. При реализацииалгоритмов обработки данных использовался структурный подход при проектированиик написании программ приложения.
В появившемся при вызове программы окне вводим размерность поля.
В главном окне отмечаем расположение слона и цели. Отметив на полекороля, мы делаем проверку, чтобы пользователь не мог отметить клетку-цель наполе, не совпадающее цвету, поля короля, а также на поле где расположен самкороля.
Если мы вводим размерность поля меньше или больше указанного диапазона,то выводится сообщение
Проектирование программы
Все предшествующие этапы необходимы для сбора информации,используемой для проектирования программы. Проект программы это не самапрограмма, а её эскиз, в котором чётко зафиксированы все функции задачи, какнекоторые её подзадачи.
/> /> /> />
Нахождение кратчайшего пути передвижения короля от начальной позиции до целевой клетки
/> />Размерность поля (n), начальное месторасположение короля, целевая клетка
/> />Кратчайший путь (пути)
Программирование
procedure TForm1.Button1Click(Sender: TObject);
var code: integer; // Сюда функция val запишет ошибку, в случае еевозникновения
begin
val (edit2.text, razmerY, code); // Получаем размер поля
val (edit1.text, razmerX, code); // из текстовых полей
// В случае возникновения введенного числа возможному размеру полянадо выдать ошибку и завершить выполнение процедуры
if ((razmerX<4) or (razmerX>25)) then beginapplication.MessageBox('Неправильная циферка!', 'Шахматы', MB_APPLMODAL); exit;end;
Form2.execute(razmerX, razmerY); // Передаем данные на Form 2
form2.ShowModal; // Показываем Form 2
end;
procedure TForm1.Edit1Change(Sender: TObject);
begin
edit2.text:=edit1.text; // Поле — квадрат
end;
procedure TForm1.FormPaint(Sender: TObject);
begin
if unit2.tf=true then self.Close; // Если пользователь нажимаетВыход на Form 2, нужно завершить работу проги
end;
end.
procedure Execute(x, y: integer);
function max(x, y:integer):integer;
procedure procClick(sender: tobject);
procedure dda_line(x1, y1, x2, y2:integer);
end;
var
Form2: TForm2;
img: array[1..20, 1..20] of timage;
etap: integer;
korolX, korolY: integer;
nadoX, nadoY:integer;
razmerX, razmerY:integer;
tf: boolean;
implementation
{$R *.dfm}
procedure TForm2.dda_line(x1,y1, x2, y2: integer);
// Процедура получает координаты конца и начала и «рисует» линиюмежду ними по алгоритму ДДА
var
i, L, xstart, ystart, xend, yend: integer;
dx, dy: real;
x, y: array [0..1000] of real;
begin
xstart:=x1;
ystart:=y1;
xend:=x2;
yend:=y2;
L:=max(abs(xend-xstart), abs(yend-ystart));
dx:=(x2-x1)/L;
dy:=(y2-y1)/L;
i:=0;
x[i]:=x1;
y[i]:=y1;
inc(i);
while(i<L) do begin
x[i]:=x[i-1]+dx;
y[i]:=y[i-1]+dy;
inc(i);
end;
x[i]:=x2;
y[i]:=y2;
i:=1;
// В клетки, где проходит линия, загрузим голубую картинку
while (i<L) do begin
img[round(x[i]), round(y[i])].Picture.LoadFromFile('put.bmp');
inc(i); end;
// В мемо запишем текущую информацию для пользователя
memo1.Clear;
memo1.Lines.Add('Вам требуется' + inttostr(L) + ' ходов:))');
//
// Изменим внешний вид и функцию кнопки под мемо
bitbtn1.Kind:=bkRetry;
bitbtn1.Caption:=' Еще раз!';
bitbtn1.tag:=2;
end;
procedure TForm2.procClick(sender: tobject);
// Процедура постановки короля на поле и указания клетки — цели
var x, y:integer;
begin
//
// Получаем координаты по tag
x:=(sender as timage).Tag div 100;
y:=(sender as timage).tag mod 100;
// Если это постановка короля, загрузить «короля» в выбраннуюклетку
if etap=postanovka then begin
if ((x +y) mod 2)=0 then (sender astimage).Picture.LoadFromFile('krch.bmp')
else
(sender as timage).Picture.LoadFromFile('krbl.bmp');
etap:=selectPlace; // Теперь переходим к указанию места назначения
korolX:=x;
korolY:=y;
memo1.Clear;
memo1.Lines.add('Укажите целевую клетку');
end;
// Мы выбрали клетку — цель
if etap=selectPlace then begin
// Если аккурат в этой клетке стоит король, выходим из процедуры,пользователь должен выбрать другое место
if ((korolX=x) and (korolY=y)) then exit;
// Загрузим в клетку маркер
(sender as timage).Picture.LoadFromFile('zel.bmp');
nadoX:=x;
nadoY:=y;
// Изменим значение переменой etap, чтобы больше ничего нельзябыло делать: ни расставлять короля, ни выбирать клетку
inc(etap);
// И прочертим линию от короля до клетки – назначения – это ибудет кратчайший путь
dda_line(korolX, korolY, nadoX, nadoY);
end;
//else
end;
procedure TForm2.Execute(x, y: integer);
// Процедура вызывается, когда от пользователя получена информацияо размерах X и Y поля
var wid, i, j: integer;
begin
razmerX:=x;
razmerY:=y;
etap:=postanovka; // Сейчас пользователь будет ставить короля,развернем окно на весь экран
self.WindowState:=wsMaximized;
//
// Высчитываем размер клетки исходя из размеров окна и количестваклеток
wid:=self.Width div (max(x, y)+2);
for i:=1 to x do
for j:=1 to y do begin
img[i,j]:=timage.create(self); // Выделяем память
img[i,j].Parent:=self; // Указываем родителя, чтобы клетка былаименно на Form 2, а не где — то
img[i,j].Top:=j*wid;
img[i,j].Stretch:=true; // Чтоб весь рисунок помещался
img[i,j].Left:=i*wid;
// В зависимости от координат поля загружаем то черный, то белыйфоны для клеток
if ((i+j) mod 2)=0 then
img[i,j].picture.loadfromfile('ch.bmp') //:=inttostr(x+y);
else
img[i,j].picture.loadfromfile('bl.bmp');//:=inttostr(x+y);
img[i,j].Width:=wid;
img[i,j].Height:=wid;
img[i,j].Tag:=i*100+j;
// Устанавливаем обработчик нажатия на клетку
img[i,j].onclick:=procClick;
end;
// Для пущей верности
self.WindowState:=wsMaximized;
// Снабдим мемо текущей информацией
memo1.Clear;
memo1.Lines.Add('Укажите начальное место расположения короля');
memo1.Left:=wid*(x+2);
memo1.Font.Name:='Times New Roman';
memo1.Font.Size:=25;
memo1.Width:=round(form2.width /2.5);
memo1.Height:=self.Height div 2;
// Придадим кнопке под мемо соответствующий вид
bitbtn1.Left:=memo1.left;
bitbtn1.top:=memo1.Top+memo1.Height;
bitbtn1.Width:=memo1.Width-25;
bitbtn1.Tag:=1;
bitbtn1.Kind:=bkCancel;
bitbtn1.Font:=memo1.font;
bitbtn1.height:=memo1.font.size*2;
bitbtn1.Caption:='Выход';
end;
procedure TForm2.Button1Click(Sender: TObject);
begin
// //
end;
procedure TForm2.FormCreate(Sender: TObject);
begin
self.WindowState:=wsMaximized;
unit2.tf:=false;
end;
procedure TForm2.BitBtn1Click(Sender: TObject);
var i, j:integer;
begin
// Если tag=1, то выходим из программы
if (sender as tbitbtn).tag=1 then begin self.close; tf:=true; end;
// Иначе вновь загружаем Form 1 для указания размеров
for i:=1 to razmerX do
for j:=1 to razmerY do
img[i,j].Free;
self.WindowState:=wsNormal;
self.Visible:=false;
end;
end.
Тестовый пример программы
/>
Рис.1. Рабочее окно приложения – ставим короля
/>
Рис.2. Рабочее окно приложения – нахождение кратчайшего путишахматного короля
Заключение
Результатом работы над курсовой работой создано приложение средеDelphi, которое находит в нем кратчайший путь и визуализирует его на формеприложения. Приложение является полупрофессиональным. Выполненныемногочисленные тестовые примеры позволяют утверждать, что надежностьпрограммного обеспечения проекта довольно высока.
Список литературы
1. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб.Пособие. – Владивосток: Изд — во ДВГТ, 2000. – 288с.
2. Молчанова Л.А., Прудникова Л.И. Delphi в примерах и задачах: Учеб.пособие. Владивосток: Изд — во ТГЭУ, 2006. – 92с.