Помощь - Поиск - Пользователи - Календарь
Полная версия: Графы.
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
S!n
Задача звучит так: В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города А в город В с минимальной величиной 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

Lapp
Что-то ты переусердствовал...
Зачем тебе это:
Type
<Запись>=record
dlina:integer; {Длина дороги (км)}
poshlina:integer; {Пошлина за проезд по одной дороге}
end;
<Массив1>=array[dlina,poshlina] of <Запись>;
- ?
Сами по себе координаты элемента массива уже содержат информацию, которую ты собираешься хранить в нем. Какой смысл? Взать, например, элемент [2,3] и присвоить ему запись, в которой двойка и тройка?.. blink.gif

Похоже, что в твоем трехмерном массиве имеет смысл просто хранить эти самые записи. Но с ним тоже не вполне ясно. Как ты будешь эту инфу рассчитывать? И она неоднозначная..

Ты приведи сам алгоритм, которым ты собираешься пользоваться. Тот самый, теретический, который ты понимаешь. Это и есть больше половины задачи. А массивы - какая разница, скольки они мерные..
S!n
Хм... алгоритм... Алгоритм назвать не могу, так как впервые имею дело с графами.
Могу по пунктам расписать, что мне нужно сделать:
1) Создание файла в который будет заноситься информация о количестве дорог между городами, расстояние и пошлина за каждую дорогу.
2) Ввод данных
3) Сохранение данных в файл
4) Сравнение каждого из элементов файла и нахождение самого короткого пути с самой маленькой пошлиной.
5) Вывод на экран сообщения о найденном пути
6) Возможность изменения элементов файла, добавление новых дорог.

Цитата
Сами по себе координаты элемента массива уже содержат информацию, которую ты собираешься хранить в нем. Какой смысл? Взать, например, элемент [2,3] и присвоить ему запись, в которой двойка и тройка?.. blink.gif

Видишь-ли, в чем дело. Последний элемент моего трехмерного массива:
<Масив2>:array[<Город А>,<Город В>,<КОЛ-ВО ПУТЕЙ МЕЖДУ ГОРОДАМИ>] of <Массив1>

Должен содержать инфу о длине дороги и стоимости. Я просто не знаю, каким образом мне это реализовать.
Lapp
Цитата(S!n @ 2.12.2008 16:02) *
2) Ввод данных
Вот эти два слова - это и есть та самая теория, которую, как я теперь вижу, ты, несмотря на твои слова, не представляешь. Создание, запись файлов - это пара операторов, да и не нужно это.. А вот КАК ты будешь сканить возможные пути - это как раз важно. У тебя об этом ни слова..
Советую тебе поискать по Форуму. Задачи подобного рода делались неоднократно. А лучше, если честно, возьми учебник по графам.. Будешь _действительно_ представлять себе теорию - программа приложится..

Цитата(S!n @ 2.12.2008 16:02) *
Видишь-ли, в чем дело. Последний элемент моего ...
Я вижу в чем дело: на вопрос отвечать не считаешь нужным.

Цитата(S!n @ 2.12.2008 16:02) *
Я просто не знаю, каким образом мне это реализовать.
Ты не только не знаешь КАК реализовать. Ты также не знаешь, ЧТО - и это важнее.

Читай теорию по графам.
S!n
Хорошо. Спасибо. Если возникнут вопросы, напишу ещё.
S!n
Сегодня, не без помощи препода понял, что от меня нужно, но как вы и предполагали возникла проблема с сохранением данных в файл. Вопрос написан в комментариях. Вот код:

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.
S!n
Изменил свою прогу таким образом (Изменение в разделе 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.

Я не могу понять, как правильно занести инфу в файл. Если целиком массив не получится туда поместить, то тогда только по одному элементу массива? И ещё, туда ли я ставлю процедуру записи в файл?
does viagra give you more stamin
Levitra Farmacia Italia
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.