> 1 <

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

Day_moon

Members


Статус

3 сообщений

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

#1968   2010-05-06 16:29 GMT+3 часа(ов)      
Взял готовую программу, но видимо не я один такой "умный" и пришла рецензия:

Реценция
...обозначение ребра как список из двух вершин является неудовлетворительным, поскольку параллельные ребра не различаются и есть сомнения в ответе. Может программа проходит по какому-нибудь из параллельных ребер дважды.
Используйте обозначение ребра как список из трех сущностей: две вершины и метка ребра. Переделайте программу.


Попытался переделать, но застрял... Вот что у меня получилось:

(defun F (Graph &optional (Temp (cons (caar Graph) nil)) (Way nil))
(if Temp ; если список не пуст делать
((lambda (Current_Top) ;текущая вершина - первый элемент списка Temp
(if(Find Current_Top Graph)
((lambda (Current_Top_List) ;список связей текущей вершины
((lambda (Next_Top) ;берем первое ребро графа (следующая вершина - второй элемент списка)
(F ; рекурсивно запускаем F , удалив используемое ребро из ребер графа и добавляем вторую вершину этого ребра в список Temp
(remove Current_Top_List Graph)
(cons (car Next_Top) Temp) ;добавляем вершину в список Temp
Way))
(cdr Current_Top_List)));Next_Top следующая вершина списка
(Find Current_Top Graph)) ;ищем список в списке списков, начинающийся текущей вершиной
(F Graph (cdr Temp) (cons Current_Top Way))))
(car Temp))
Way)) ;когда список Temp становится пустым выводим список Way, это и есть эйлеров путь
 
(defun Find(ver graph)
((lambda (gran)
(if (= (car gran) ver)
gran
(if (= (cdr gran) ver)
((subst (car gran)(cdr gran) gran)
(subst ver (car gran) gran)
gran)
(Find(ver (cdr graph))))))
(car graph)))
 
(defun Z()
(F '((1 2)(1 3)(2 3)(2 4)(2 5)(3 4)(3 5)(4 5)) '(4))
)


Подскажите в чем ошибка в Find, или еще где... Осталось еще метку ребра добавить...

отредактировал(а) Day_moon: 2010-05-06 17:45 GMT+3 часа(ов)

Михаил

Members


Статус

120 сообщений

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

#1969   2010-05-06 16:43 GMT+3 часа(ов)      

Day_moon

Members


Статус

3 сообщений

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

#1970   2010-05-06 16:49 GMT+3 часа(ов)      
Я уже отправлял этот код... Мне теперь нужно что бы ребра задавались так: ((1 2)(1 3)(2 3)(2 4)(2 5)(3 4)(3 5)(4 5))
Скажите хотя бы как правильно передать в Find вершину и список ребер.

VH

Members


Статус

289 сообщений

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

#1972   2010-05-06 17:19 GMT+3 часа(ов)      
Это из препода цитата «...Может (выделено мной - VH.) программа проходит по какому-нибудь из параллельных ребер дважды...»?

Day_moon

Members


Статус

3 сообщений

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

#1974   2010-05-06 17:45 GMT+3 часа(ов)      
Да это цитата

VH

Members


Статус

289 сообщений

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

#1975   2010-05-06 18:05 GMT+3 часа(ов)      
Фраза сия обнаруживает туповатость <данного> препода во всей ея красе.
Анализировать представленную функцию на предмет того, каким же образом она все-таки генерирует Эйлеров путь, препод <видимо> не способен. Можно ли чем иным объяснить <чисто научные> словечки "сомнения" и "может"? Особенно впечатляет выражение «...программа проходит...».
Функция (F) никуда не «проходит», а выполняет <рекурсивно> преобразование данных <в виде списков> (являющихся ее аргументами) и возвращает результат этих преобразований.
В процессе обработки данных <в том числе> функция (F) посредством вызова функции (REMOVE_FIRST) последовательно исключает из элементов представляющего граф списка пару вершин, ребро между которыми «рассмотрено» и включено в Эйлеров путь, в чем легко можно удостовериться, применив трассировку вызовов функции (F) с помощью функции (trace).
Предоставлю <для убедительности> часть протокола трассировки (полужирным шрифтом выделяются исключаемые к следующему уровню рекурсии пары вершин):
(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)))
Entering: F, Argument list: (((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)))
 Entering: F, Argument list: (((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)) (2 1) NIL)
  Entering: F, Argument list: (((1 6) (2 3 5 6) (3 2 4 5 6) (4 3 5) (5 2 3 4 6) (6 1 2 3 5)) (1 2 1) NIL)
   Entering: F, Argument list: (((1) (2 3 5 6) (3 2 4 5 6) (4 3 5) (5 2 3 4 6) (6 2 3 5)) (6 1 2 1) NIL)
    и так далее...
К слову, описание графа вовсе не представляет собой совокупность «обозначение ребра как список из двух вершин».

отредактировал(а) VH: 2010-05-06 18:10 GMT+3 часа(ов)

Hoya

Members


Статус

2 сообщений

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

#7777   2017-05-17 13:03 GMT+3 часа(ов)      
Доброго времени суток! можно как то код этот под чистый лисп переписать?
> 1 <


Онлайн :

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




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