Автор | Сообщение |
Ass
5 сообщений |
#702 2009-11-06 09:15 GMT+3 часа(ов) |
Очень прошу помочь!
Написать программу на языке XLisp, определяющую эйлеровый путь, начинающийся с заданной вершины в неориентированном графе. Заранее благодарен. |
|
VH
289 сообщений |
#712 2009-11-10 03:23 GMT+3 часа(ов) |
Для неориентированного графа без вершин с нечетными степенями (или с двумя вершинами нечетной степени), представленного в виде ((номер_вершины . список_связанных_вершин)...)
(defun F (Graph &optional (Stack (cons (caar Graph) nil)) (Result nil)) Например, для графа (<можно расположить вершины по кругу>) ((1 2 6)(2 1 3 5 6)(3 2 4 5 6)(4 3 5)(5 2 3 4 6)(6 1 2 3 5)) (F '((1 2 6)(2 1 3 5 6)(3 2 4 5 6)(4 3 5)(5 2 3 4 6)(6 1 2 3 5))) возвращает эйлеров цикл (1 2 3 4 5 2 6 3 5 6 1). При желании задать начальную вершину, а также если граф содержит <две> вершины нечетной степени (известно, что эйлеров путь начинается в одной из них), придется явно указать номер вершины (или предварительно вычислить его), например, для графа ((1 2 6)(2 1 3 6)(3 2 4 5 6)(4 3 5)(5 3 4 6)(6 1 2 3 5)) (F '((1 2 6)(2 1 3 6)(3 2 4 5 6)(4 3 5)(5 3 4 6)(6 1 2 3 5)) '(2)) возвращает эйлеров путь (2 1 6 2 3 4 5 3 6 5). отредактировал(а) VH: 2009-11-10 03:31 GMT+3 часа(ов) |
|
Ass
5 сообщений |
#713 2009-11-11 15:04 GMT+3 часа(ов) |
VH! Огромное спасибо,
побегу набирать прогу и оформлять отчет. Надеюсь сдам. |
|
VH
289 сообщений |
#714 2009-11-11 15:44 GMT+3 часа(ов) |
Задание так сформулировано, что в принципе следует некую «оболочку» еще сделать - потому что граф препод может и каким-нибудь другим способом представить (надо будет в наше представление преобразовать), вершин нечетной степени может быть больше двух (в этом случае придется отказаться от вызова предоставленной функции), заданный номер начальной вершины (при наличии двух вершин нечетной степени) может быть неправильным.
|
|
Ass
5 сообщений |
#986 2009-12-29 18:12 GMT+3 часа(ов) |
VH! Дорогой друг, ты как в воду глядел!
Вот что препод ответил (новогодний подарок): Курсовая работа выполнена. Но … Ваши графы не содержат параллельные ребра, т. е. две вершины могут быть соединены только одним ребром. Это достаточно обременительное ограничение – в исходной задаче Эйлера о кенигсбергских мостах параллельные ребра как раз были. Если решать задачу с параллельными ребрами, тогда недостаточно идентифицировать ребра двумя вершинами, должны быть метки для ребер Можно ли легко переделать вашу программу, чтобы была возможность решать задачу для графа с параллельными ребрами? Может быть, надо ввести новые структуры данных? Ну чем не изверг, чего еще надо!? Насчет замечания о мостах с параллельными ребрами я с ним не согласен, тем более что в задании о них ни слова. Так что если есть возможность, помоги. Очень прошу!!! |
|
VH
289 сообщений |
#994 2009-12-29 23:40 GMT+3 часа(ов) |
Вам когда нужно?
--- отредактировал(а) VH: 2009-12-30 17:42 GMT+3 часа(ов) |
|
Ass
5 сообщений |
#995 2009-12-30 00:49 GMT+3 часа(ов) |
Огромное спасибо VH!
Чем раньше, тем лучше. Я отправляю по электронке (заочник), а через некоторое время получаю вот такие неутешительные рецензии. Сердечно поздравляю Вас с Новым Годом!!! |
|
Informal
1 сообщений |
#2113 2010-05-23 06:12 GMT+3 часа(ов) |
Здравствуйте! А сильно изменится программа, для нахождения Эйлерова цикла? Или все-таки если существует Эйлеров цикл, то всегда будет его возвращать (именно цикл)? Просто хотелось бы посмотреть на это. А то иногда может осуществлять переходы по несуществующим ребрам (например, в графе, в котором и Эйлерова пути нет).
|
|
Шмонов
4 сообщений |
#3925 2011-02-13 19:38 GMT+3 часа(ов) |
Кстати с помощью Lisp созданы: «Методы изобретательства, с помощью которых три программиста легко могут составить такие программы для компьютера, посредством которых компьютер может изобрести много изобретений без помощи человека». Это является названием произведения. Я полагаю, что эти программы можно продать за миллиарды долларов. Прошу вас способствовать тому чтобы было внедрено (то есть использовано) то что изложено в этом произведении. Я являюсь автором этого произведения. Есть положительные отзывы на это произведение. Это произведение и мой адрес изложены (в Интернете) на сайте www.55522.ru
отредактировал(а) Шмонов: 2011-02-13 20:43 GMT+3 часа(ов) |
|
Шмонов
4 сообщений |
#3926 2011-02-13 19:40 GMT+3 часа(ов) |
Между прочим я полагаю что с помощью Lisp создана программа для компьютера с помощью которой компьютер может изобрести много изобретений без помощи человека. Подробнее об этом изложено на сайте www.method.ru
отредактировал(а) Шмонов: 2011-02-13 20:46 GMT+3 часа(ов) |
|
misha![]()
1275 сообщений |
#3935 2011-02-13 21:00 GMT+3 часа(ов) |
PR?
|
|
megamanx
307 сообщений |
#3936 2011-02-13 21:42 GMT+3 часа(ов) |
Господин-товарищ-барин Шмонов (чуть не описался, Швоньдер), а этот спам руками писан, или ботом, которого автоматически написала программа, которая генерирует идеи и которая написана на лиспе?
Извините за тон - у меня только закончилась промывка мозга лекциями о методах ТРИЗ/АРИЗ, волшебной шляпе и жизненном пути Туполева. Вспоминаю этот безрадостный бред поёживаясь. P.S. Обобрение общественности - это всегда хорошо. |
|
I wish I'd made you angry earlier
|
|
joba
157 сообщений |
#3950 2011-02-16 17:23 GMT+3 часа(ов) |
>ТРИЗ
>бред Вот это Вы зря. |
|
megamanx
307 сообщений |
#3952 2011-02-17 17:50 GMT+3 часа(ов) |
Цитата Я отвечу на это, пусть даже придётся заводить журнал http://flakelisper.livejournal.com/819.html |
|
I wish I'd made you angry earlier
|
|
Hoya
2 сообщений |
#7778 2017-05-17 13:04 GMT+3 часа(ов) |
Доброго времени суток! можно как то этот алгоритм реализовать на чистом Lisp'е?
|
|