Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Pascal] Задача "Перегоны"

Автор: Denic 18.11.2006, 03:54

Помогите решить задачу:

На некоторой железнодорожной ветке расположено N станций, которые последовательно пронумерованны от 1 до N. Известны расстояния между некоторыми станциями. Надо вычислить длинны всех перегонов между станциями или указать, что это сделать нельзя (т.е информация либо противоречит или её недостаточно).

Даже незнаю как возможно есть какие-нибудь мысли или хотя бы алгоритм решения.

Автор: maxim1000 18.11.2006, 14:43

можно попробовать свести это к системе линейных уравнений (относительно попарных расстояний между соседними станциями)
а там уже посмотреть есть ли решения

Автор: Snowy 18.11.2006, 14:51

Перенесено из Паскаля

Автор: AlexST 18.11.2006, 21:16

Строим граф по принципу: вершины связаны между собой, если известно расстояние между ними (лучше сразу в виде матрицы). Проверяем: если из любой вершины можно попасть в любую, то задание решаемо. smile

(понятно что вариантов реализации куча, в т. ч. не через граф smile

)

Как найти расстояния писать надо?

Автор: Denic 18.11.2006, 23:26

Цитата(AlexST @ 18.11.2006, 21:16

)

Как найти расстояния писать надо?

Не надо

Цитата(AlexST @ 18.11.2006, 21:16

)

лучше сразу в виде матрицы

Да скорее всего, я тут подумал и придумал как решать, надо завети квадратную матрицу

Код


const
  n=100;
var 
  a: array[1..n,1..n] of real;
  i, j: integer; 
  x,y,d: integer;
  e: integer; // количества расстояний между извесными станциями
  .....

begin
  for i:=1 to n do
  for j:=1 to n do
  a[i,j]:=1;
  //читаем и заполняем матрицу "расстояниями"
  for i:=1 to e do
    begin
    Write('введите перегон №1');
    readln(x);
    Write('введите перегон №2');
    readln(x);
        Write('введите расстояние');
    readln(d);
    a[x,y]:=d;
  end;
end;

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

Автор: AlexST 19.11.2006, 13:47

Зачем везде 1? Нуль тогда уж...

Код


for i:=1 to n do
  for j:=1 to n do
  a[i,j]:=0;

Вот тут надо следить, что бы все элементы были расположены над гл. диагональю

Код


begin
    Write('введите перегон №1');
    readln(x);
    Write('введите перегон №2');
    readln(y);
    Write('введите расстояние');
    if x>y then readln(a[x,y])
              else readln(a[y,x]);
  end;

Дальше проверяем возможно ли связать все точки друг с другом. Здесь достаточно найти хотя бы один путь, проходящий по всем вершинам.
Потом вычисляем пути. Т. е. заполняем все клетки над диагональю.
Здесь напрашиваются закономерности:
[i, j]=[j-1, i]+[i, j-1]
[i, j]=[i-1, j]-[i-1, i]
[i, j]=[i, j+1]-[i, j+1]
Список можно продолжать. Теперь надо подумать как это организовать (итерации по вычислению путей, в смысле). Счас нет времени, подумаю - напишу ещё. smile

Да, откуда задача?

Автор: Denic 21.11.2006, 05:28

Цитата(AlexST @ 19.11.2006, 13:47

)

Зачем везде 1? Нуль тогда уж...
for i:=1 to n do
for j:=1 to n do
a[i,j]:=0;

Лучше -1 так как данные могут быть данны не корректные и придется проверять есть ли решения или данные противоречивые. Например в тестах было данно расстояние от 1-го до 1-го равно 1.

Цитата(AlexST @ 19.11.2006, 13:47

)

Да, откуда задача?

С районной олимпиады

Автор: AlexST 22.11.2006, 22:22

Цитата(Denic @ 21.11.2006, 05:28

)

Лучше -1 так как данные могут быть данны не корректные и придется проверять есть ли решения или данные противоречивые.

Согласен. Неподумал. Только насчёт некорректности (то бишь противоречивости) - алгоритм такой проверки по сложности не уступает самой задаче. Его реализовывать не надо было.

Цитата(Denic @ 21.11.2006, 05:28

)

Например в тестах было данно расстояние от 1-го до 1-го равно 1.

Да хоть -800. smile

Главная диагональ не измененяется и не участвует в процессе вычислений.

Цитата(Denic @ 21.11.2006, 05:28

)

С районной олимпиады

Ядрена корень. Вроде элементарно, но как это нормально реализовать придумать пока не получается. smile

Думал сёдня уже код дам, ан нет...

P. S. Сосредотачиваться на возможности связать все точки друг с другом я не буду. Понятно: берем любую вершину и проверяем, можно ли из неё попасть во все остальные.

Автор: Denic 23.11.2006, 06:43

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

Цитата(AlexST @ 22.11.2006, 22:22

)

Только насчёт некорректности (то бишь противоречивости) - алгоритм такой проверки по сложности не уступает самой задаче

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

Автор: AlexST 23.11.2006, 14:18

Не, ну всё далеко не так просто. smile

Сделаю скоро.

P. S.
Главную диагональ нет смысла обрабатывать.
Думается мне, что матрицу в топку.
Какие данные в твою прогу я не вводил - одно безобразие. )))) Хотя оно и понятно.
Вот тебе три матрицы. Тестируй прогу. smile

Автор: maxim1000 23.11.2006, 15:52

хм... создаётся впечатление, что моё предложение все просто пропустили smile

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

Автор: AlexST 23.11.2006, 15:54

Цитата(maxim1000 @ 23.11.2006, 15:52

)

создаётся впечатление, что моё предложение все просто пропустили

Нет.

Я как раз прогу делаю через уравнения. Мы просто посмотрели другой способ. Раз это олимпиадная задачка, то решение не должно использовать специальных знаний, например таких как решение матричных уравнений, имхо, а там не знаю...