Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
Yorkfield
1 / 1 / 0
Регистрация: 17.02.2009
Сообщений: 13
1

Поезд. Проложение самого дешевого маршрута.

01.05.2009, 23:09. Просмотров 2459. Ответов 5
Метки нет (Все метки)

Здравствуйте, есть такая задачка:
Есть поезд, он двигается по станциям(1->2->3->4->...->n), проезд с 1->n стоит 1000руб., с 1->3 стоит 50руб., с 3->n стоит 850руб.
Получается если человек поедет таким маршрутом: 1->3->n он заплатит в сумме 900руб., а если 1->n он заплатит 1000руб.
Вопрос: Нужно проложить самый дешевый маршрут. Информатик сказал нужен двойной массив. Если решите, можете объяснить поподробнее, я не понял, как ее делать.)
Получилась такая таблица:
| 1 | 2 | 3 | 4 | 5 | .... | n |
1|.0.......50..................1000
2|.....0..............................
3|..........0....................850
4|...............0....................
5|....................0...............
.|.....................................
.|.....................................
.|.....................................
.|.....................................
n|..................................0.

с 1->1 = 2->2= 3->3 проезд стоит 0 руб, ну это понятно, потомц что вы ничего не проехали), с1->3 стоит 50руб, с 3-> n стоит 850 руб, и все аналогично так же..
Ну вот все что сказал по этой задаче наш мнформатик... Помогите решить пожалуйста!

Добавлено через 6 часов 44 минуты 28 секунд
Кто нибудь, возьмитесь за эту задачу пожалуйста.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2009, 23:09
Ответы с готовыми решениями:

Определить стоимость самого дешевого блюда в меню ресторана "Дракон"
Помогите с задачей: Составить программу, выводящую на экран меню ресторана "Дракон" (наименование...

По введенному номеру маршрута вывести на печать вид транспорта, начальный и конечный пункт маршрута
Написать программу по созданию файла записей, содержащих сведения согласно условию задачи: Номер...

Определить стоимость самого дешевого блюда в ресторане
Помогите с задачей на записи: Составить программу, выводящую на экран меню ресторана "Дракон"...

Определить длину самого оптимального маршрута движения человека
Даны координаты четырех точек на плоскости (x1, y1, x2, y2, x3, y3, x4, y4). Человек может начинать...

Проложение маршрута
Добрый день, интересует вопрос: нужно проложить маршрут в админке с помощью карты, попытался...

5
lexus_ilia
3062 / 722 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
02.05.2009, 02:09 2
Вопрос: "А чему тогда равны остальные значения у данной Вами "таблице" ?".
Просто то что Вы говорите можно решить при помощи алгоритмов используемых над графами, а та таблица ,что у Вас, похожа на таблицу смежности, но если у Вас информатик и Вы не в универе (или колледже), то решение проще...
Хотя и с графами не особо сложно...
0
Yorkfield
1 / 1 / 0
Регистрация: 17.02.2009
Сообщений: 13
02.05.2009, 21:09  [ТС] 3
остальные данные неизвестны...
lexus_ilia
я учусь в школе, если не сложно можете написать, и объяснить, как ее решать? Буду очень вам признателен.
0
lexus_ilia
3062 / 722 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
02.05.2009, 21:46 4
Цитата Сообщение от Yorkfield Посмотреть сообщение
остальные данные неизвестны
Просто как можно прокладывать маршрут не зная стоимости от всех остальных станций ? Может есть какая-то аналогия в высчитывании стоимости, если это так, то всё решаемо, а если нет, то не решаемо...
Или может стоимости вносит пользователь ?
0
Messenger of G.
Посланник моего господина
110 / 105 / 52
Регистрация: 02.05.2009
Сообщений: 181
02.05.2009, 22:18 5
Насколько я правильно понял задачу, необходимо по таблице стоимости проезда (a,b) между станциями a и b определить наименшую стоимость проезда от первой до последней. Тогда стоит использовать ДП. Например, пусть дана матрица А, хранящая стоимости прямых рейсов. Создаем массив С, который содержит минимальную стоимость проезда между станциями (a,b) и заполняем его по следующим правилам:
1) C[a,a]=0
2) C[a,a+1]=A[a,a+1]
3) C[a,a+2]=min(A[a,a+2];A[a,a+1]+A[a+1,a+2])
4) C[a,a+k]=min(С[a,a+i]+С[a+i,a+k]) для всех i in [1..k].
Для последнего пункта важен порадок заполнения, а именно по возрастанию k.
Если такой вариант подходит, могу привести пример реализации (но несколько позже)

Добавлено через 25 минут 6 секунд
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
program Train;
const max=5;
var F:Text;
s:string;
A,C:array[1..max,1..max] of word;
n,i,k,j:word;
begin
Assign(F,'source.txt');
Reset(F);
readln(F,n);
for i:=1 to n do
    for j:=1 to n do
        read(F,A[i,j]);
Close(F);
fillchar(C,sizeof(C),0);
for k:=1 to n-1 do {самый дешевый переезд через к станций}
    begin
         for j:=1 to n-k do {переезд от j до j+k станции}
             begin
                  C[j,j+k]:=A[j,j+k]; {первый вариант — напрямую}
                  for i:=j+1 to j+k-1 do {либо пересадка на i-й станции, если таковая имеется (если билет не прямой, пересадка будет; если несколько пересадок на идеальном маршруте, не важно, как опору берем любую, все равно все учтем)}
                      if C[j,i]+C[i,j+k]<C[j,j+k] {если наименшая стоимость маршрута до и после пересадки менее имеющегося оптимизированого маршрута, то этот маршрут лучше}
                         then C[j,j+k]:=C[j,i]+C[i,j+k];
             end;
    end;
writeln(C[1,n]);
end.
И пример входного файла source.txt
Код
3
0 1 3
1 0 1
3 1 0
Я только на базовых примерах тестировал алгоритм, поэтому указывайте на ошибки, если таковые имеются в коде.
0
Yorkfield
1 / 1 / 0
Регистрация: 17.02.2009
Сообщений: 13
03.05.2009, 23:46  [ТС] 6
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
(*
  { Created in 03.05.2009 11:05:59 }
{$APPTYPE CONSOLE}
*)
program a6;
 const n=100;
 var
  tab: array[1..n, 1..n] of integer;
  i, j, k, Last, Counter: integer;
  s, Path, MinPath: string;
  Sum, MinSum: Longint;
 procedure Oi(x1: integer);
  var
   i: integer;
  begin
   for i:=x1+1 to Last do begin
    if tab[x1, i]>0 then begin
     inc(tab[x1, i], Sum);
     Str(i, s);
     Path:=Path+'>'+s;
     if i<Last then Oi(i) else begin
      writeln('Маршрут: ', Path, '  Цена = ', Sum);
      if (MinSum<0) or (MinSum>Sum) then begin
       MinPath:=Path;
       MinSum:=Sum
      end
     end;
     dec(Sum, tab[x1, i]);
     while Path[Length(Path)]<>'-' do Delete(Path, Length(Path), 1);
     Delete(Path, Length(Path), 1)
    end;
   end;
  end;
BEGIN
 FillChar(tab, SizeOf(tab), 0);
 writeln('Введите номер конечного пункта.');
 Readln(Last);
 writeln('Введите количество разрешённых проездов.');
 Readln(Counter);
 writeln('Введите разрешённые проезды и их стоимость (начало конец стоимость).');
 for k:=1 to Counter do read(i, j, tab[i, j]);
 for i:=1 to Last do begin
  for j:=1 to Last do
   if i=j then write('.0...') else if tab[i,j]=0 then write('.....') else write(tab[i, j]: 5);
  writeln
 end;
 Path:='1';
 MinPath:='';
 Sum:=0;
 MinSum:=-1;
 Oi(1);
 writeln;
 if MinSum<0 then writeln('Поездка невозможна.') else begin
  writeln('Лучший маршрут: ', MinPath);
  writeln('Цена лучшего маршрута = ', MinSum)
 end
(*
Введите номер конечного пункта.
5
Введите количество разрешённых проездов.
3
Введите разрешённые проезды и их стоимость (начало конец стоимость).
1 5 1000
1 3 50
3 5 850
.0........   50..... 1000
......0..................
...........0........  850
................0........
.....................0...
Маршрут: 1->3->5  Цена = 900
Маршрут: 1->5  Цена = 1000
 
Лучший маршрут: 1->3->5
Цена лучшего маршрута = 900
*)
END.
Добавлено через 34 секунды
ну как оцените, экспоненциальный алгоритм.
0
03.05.2009, 23:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2009, 23:46

Как создать проложение маршрута на карте на своем сайте?
Как создать проложение маршрута на карте на своем сайте? какими тэгами прописать?

SWI Prolog: Поиски дешевого маршрута
Здравствуйте, помогите пожалуйста с реализацией алгоритма поиска маршрута из точки А в Z по самому...

Программа для выбора самого дешевого ПК
Доброго времени суток, я только начинаю свой путь по вселенной Lisp, и вот уже столкнулся из...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru