Задача с графами |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Задача с графами |
Ольга |
Сообщение
#1
|
Гость |
Пожалуйста, очень нужно!
Задаем количество вершин, какая с какой соединяется(каждой присваивается номер) и главную вершину.Необходимо вывести кол-во достижимых и недостижимых от главной вершины и граф:вершины(с номером внутри) соединены стрелками(как задали), главная вершина-красного цвета,достижимые-синего,недостижимые-зеленого.(решить с использованием матрицы смежности). |
Altair |
Сообщение
#2
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Для решения этой задачи используют модифицированный алгоритм Флойда, носящий название "транзитивное замыкание матрицы" или Улгоритм Уоршала.
вот процедура... type Здесь С- матрица стоимостей совпадает с матрицей смежности. Т.е. c[i,j]=1 только если есть дуга i-j в матрице а получим где есть 1 там есть путь от одной вершины к другой. Матрица А как раз и будет транзитивным замыканием матрицы смежности. Про Алгоритм Флойда, прочтешь здесь: http://forum.pascal.net.ru/index.php?showt...indpost&p=40473 А вот графическая реализация если нужна, то стоит у Вольво попросить модуль для рисования наклонных стрелок -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Altair |
Сообщение
#3
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Вот я тут поразвлекся, и к чему пришел.
граф взял этот, но вершину 19 изолировал. Матрицу смежности занес в файл g.txt - g.txt ( 2.11 килобайт ) Кол-во скачиваний: 659 Программа: (компилятор FPC)
EXE и исходник в архиве - Bin.rar ( 24.97 килобайт ) Кол-во скачиваний: 520 В результате получилось для данного графа: Единственно чего нет - стрелок... доработайте... и посмотрите, возможны какие-то глюки, я только на этом грфе тестировал. Но главное алгоритмы... p.s. если надо для TP, можно удет переделать... p..s на скрине возможно цвета не различимы, но все как надо, это при сжатии рисунка исказилось Добавил позже. насчет вывод графа на экран. я выодил по сетке.. может быть будет красивее если сделать по рандому от размера экрана.. тогда распределение будет всегда равномерным.... -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
volvo |
Сообщение
#4
|
Гость |
Ольга,
в присоединенном файле - адаптация программы Altair-а для Турбо-Паскаля. Обрати внимание: значение константы nn уменьшено до 50, иначе будет ошибка компилятора "Слишком много данных". Кроме этого, первой строкой программы должно быть: {$n+}, иначе моя процедура не будет работать... Прикрепленные файлы GRAPHOUT.PAS ( 3.54 килобайт ) Кол-во скачиваний: 367 |
Ольга |
Сообщение
#5
|
Гость |
Когда я пытаюсь запустить программу выдается Error 200: Division by zero.
|
Ольга |
Сообщение
#6
|
Гость |
Я не то запускала. А как сделать, чтобы вершины шли по кругу, запрашивалось кол-во вершин и как они соединяются?
|
volvo |
Сообщение
#7
|
Гость |
Ольга, для этого надо было все это указывать СРАЗУ в задании. Сколько раз можно повторять? Сделать программу сложно, ПЕРЕДЕЛЫВАТЬ - еще сложнее.
|
Altair |
Сообщение
#8
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Цитата Когда я пытаюсь запустить программу выдается Error 200: Division by zero. Модуль CRT пропатчите. Цитата Сделать программу сложно, ПЕРЕДЕЛЫВАТЬ - еще сложнее. Дейтсвительно, ну что такое ? :sad: -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
what are the risks of taking gab |
Сообщение
#9
|
Гость |
Precio De Levitra En Farmacias
|
where can i buy prednisone witho |
Сообщение
#10
|
Гость |
Canadian Pharmacies Nexium
|
hydroxychloroquine for sale onli |
Сообщение
#11
|
Гость |
Cialis For Sale From Canada
|
Текстовая версия | 23.12.2024 16:31 |