Кратчайший путь передвижения короля по шахматному полю

Министерство образования и науки Российской Федерации

Агентство по образованию

Тихоокеанский государственный экономический университет

Экономический институт

«Кратчайший путь передвижения короля по шахматному полю»

Выполнил: Прудникова Л.И.

Владивосток 2009

Введение

Условие решаемой задачи дословно по заданию звучит следующим образом: «найти кратчайший путь передвижения короля по заданному клеточному полю, соединяющих два заданных поля доски»

Целью представленной работы является разработка приложения “Поиск кратчайшего пути”, которое создает шахматную доску, находит кратчайший путь передвижения короля и отображает его.

Перед началом вычисления пользователь должен указывать в программе следующую информацию:

- размерность поля

- установить слона на начальную позицию и указать конечную (при помощи мыши)

После этого программа должна показать кратчайший путь (пути) движения короля, выделяя его другим цветом.

Неформальная постановка задачи

Задачу ставит заказчик, а принимает разработчик. Между разработчиком и заказчиком должен состояться диалог, цель которого выяснить, одинаково ли они понимают задачу. Диалог может длиться день, месяц… В моей ситуации требуется написать программу, чтобы она могла найти кратчайший путь передвижения короля по заданному клеточному полю, соединяющих два заданных поля доски. Причём начальная и целевая клетки указываются при помощи мыши в запущенной программе.

Формальная постановка задачи

Разработка или поиск алгоритма решения задачи

Проект программы:

Задаём размер поля n.

Проверим, чтобы король и его местоположение должны находиться на полях одного цвета.

Образуем матрицу для расчёта пути размерности n+1.

С помощью полученной матрицы во избежание выхода за шахматное поле заполним окаймляющие элементы значениями false.

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

Спецификация функций программы

В появившемся при вызове программы окне вводим размерность поля.

а) если мы вводим размерность поля меньше или больше указанного диапазона, то выводится сообщение

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

Тем самым указываются все случаи, которые могут возникнуть при решении задачи на компьютере. Каждый такой случай оформляется как некоторая функция (в смысли достижения цели)

Руководство пользователя

При разработке приложения применялся принятый в среде Delphi объектно-ориентированный подход реализации интерфейса. При реализации алгоритмов обработки данных использовался структурный подход при проектировании к написании программ приложения.

В появившемся при вызове программы окне вводим размерность поля.

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

Если мы вводим размерность поля меньше или больше указанного диапазона, то выводится сообщение

Проектирование программы

Все предшествующие этапы необходимы для сбора информации, используемой для проектирования программы. Проект программы это не сама программа, а её эскиз, в котором чётко зафиксированы все функции задачи, как некоторые её подзадачи.

Программирование

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 begin application.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;