Задача звучит так: В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города А в город В с минимальной величиной S+P, где S - сумма длин дорог пути, а Р - сумма пошлин проезжающих дорог.
В теории понимаю, как сделать, но на практике полный конфуз.
Задачу нужно сделать с использованием трехмерного массива, записей и всё сохранять в файл с возможностью модернизации, причем трехмерный массив состоит из другого двумерного массива. В общем примерно так:
Type
<Запись>=record
dlina:integer; {Длина дороги (км)}
poshlina:integer; {Пошлина за проезд по одной дороге}
end;
<Массив1>=array[dlina,poshlina] of <Запись>;
var
<Масив2>:array[<Город А>,<Город В>,<Кол-во путей между городами>] of <Массив1>
program min_road;
uses wincrt;
const n=7;{кол-во вершин графа}
var
map:array [1..N,1..N] of integer;{Карта: map[i,j] не 0, если точки i и j соединены}
road:array [1..n] of integer;{маршрут-номера точек карты}
incl:array [1..n] of boolean;{incl[i]=true, если точка с номером i включена в road}
len:integer; {Длина последнего найденного маршрута}
c_len:integer;{длина текущего маршрута}
start,finish:integer;{Начальная и конечная точки}
i,j:integer;
procedure step(s,f,p:integer);
var c:integer; {номер точки в которую делаем очередной шаг}
begin
if s=f then
begin
len:=c_len; {сохраняем длинну найденного маршрута}
write('путь: ');
for i:=1 to p-1 do write(road[i],' ');
writeln (' Длинна: ',len);
end
else
{выбираем очередную точку}
for c:=1 to n do {проверяем все вершины}
if (map[s,c]<>0) and (not incl[c]) and ((len=0) or (c_len+map[s,c]<len))
{точка соединена с текущей и не включена в маршрут}
then
begin
road[p]:=c; {добавим вершину в путь}
incl[c]:=true;{пометим вершину, как включенную}
c_len:=c_len+map[s,c];
step(c,f,p+1);
incl[c]:=false;
road[p]:=0;
c_len:=c_len-map[s,c];
end;
end;
begin
{инициализация массивов}
for i:=1 to N do road[i]:=0;
for i:=1 to N do incl[i]:=false;
for i:=1 to n do
for j:=1 to n do map [i,j]:=0;
{ввод значений элементов карты}
map [1,2]:=1;map [2,1]:=1;
map [1,3]:=1;map [3,1]:=1;
map [1,4]:=1;map [4,1]:=1;
map [3,4]:=1;map [4,3]:=1;
map [3,7]:=1;map [7,3]:=1;
map [4,6]:=1;map [6,4]:=1;
map [5,6]:=1;map [6,5]:=1;
map [5,7]:=1;map [7,5]:=1;
map [6,7]:=1;map [7,6]:=1;
write ('Введите через пробел номера начальной и конечной точек -> ');
readln (start,finish);
road [1]:=start; {Внесем точку в маршрут}
incl [start]:=true;{пометим ее как включенную}
len:=0;
c_len:=0;
step (start,finish,2); {ищем вторую точку}
writeln ('Для завершения нажмите <Enter>');
readln;
end.
М | При публикации программного кода, пожалуйста, используй теги: выделить программу блоком и выбрать нужный пункт из меню CODE над окном ввода Lapp |
Что-то ты переусердствовал...
Зачем тебе это:
Type- ?
<Запись>=record
dlina:integer; {Длина дороги (км)}
poshlina:integer; {Пошлина за проезд по одной дороге}
end;
<Массив1>=array[dlina,poshlina] of <Запись>;
Хм... алгоритм... Алгоритм назвать не могу, так как впервые имею дело с графами.
Могу по пунктам расписать, что мне нужно сделать:
1) Создание файла в который будет заноситься информация о количестве дорог между городами, расстояние и пошлина за каждую дорогу.
2) Ввод данных
3) Сохранение данных в файл
4) Сравнение каждого из элементов файла и нахождение самого короткого пути с самой маленькой пошлиной.
5) Вывод на экран сообщения о найденном пути
6) Возможность изменения элементов файла, добавление новых дорог.
<Масив2>:array[<Город А>,<Город В>,<КОЛ-ВО ПУТЕЙ МЕЖДУ ГОРОДАМИ>] of <Массив1>
Хорошо. Спасибо. Если возникнут вопросы, напишу ещё.
Сегодня, не без помощи препода понял, что от меня нужно, но как вы и предполагали возникла проблема с сохранением данных в файл. Вопрос написан в комментариях. Вот код:
uses wincrt;
const n=10;
type
rec=record
dlina:integer;
poshlina:integer;
end;
var
map:array[1..n,1..n,1..n] of rec;
road,i,city1,city2:integer;
roadfile:file of ?;
begin
assign(roadfile,'road.txt'); {Связывание файлововой переменной с самим файлом}
reset(roadfile); {Т.к. файл скорее всего будет типизированным то процедурой reset открываю его для чтения и записи}
write('Введите начальный и конечный города -> ');
readln(city1,city2); {Эти переменные пока не используются}
write('Введите количество дорог -> ');
readln(road);
for i:=1 to road do {Цикл, в ходе которого всем заданным дорогам присваивается длина и пошлина}
begin
with map[city1,city2,i] do {Открываю доступ к полям записи для их редактирования}
begin
write('Введите длину ',i,' дороги -> ');
readln(dlina);
Write('Введите пошлину ',i,' дороги -> ');
readln(poshlina);
end;
write(roadfile,map); {Здесь туплю. Можно ли таким образом занести весь массив целиком в файл?
И если да, то какого типа должен быть файл? Перепробовал уже всё, что знаю, но ничего не выходит.}
end;
close(roadfile);
end.
Изменил свою прогу таким образом (Изменение в разделе type и var):
uses wincrt;
const n=10;
type
rec=record
dlina:integer;
poshlina:integer;
end;
type_map=array[1..n,1..n,1..n] of rec;
var
map:type_map;
road,i,city1,city2:integer;
roadfile:file of type_map;
begin
assign(roadfile,'road.txt'); {Связывание файлововой переменной с самим файлом}
reset(roadfile); {Файл типизированный, значит процедурой reset открываю его для чтения и записи}
write('Введите начальный и конечный города -> ');
readln(city1,city2); {Эти переменные пока не используются}
write('Введите количество дорог -> ');
readln(road);
for i:=1 to road do {Цикл, в ходе которого всем заданным дорогам присваивается длина и пошлина}
begin
with map[city1,city2,i] do {Открываю доступ к полям записи для их редактирования}
begin
write('Введите длину ',i,' дороги -> ');
readln(dlina);
Write('Введите пошлину ',i,' дороги -> ');
readln(poshlina);
end;
write(roadfile,map); {Ошибка здесь}
end;
close(roadfile);
end.
Levitra Farmacia Italia