Подсказки к ДЗ:

1) Структура данных (возможна оптимизация):

//открываем файл для чтения;
//читаем из него m,n - количество строк и столбцов поля
setlength(pole,m+2,n+2);//здесь строки поля 1..m, а колонки 1..n. Остальное - стенка
//читаем из файла xs,ys - координаты стартовой клетки (начало координат: [1,1])
//читаем из файла xe,ye - координаты конечной клетки
//читаем в цикле по строкам от 1 до m и столбцам от 1 до n из файла
//веса v всех клеток, и заполняем массив pole, учитывая, что:
// начальное значениы S задаем=большое число
// если v=большое число, то это стенка, задаем f=1, иначе f=0
//для нулевой и m+1 - й строки задаем f=1 (стенка)
//для нулевого и n+1 - й колонки задаем f=1 (стенка)
//для клетки (xs,ys) (стартовой) задаем s=0

type pp=record
x,y:integer;//координаты предшественника
v:integer;//"вес" клетки
f:integer;//флаг: стенка: f=-1, обычное поле: f=0
s:integer;//путь до клетки (сумма весов по маршруту)
end;
var pole:array [,] of pp;//двумерный массив записей
xs,ys,xe,ye,m,n:integer;

2) Описание модуля Rread - процедуры подготовки данных (возможна оптимизация):

3) Описание модуля Pathfinder(I,j) - процедуры (или функции?) поиска кратчайшего пути из (xs, ys) в (xe, ye):

Пусть (i, j) – текущая клетка, а соответствующий ей элемент массива: pole[I, j].
Если клетка [i+1, j]-не стенка и pole[i, j].s + pole[i+1, j].v a) Вычисляем pole[i+1, j].s=pole[i, j].s + pole[i+1, j].v; b) Запускаем Pathfinder(i+1, j)
… и то же самое для остальных направлений

4) Текст (почти полный) головной программы:

begin
Rread; Pathfinder(xs,ys);
Println(‘Длина кратчайшего пути из (’,xs,’, ‘,ys,’) в (‘, xe,’, ‘,ye,’):’,pole[xe, ye].s);
… Далее идет вывод кратчайшего пути в форме: (xs,ys)->, …, ->(xe, ye)
End.

Pas-файл с выполненным заданием выслать в мой E-mail адрес: LEOMTL@MAIL.RU, прикрепив к письму и указав в «Теме»
ФИО, класс и подгруппу, например: Иванов Иван, 11Т1 (в названии класса-подгруппы всё писать подряд и латиницей)

Принципы динамического программирования на примере задачи поиска кратчайшего пути на клеточном поле

Содержание

Похожие презентации