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


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

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

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


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

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

Ты приведи сам алгоритм, которым ты собираешься пользоваться. Тот самый, теретический, который ты понимаешь. Это и есть больше половины задачи. А массивы - какая разница, скольки они мерные..


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


Новичок
*

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

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


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

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

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

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


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


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

Группа: Пользователи
Сообщений: 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 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

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

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


Хорошо. Спасибо. Если возникнут вопросы, напишу ещё.


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


Новичок
*

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

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


Сегодня, не без помощи препода понял, что от меня нужно, но как вы и предполагали возникла проблема с сохранением данных в файл. Вопрос написан в комментариях. Вот код:

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 -


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


Новичок
*

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

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


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

Я не могу понять, как правильно занести инфу в файл. Если целиком массив не получится туда поместить, то тогда только по одному элементу массива? И ещё, туда ли я ставлю процедуру записи в файл?

Сообщение отредактировано: S!n -


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

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

 





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