Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 27.07.2008, 18:50   #1
kopzone
Новичок
Джуниор
 
Регистрация: 27.07.2008
Сообщений: 2
Печаль Задача на граф

Задали решить задачку но чет туплю..а времени в обрез.. если кто поможет буду признателен..обязательные параметры (Delphi)з.ы. не силен.
Задачка:
Имеется n филиалов организации, связанных вычислительной сетью (см. рис.). Стоимость передачи информации по сети зависит от расстояния, на которое необ-ходимо переслать информацию. Определите филиал для размещения сервера ба-зы данных, который располагается на расстоянии, не превышающем L км от наи-большего количества филиалов.

Вот так выглядит граф
Формат входных данных:
Предусмотреть ввод L с клавиатуры, матрица смежности вводится из файла
Пример файла входных данных
0 70 0 0 0 80 0 0
70 0 50 0 0 0 0 0
0 50 0 40 0 0 0 0
0 0 40 0 10 0 0 0
0 0 0 10 0 20 0 0
80 0 0 0 20 0 30 0
0 0 0 0 0 30 0 110
0 0 0 0 0 0 110 0
Пример выходных данных при L=50км
5

к сведению эта задача была на облостной олимпиаде..в 1995 году(( жалко там не выложили решения

From Stilet: Тему нужно называть так чтоб было не стыдно ее читать. В следующий раз удалю

Последний раз редактировалось Stilet; 28.07.2008 в 10:22.
kopzone вне форума Ответить с цитированием
Старый 27.07.2008, 21:20   #2
zetrix
Delphi/C++/C#
Участник клуба
 
Аватар для zetrix
 
Регистрация: 29.10.2006
Сообщений: 1,972
По умолчанию

Так это ж обычная матрица ценности. Типичная задачка. Решается рекурсивным методом для каждого узла. От него рассматриваются все маршруты. Переходим от одного узла к другому, исключая те узлы, через которые мы прошли. Условием прекращения рекурсии: нет узлов, через которые можно пройти.
В итоге для каждого узла находим длины путей удовлетворяющих исловию (меньше Л). Заносим в массив кол-во узлов удовлетворяющих условию. Затем находим максимальное значение в получившемся массиве.
Сейчас посмотрю... Подобную задачку делали на парах на 2 курсе...
------ спустя 40 минут ------
Надо же, нашёл)
В программе задача: найти кратчайший путь из одного города в другой. В самом начале задаются города и расстояния между ними. Как наработка сойдёт. Для вашей задачи придётся переделать.

Да кстати, задавать города лучше смотря на рисунок, иначе можно запутаться. Я старался сделать как можно подробнее программу.
Вложения
Тип файла: rar 10_2.rar (1.2 Кб, 20 просмотров)

Последний раз редактировалось zetrix; 27.07.2008 в 22:28.
zetrix вне форума Ответить с цитированием
Старый 27.07.2008, 22:01   #3
pu4koff
Старожил
 
Аватар для pu4koff
 
Регистрация: 22.05.2007
Сообщений: 9,065
По умолчанию

а тут разве не просто пройти по строкам и для каждой строки подсчитать количество элементов > L и ищем среди этих значений максимум
pu4koff вне форума Ответить с цитированием
Старый 27.07.2008, 22:25   #4
zetrix
Delphi/C++/C#
Участник клуба
 
Аватар для zetrix
 
Регистрация: 29.10.2006
Сообщений: 1,972
По умолчанию

нет не проще.
Ведь возможна ситуация, когда допустим филиалы 1,2,3,4 образуют цепочку, суммарной длинной < L и в итоге вариант с этой цепочкой может быть оптимальным. По строкам вы вообще не выйдите на такой вариант.
zetrix вне форума Ответить с цитированием
Старый 27.07.2008, 23:10   #5
kopzone
Новичок
Джуниор
 
Регистрация: 27.07.2008
Сообщений: 2
По умолчанию

Я пробовал численнымми методами..Метод нахождения остова минимального веса в звешеном графе.. там по сути алгоритм схожий..но как то он не пошел.. Спасиб за помщь.. щаз гляну попробую разобораться
kopzone вне форума Ответить с цитированием
Старый 27.07.2008, 23:14   #6
pu4koff
Старожил
 
Аватар для pu4koff
 
Регистрация: 22.05.2007
Сообщений: 9,065
По умолчанию

Цитата:
Сообщение от zetrix Посмотреть сообщение
нет не проще.
Ведь возможна ситуация, когда допустим филиалы 1,2,3,4 образуют цепочку, суммарной длинной < L и в итоге вариант с этой цепочкой может быть оптимальным. По строкам вы вообще не выйдите на такой вариант.
действительно. извиняюсь. об этом как-то не подумал я
pu4koff вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
переменная в граф. режиме. t13sto Паскаль, Turbo Pascal, PascalABC.NET 7 21.07.2008 14:25
Граф в паскале LLIypLLIyH Помощь студентам 10 16.06.2008 14:09
Граф в Делфи консоль LLIypLLIyH Помощь студентам 6 12.06.2008 18:20
Ошибка граф. драйвера satana Паскаль, Turbo Pascal, PascalABC.NET 1 15.10.2007 17:22