> 1 <

Автор Сообщение

Ass

Members


Статус

5 сообщений

Где: Kazakhstan
Род занятий:
Возраст:

#702   2009-11-06 09:15 GMT+3 часа(ов)      
Очень прошу помочь!
Написать программу на языке XLisp, определяющую эйлеровый путь, начинающийся с заданной вершины в неориентированном графе.
Заранее благодарен.

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#712   2009-11-10 03:23 GMT+3 часа(ов)      
Для неориентированного графа без вершин с нечетными степенями (или с двумя вершинами нечетной степени), представленного в виде ((номер_вершины . список_связанных_вершин)...)
(defun F (Graph &optional (Stack (cons (caar Graph) nil)) (Result nil))
(if Stack
((lambda (curr_vertex)
((lambda (curr_record)
(if (cdr curr_record)
((lambda (next_vertex)
(F
((lambda (new_Graph)
((lambda (next_record)
(subst (remove curr_vertex next_record) next_record new_Graph))
(assoc next_vertex new_Graph)))
(subst (remove next_vertex curr_record) curr_record Graph))
(cons next_vertex Stack)
Result))
(cadr curr_record))
(F Graph (cdr Stack) (cons curr_vertex Result))))
(assoc curr_vertex Graph)))
(car Stack))
Result))

Например, для графа (<можно расположить вершины по кругу>)
((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

Members


Статус

5 сообщений

Где: Kazakhstan
Род занятий:
Возраст:

#713   2009-11-11 15:04 GMT+3 часа(ов)      
VH! Огромное спасибо,
побегу набирать прогу и оформлять отчет.
Надеюсь сдам.

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#714   2009-11-11 15:44 GMT+3 часа(ов)      
Задание так сформулировано, что в принципе следует некую «оболочку» еще сделать - потому что граф препод может и каким-нибудь другим способом представить (надо будет в наше представление преобразовать), вершин нечетной степени может быть больше двух (в этом случае придется отказаться от вызова предоставленной функции), заданный номер начальной вершины (при наличии двух вершин нечетной степени) может быть неправильным.

Ass

Members


Статус

5 сообщений

Где: Kazakhstan
Род занятий:
Возраст:

#986   2009-12-29 18:12 GMT+3 часа(ов)      
VH! Дорогой друг, ты как в воду глядел!
Вот что препод ответил (новогодний подарок):
Курсовая работа выполнена.
Но …
Ваши графы не содержат параллельные ребра, т. е. две вершины могут быть соединены только одним ребром. Это достаточно обременительное ограничение – в исходной задаче Эйлера о кенигсбергских мостах параллельные ребра как раз были.
Если решать задачу с параллельными ребрами, тогда недостаточно идентифицировать ребра двумя вершинами, должны быть метки для ребер
Можно ли легко переделать вашу программу, чтобы была возможность решать задачу для графа с параллельными ребрами? Может быть, надо ввести новые структуры данных?

Ну чем не изверг, чего еще надо!?
Насчет замечания о мостах с параллельными ребрами я с ним не согласен, тем более что в задании о них ни слова.
Так что если есть возможность, помоги. Очень прошу!!!

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#994   2009-12-29 23:40 GMT+3 часа(ов)      
Вам когда нужно?
А то уже готово.
Для возможности решения задачи «с параллельными ребрами» <проще всего> можно повторно включать номер вершины в 'список связанных вершин' и вместо <встроенной> функции (remove) использовать <собственную> функцию (REMOVE_FIRST), которая исключает из данного списка 'seq' только первый экземпляр данного элемента 'elem' (если они там присутствуют).
(defun REMOVE_FIRST (elem seq)
(if seq
(if (equal (car seq) elem)
(cdr seq)
(cons (car seq) (REMOVE_FIRST elem (cdr seq))))))

Функция (F) теперь определяется следующим образом:
(defun F (Graph &optional (Stack (cons (caar Graph) nil)) (Result nil))
(if Stack
((lambda (curr_vertex)
((lambda (curr_record)
(if (cdr curr_record)
((lambda (next_vertex)
(F
((lambda (new_Graph)
((lambda (next_record)
(subst (REMOVE_FIRST curr_vertex next_record) next_record new_Graph))
(assoc next_vertex new_Graph)))
(subst (REMOVE_FIRST next_vertex curr_record) curr_record Graph))
(cons next_vertex Stack)
Result))
(cadr curr_record))
(F Graph (cdr Stack) (cons curr_vertex Result))))
(assoc curr_vertex Graph)))
(car Stack))
Result))

Добавим ребро между вершинами 1 и 2 в первый из ранее представленных графов (при этом получаются две вершины нечетной степени!, так что нам просто повезло, что функция начинает поиск эйлерова пути с одной из них)
(F '((1 2 2 6)(2 1 1 3 5 6)(3 2 4 5 6)(4 3 5)(5 2 3 4 6)(6 1 2 3 5)))
Однако задача создания «оболочки» по-прежнему важна.
Но относительно кёнигсбергских мостов препод прав - они «параллельны», но и это нам на руку - не важно, по какому именно «мосту» идти от одной вершины к другой, если «мостов» несколько, так что и именовать их нет нужды.


---

отредактировал(а) VH: 2009-12-30 17:42 GMT+3 часа(ов)

Ass

Members


Статус

5 сообщений

Где: Kazakhstan
Род занятий:
Возраст:

#995   2009-12-30 00:49 GMT+3 часа(ов)      
Огромное спасибо VH!
Чем раньше, тем лучше.
Я отправляю по электронке (заочник),
а через некоторое время получаю вот такие неутешительные рецензии.

Сердечно поздравляю Вас с Новым Годом!!!

Informal

Members


Статус

1 сообщений

Где: Russia
Род занятий: IT
Возраст:

#2113   2010-05-23 06:12 GMT+3 часа(ов)      
Здравствуйте! А сильно изменится программа, для нахождения Эйлерова цикла? Или все-таки если существует Эйлеров цикл, то всегда будет его возвращать (именно цикл)? Просто хотелось бы посмотреть на это. А то иногда может осуществлять переходы по несуществующим ребрам (например, в графе, в котором и Эйлерова пути нет).

Шмонов

Members


Статус

4 сообщений
http://www.55522.ru
Где: Russia
Род занятий:
Возраст: 65

#3925   2011-02-13 19:38 GMT+3 часа(ов)      
Кстати с помощью Lisp созданы: «Методы изобретательства, с помощью которых три программиста легко могут составить такие программы для компьютера, посредством которых компьютер может изобрести много изобретений без помощи человека». Это является названием произведения. Я полагаю, что эти программы можно продать за миллиарды долларов. Прошу вас способствовать тому чтобы было внедрено (то есть использовано) то что изложено в этом произведении. Я являюсь автором этого произведения. Есть положительные отзывы на это произведение. Это произведение и мой адрес изложены (в Интернете) на сайте www.55522.ru

отредактировал(а) Шмонов: 2011-02-13 20:43 GMT+3 часа(ов)

Шмонов

Members


Статус

4 сообщений
http://www.55522.ru
Где: Russia
Род занятий:
Возраст: 65

#3926   2011-02-13 19:40 GMT+3 часа(ов)      
Между прочим я полагаю что с помощью Lisp создана программа для компьютера с помощью которой компьютер может изобрести много изобретений без помощи человека. Подробнее об этом изложено на сайте www.method.ru

отредактировал(а) Шмонов: 2011-02-13 20:46 GMT+3 часа(ов)

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#3935   2011-02-13 21:00 GMT+3 часа(ов)      
PR?

megamanx

Members


Статус

307 сообщений

Где: Russia
Род занятий:
Возраст:

#3936   2011-02-13 21:42 GMT+3 часа(ов)      
Господин-товарищ-барин Шмонов (чуть не описался, Швоньдер), а этот спам руками писан, или ботом, которого автоматически написала программа, которая генерирует идеи и которая написана на лиспе?
Извините за тон - у меня только закончилась промывка мозга лекциями о методах ТРИЗ/АРИЗ, волшебной шляпе и жизненном пути Туполева. Вспоминаю этот безрадостный бред поёживаясь.
P.S. Обобрение общественности - это всегда хорошо.
I wish I'd made you angry earlier

joba

Members


Статус

157 сообщений

Где: ---
Род занятий:
Возраст:

#3950   2011-02-16 17:23 GMT+3 часа(ов)      
>ТРИЗ
>бред
Вот это Вы зря.

megamanx

Members


Статус

307 сообщений

Где: Russia
Род занятий:
Возраст:

#3952   2011-02-17 17:50 GMT+3 часа(ов)      
Цитата
>ТРИЗ
>бред
Вот это Вы зря.

Я отвечу на это, пусть даже придётся заводить журнал
http://flakelisper.livejournal.com/819.html
I wish I'd made you angry earlier

Hoya

Members


Статус

2 сообщений

Где: Russia
Род занятий:
Возраст:

#7778   2017-05-17 13:04 GMT+3 часа(ов)      
Доброго времени суток! можно как то этот алгоритм реализовать на чистом Lisp'е?
> 1 <


Онлайн :

0 пользователь(ей), 27 гость(ей) :




Реклама на сайте: