Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Pascal] Задача "Перегоны" 
:(
    Опции темы
Denic
Дата 18.11.2006, 03:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 41
Регистрация: 7.10.2005

Репутация: нет
Всего: нет
  Помогите решить задачу:

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

 Даже незнаю как возможно есть какие-нибудь мысли или хотя бы алгоритм решения. 
PM MAIL   Вверх
maxim1000
Дата 18.11.2006, 14:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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


--------------------
qqq
PM WWW   Вверх
Snowy
Дата 18.11.2006, 14:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 11363
Регистрация: 13.10.2004
Где: Питер

Репутация: 4
Всего: 484
Перенесено из Паскаля
PM MAIL   Вверх
AlexST
Дата 18.11.2006, 21:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 331
Регистрация: 30.4.2006
Где: Москва

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

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

Это сообщение отредактировал(а) AlexST - 18.11.2006, 21:17
PM MAIL ICQ   Вверх
Denic
Дата 18.11.2006, 23:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 41
Регистрация: 7.10.2005

Репутация: нет
Всего: нет
  
Цитата(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;

 А дальше, я так думаю, надо вычислить неизвестные растояния. И посмотреть что получится. Диагональ над главной, будет ответом.
PM MAIL   Вверх
AlexST
Дата 19.11.2006, 13:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 331
Регистрация: 30.4.2006
Где: Москва

Репутация: 2
Всего: 3
Зачем везде 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 

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

Это сообщение отредактировал(а) AlexST - 19.11.2006, 13:50
PM MAIL ICQ   Вверх
Denic
Дата 21.11.2006, 05:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 41
Регистрация: 7.10.2005

Репутация: нет
Всего: нет
Цитата(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 Найти цитируемый пост)
Да, откуда задача?

 С районной олимпиады
PM MAIL   Вверх
AlexST
Дата 22.11.2006, 22:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 331
Регистрация: 30.4.2006
Где: Москва

Репутация: 2
Всего: 3
Цитата(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 Ядрена корень. Вроде элементарно, но как это нормально реализовать придумать пока не получается.  smile
Думал сёдня уже код дам, ан нет...

P. S. Сосредотачиваться на возможности связать все точки друг с другом я не буду. Понятно: берем любую вершину и проверяем, можно ли из неё попасть во все остальные.
PM MAIL ICQ   Вверх
Denic
Дата 23.11.2006, 06:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 41
Регистрация: 7.10.2005

Репутация: нет
Всего: нет
По моему задача не такая уж сложная, я тут набросал программку её надо ещё доделать, но она вроде всё правильно считает осталось, только сделать проверки на корректность данных и вывести результаты. Нужные числа над главной диагональю.
 
Цитата(AlexST @  22.11.2006,  22:22 Найти цитируемый пост)
Только насчёт некорректности (то бишь противоречивости) - алгоритм такой проверки по сложности не уступает самой задаче

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

Присоединённый файл ( Кол-во скачиваний: 10 )
Присоединённый файл  3.rar 4,87 Kb
PM MAIL   Вверх
AlexST
Дата 23.11.2006, 14:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 331
Регистрация: 30.4.2006
Где: Москва

Репутация: 2
Всего: 3
Не, ну всё далеко не так просто.  smile 
Сделаю скоро.

P. S. 
Главную диагональ нет смысла обрабатывать.
Думается мне, что матрицу в топку.
Какие данные в твою прогу я не вводил - одно безобразие. )))) Хотя оно и понятно.
Вот тебе три матрицы. Тестируй прогу.  smile 
user posted image
PM MAIL ICQ   Вверх
maxim1000
Дата 23.11.2006, 15:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110
хм... создаётся впечатление, что моё предложение все просто пропустили smile
может, конечно, я ошибаюсь, но после представления задачи в виде системы линейных уравнений, она становится тривиальной...


--------------------
qqq
PM WWW   Вверх
AlexST
Дата 23.11.2006, 15:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 331
Регистрация: 30.4.2006
Где: Москва

Репутация: 2
Всего: 3
Цитата(maxim1000 @  23.11.2006,  15:52 Найти цитируемый пост)
создаётся впечатление, что моё предложение все просто пропустили 
Нет.  smile  Я как раз прогу делаю через уравнения. Мы просто посмотрели другой способ. Раз это олимпиадная задачка, то решение не должно использовать специальных знаний, например таких как решение матричных уравнений, имхо, а там не знаю...


Это сообщение отредактировал(а) AlexST - 23.11.2006, 16:00
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0834 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.