Форум программистов, компьютерный форум, киберфорум
Lisp
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
1 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 10
1

Каким образом можно использовать функции высокого порядка

07.11.2013, 07:24. Показов 1408. Ответов 15
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Помогите пожалуйста ответить на вопрос.

Каким образом можно использовать функции высокого порядка (аргументами функций являются функции) при реализации ваших функций psh или rv?

Lisp
1
2
3
4
5
6
7
8
9
10
;функция поиска в ширину
(defun psh(nv nov y e)
   (cond ((null nov)nil)
     ((member y nov)t)
     (t(psh (append nv nov) (psmv nv nov e) y e))))
 
;функция перебора вершин
(defun rv(1v v e)
   (cond ((null v) t)   
     ((path 1v (first v) e)(rv 1v (rest v) e))(t nil)))
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.11.2013, 07:24
Ответы с готовыми решениями:

"Функции более высокого порядка. Функциональный аргумент, функциональное значение. Способы композиции функций" - композиции и функции высокого порядка
Идут 2 вопроса подряд: "Локальные определения (форма LET). Функции более высокого порядка....

Каким образом в Common Lisp можно возвращать более одного значения, не используя объекты-контейнеры?
Каким образом в Common Lisp можно возвращать более одного значения, не используя...

Функция высокого порядка
Доброго времени суток. Есть 2 лабы, требующие решения! Помогите, пожалуйста! 1....

Рекурсия высокого порядка
Необходимо сделать с помощью рекурсии высокого порядка реверс списка на всех уровнях. У меня...

15
Модератор
Эксперт функциональных языков программированияЭксперт Python
37301 / 20735 / 4272
Регистрация: 12.02.2012
Сообщений: 34,124
Записей в блоге: 14
07.11.2013, 16:22 2
Не "высокого", а высшего порядка. Как у тебя задаются графы?
0
1 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 10
07.11.2013, 16:31  [ТС] 3
Вот вся программка

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
;функция проверки существования пути
(defun path(x y e)
   (psh nil (list x) y e))  
 
;функция проверки принадлежности смежных вершин
(defun smv(x y nv nov)
   (cond ((not (member x nov))nil)  
     ((member y nov)nil)
     ((member y nv) nil)(t t)))
 
;функция поиска смежных вершин
(defun psmv(nv nov e)
   (cond ((null e)nil)
     ((smv(first(first e))(first(rest(first e)))nv nov)
        (cons (first(rest(first e)))(psmv nv nov (rest e))))
     ((smv(first(rest(first e)))(first(first e)) nv nov)
      (cons (first(first e)) (psmv nv nov (rest e))))
     (t(psmv nv nov (rest e)))))
 
;функция поиска в ширину
(defun psh(nv nov y e)
   (cond ((null nov)nil)
     ((member y nov)t)
     (t(psh (append nv nov) (psmv nv nov e) y e))))
 
;функция перебора вершин
(defun rv(1v v e)
   (cond ((null v) t)   
     ((path 1v (first v) e)(rv 1v (rest v) e))(t nil))) 
 
;функция определения связанности граф
(defun graf(v e)
   (rv (first v) (rest v) e))
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
37301 / 20735 / 4272
Регистрация: 12.02.2012
Сообщений: 34,124
Записей в блоге: 14
07.11.2013, 16:35 4
Цитата Сообщение от KEgor Посмотреть сообщение
Вот вся программка
- для тех, кто знает Лисп, возможно и так. А для тебя это не "программка", а Эверест. И ты не ответил на вопрос: как представляются графы в программе.
0
1 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 10
07.11.2013, 17:30  [ТС] 5
Для представления графа используются два списка: список верши и список ребер графа, а для определения связности графа используется поиск пути от одной вершины к другой.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
37301 / 20735 / 4272
Регистрация: 12.02.2012
Сообщений: 34,124
Записей в блоге: 14
07.11.2013, 17:37 6
Уже лучше. Посмотрю.
0
1 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 10
10.11.2013, 16:42  [ТС] 7
В программе были реализованы следующие функции:

path(x y e) - предикат проверки, существования пути из вершины X в вершину Y, где e – список ребер.

smv (x y nv nov) – функция проверки принадлежности смежных вершин, определяет, является ли вершина y смежной с одной из новых вершин, где x - первая вершина ребра, y - вторая вершина ребра, nv - список найденных вершин, nov - список новых вершин.

psmv (nv nov e) – функция поиска смежных вершин, осуществляет поиск смежных вершин с новыми вершинами и добавлением их в список, где nv - список найденных вершин, nov - список новых вершин, e - список ребер.

psh(nv nov y e) - функция поиска в ширину, осуществляет просмотр вершин по алгоритму поиск «в ширину», где nv - список найденных вершин, nov - список новых вершин, y - вершина поиска, e - список ребер.

rv(1v v e) - функция перебора вершин, осуществляет перебор вершин и поиск путей от первой вершины ко всем остальным, где 1v - первая вершина, v - список вершин, e - список ребер.

graf(v e) - функция определения связанности граф, где v - список вершин, e - список ребер.
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
37301 / 20735 / 4272
Регистрация: 12.02.2012
Сообщений: 34,124
Записей в блоге: 14
10.11.2013, 17:58 8
Если смогу - посмотрю сегодня позже. В крайнем случае - завтра.
0
1 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 10
12.11.2013, 04:54  [ТС] 9
Обещали посмотреть
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
37301 / 20735 / 4272
Регистрация: 12.02.2012
Сообщений: 34,124
Записей в блоге: 14
13.11.2013, 22:51 10
Смотрю. Как-то странно работают функции. Например, psh (поиск в ширину) не путь, как ожидалось, а T... Можешь показать, что должна делать программа?
0
1 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 10
13.11.2013, 23:37  [ТС] 11
Вот исходное задание:

Напишите программу на языке XLisp, определяющую, является ли данный неориентированный граф связным.
Указание: запрограммируйте предварительно предикат (path X Y), проверяющий, существует ли путь из вершины X в вершину Y.
0
1 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 10
14.11.2013, 00:00  [ТС] 12
Что делает программа находится во вложении.
Вложения
Тип файла: doc графы.doc (93.5 Кб, 4 просмотров)
0
1 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 10
23.11.2013, 06:36  [ТС] 13
Хотя-бы объясните пожалуйста, как это можно сделать.
0
1 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 10
27.11.2013, 17:12  [ТС] 14
Однако, не только для меня эта программка Эверест!
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
37301 / 20735 / 4272
Регистрация: 12.02.2012
Сообщений: 34,124
Записей в блоге: 14
27.11.2013, 19:09 15
Воложение в формате "doc" невразумительно. В чужом коде копаться не хочется... Но задача, является ли граф связным, решается многими способами. Например, таким:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
;; найти первую вершину, связанную с v и непосещенную
 
(defun search (v graph chk)  ;; v - текущая вершина; graph - граф; chk - список уже посещенных вершин
  (dolist (i graph nil)
    (when (and (eq v (car i)) (not (member (cadr i) chk))) (return (cadr i)))
    (when (and (eq v (cadr i)) (not (member (car i) chk))) (return (car i)))))
 
;; обход в глубину (с первой вершины)
;; функция возвращает список посещенных вершин
 
(defun dfs (graph &optional (chk '(1)) (stack '(1)))
  (let ((w (if (null stack) nil (search (car stack) graph chk))))
       (cond ((and (null w) (null stack)) chk)
             ((null w) (dfs graph chk (cdr stack)))
             (t (dfs graph (cons w chk) (cons w stack))))))
 
;; проверка связности
 
(defun is-connected (graph)
  (let ((vlist (setof (apply 'append graph))))  ;; список вершин без повторений
     (= (length vlist) (length (dfs graph)))))   ;; сравнение длины списка посещенных вершин и исходного
                                                            ;; списка вершин. Если длины совпадают - граф связный.
 
;; а теперь проверка:
 
(is-connected '((1 2) (1 3) (2 4) (3 4) (4 5) (4 6) (4 7) (5 6) (6 7) (7 8) (7 9) (8 10) (8 11) (9 10) (9 11)))
 
==> T ;; это связный граф
 
;; выбрасываем 4-ю вершину и граф становится несвязным:
 
(is-connected '((1 2) (1 3) (5 6) (6 7) (7 8) (7 9) (8 10) (8 11) (9 10) (9 11)))
 
==> NIL
Так что Эверестом все это является для тебя... И будет, пока Лисп не выучишь.
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
37301 / 20735 / 4272
Регистрация: 12.02.2012
Сообщений: 34,124
Записей в блоге: 14
02.12.2013, 13:55 16
Кстати, в функции is-connected используется apply - функция высшего порядка.
0
02.12.2013, 13:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.12.2013, 13:55
Помогаю со студенческими работами здесь

Функция высокого порядка. Помогите
Помогите пожалуйста написать программу на Лиспе. Задание: Определять максимальный элемент среди...

Можно ли использовать DAO вместо Ado и если Можно то каким образом?
Люди!!!Можно ли использовать DAO вместо Ado и если Можно то каким образом!Спасибо

Каким образом можно использовать файл *.h в проекте на C#
Всем добрый. Каким образом можно использовать файл *.h в проекте на C#?

Каким образом можно использовать регулярное выражение regex из .NET под С++
Работаю в VS Express 2012. Насколько понимаю, эта библиотека должна подключаться и к проекту на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru