IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Графы., Нахождение кратчайшего пути с наименьшей пошлиной за дорогу
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 16
Пол: Мужской
Реальное имя: Стас

Репутация: -  0  +


Задача звучит так: В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города А в город В с минимальной величиной 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



--------------------
"...Пропитанный злостью и никотином
Я навсегда останусь teen'ом.
Всегда семнадцать, всегда война
И вечный дождь с двух сторон окна..."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Новичок
*

Группа: Пользователи
Сообщений: 16
Пол: Мужской
Реальное имя: Стас

Репутация: -  0  +


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

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

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

Должен содержать инфу о длине дороги и стоимости. Я просто не знаю, каким образом мне это реализовать.


--------------------
"...Пропитанный злостью и никотином
Я навсегда останусь teen'ом.
Всегда семнадцать, всегда война
И вечный дождь с двух сторон окна..."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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

Читай теорию по графам.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 4.05.2024 18:13
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name