Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Lisp
Перезагрузить страницу Написать функцию, которая возвращает количество вершин
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Adebayor Adebayor вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию Написать функцию, которая возвращает количество вершин - 16.12.2007, 16:52

Уже несколько дней мучаюсь - нерешить

Задача такая

Написать функцию, которая по заданному числовому неориентированному связному графу возвращает количество вершин у которых смежными являются вершины только с четными числами.
Ответить с цитированием
  (#2 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 16.12.2007, 18:32

Код:
(defun count-vertices-with-even-neighbours (graph)
  (loop for v in (graph-vertices graph)
        count (every (lambda (n) (evenp (graph-vertex-value graph n)))
                     (graph-neighbours-of graph v))))
Если представлить граф так: список записей (имя-вершины величина . список-имён-соседей), то функции доступа можно определить так:
Код:
(defun graph-vertices (graph)
  (mapcar #'first graph))
(defun graph-vertex (graph vertex-name)
  (assoc vertex-name graph))
(defun graph-neighbours-of (graph vertex-name)
  (cddr (graph-vertex graph vertex-name)))
(defun graph-vertex-value (graph vertex-name)
  (second (graph-vertex graph vertex-name)))
Проверка:
Код:
CL-USER> (count-vertices-with-even-neighbours
 '((a 1   b c)
   (b 2   d a c)
   (c 4   b a)
   (d 6   b)))
2
Ответить с цитированием
  (#3 (permalink)) Старый
Adebayor Adebayor вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию 16.12.2007, 19:33

проблема в том что используется мулисп85
Alexey Dejneka, можешь взглянешь? Вот полное задание.
С меня 200 р на webmoney =)

http://www.free-lance.ru/users/Bisher/uplo...640469456ae.rar
Ответить с цитированием
  (#4 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 16.12.2007, 20:15

mulisp85 у меня нет, теоретически должен работать такой код:
Код:
(defun count-vertices-with-even-neighbours (graph)
  (cond ((null graph)
         0)
        (t ((lambda (rest-count)
              (cond ((every 'evenp (cdar graph))
                     (+ 1 rest-count))
                    (t
                     rest-count)))
            (count-vertices-with-even-neighbours (cdr graph))))))
Предположения:
1. Граф задан так: ((вершина1 сосед11 сосед12 ...)(вершина2 сосед21 сосед22 ...) ...), вершинаi и соседij - целые числа.
2. Если i имеет соседа j, то j также имеет соседа i.
3. В mulisp85 есть функция проверки на чётность EVENP.
4. В mulisp85 есть функция EVERY. Если нет, её можно определить примерно так:
Код:
(defun every (pred list)
  (cond ((null list)
         t)
        ((funcall pred (car list))
         (every pred (cdr list)))
        (t
         nil)))
Проверка:
Код:
MY> (count-vertices-with-even-neighbours
 '((1   2 4)
   (2   6 1 4)
   (4   1 2)
   (6   2)))
2
Ответить с цитированием
  (#5 (permalink)) Старый
Adebayor Adebayor вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию 16.12.2007, 20:43

там в мулиспе 85 функции вообще немного по другому описываются
я в архиве выложил
http://www.free-lance.ru/users/Bishe...40469456ae.rar
а задается граф примерно так
((1 . (2 3 4)) (2 . (3)) (3 . (4)))
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 16.12.2007, 21:03

Цитата:
там в мулиспе 85 функции вообще немного по другому описываются
Свой код я могу проверить. Посылать непроверенный код я не хочу. В mulisp87 6.10b код работает.
Цитата:
задается граф примерно так
((1 . (2 3 4)) (2 . (3)) (3 . (4)))
А как точно звучит правило?
Ответить с цитированием
  (#7 (permalink)) Старый
Adebayor Adebayor вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию 16.12.2007, 21:16

Цитата:
А как точно звучит правило?
Вообщем-то все также, только в скобках.

((вершина . (вершины относящиеся к ней)) (вершина . (вершины относящиеся к ней)) (вершина . (вершины относящиеся к ней)))
Ответить с цитированием
  (#8 (permalink)) Старый
Adebayor Adebayor вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию 16.12.2007, 21:40

Вот примерно как я написал

Код:
(defun count-vertices-with-even-neighbours (lambda  (graph)
  (cond 

     (  (null graph)  0)
     

      (t (schet graph 0))
     )
))





(defun schet (lambda (graph rest-count)
     

 (cond 

((every evenp (cdar graph)) (+ 1 rest-count))
(t rest-count)
)
))



  
 
  (EQUAL (count-vertices-with-even-neighbours '((1 . (6)) (2 . (4)) (3 . (4) )))
          1)

(EQUAL (count-vertices-with-even-neighbours '((1 . (2 4 4)) (2 . (7)) (3 . (4) )))
          2)
 
   
   (RDS)
Но он считает только первую вершину и ее вершины.
А вот как сделать рекурсию чтобы он проходил по всем?
Ответить с цитированием
  (#9 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 16.12.2007, 22:22

Код:
(defun schet
    (lambda (graph before-count)
      (cond ((null graph) before-count)
            (t (schet (cdr graph)
                      (cond
                        ((every 'evenp (cdar graph))
                         (+ 1 before-count))
                        (t
                         before-count)))))))
НО! Я не понимаю этот пример:
Код:
(EQUAL (count-vertices-with-even-neighbours '((1 . (2 4 4)) (2 . (7)) (3 . (4) )))
          2)
Почему у 1 вершина 4 встречается 2 раза? Почему, хотя есть ребро от 1 к 2, нет ребра от 2 к 1? Почему есть ребро 2->7, но нет самой вершины 7? Какое точно правило представления неоринтированного графа Вы используете?
Ответить с цитированием
  (#10 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 16.12.2007, 22:25

Цитата:
Вообщем-то все также, только в скобках.

((вершина . (вершины относящиеся к ней)) (вершина . (вершины относящиеся к ней)) (вершина . (вершины относящиеся к ней)))
А Вы знаете, что записи (1 . (2 3)) и (1 2 3) обозначают в точности один и тот же список?
Ответить с цитированием
  (#11 (permalink)) Старый
Adebayor Adebayor вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 16.12.2007
По умолчанию 16.12.2007, 22:36

А можно узнать что конкретно делает функция every ?

Код:
(defun every (pred list)
  (cond ((null list)
         t)
        ((funcall pred (car list))
         (every pred (cdr list)))
        (t
         nil)))
и что в ней значит funcall ?
Ответить с цитированием
  (#12 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 16.12.2007, 22:58

Функция EVERY возвращает "истину", если все элементы списка удовлетворяют предикату PRED, и NIL в противном случае. Например:
Код:
CL-USER> (every 'evenp '(2 8 6 4))
T
CL-USER> (every 'evenp '(2 8 7 4))
NIL
Функция FUNCALL применяет функцию, заданную первым аргументом, к остальным. Например, (FUNCALL '+ 3 4) => 7. Смысл в том, что ее аргумент может быть выражением, например, (FUNCALL (CAR '(+ -)) 3 4) => 7, в частности, переменной.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Написать фунуцию которая по заданному натуральному числу определяет количество цифр kokos Вопросы начинающих программистов 4 19.01.2011 03:14
Написать функцию, которая по списку lst и атому obj возвращает множество klava Lisp 1 22.12.2009 14:05
Реализовать функцию, которая возвращает первый элемент ne_ponimaju_lisp Lisp 2 17.12.2009 15:27
Нужно написать рекурсивную функцию, которая возвращает t Bender266 Lisp 6 06.05.2009 14:40
Написать функцию, которая возвращает истину Bender266 Lisp 0 06.05.2009 13:47
Написать функцию LAST1, которая возвращает предпоследний элемент списка Sw1ft Lisp 9 17.05.2007 20:25
Как создать функцию, которая возвращает массив imported_nemesis С/С++ 5 13.03.2006 13:56
Как сделать функцию, которая создает окно и возвращает значение je0n WinAPI 1 03.02.2006 12:30
Написать процедуру которая подсчитывает количество узлов FLoYD777 Pascal 23 23.12.2005 17:44
Как написать функцию, которая бы читала из .txt информацию Лира Вопросы начинающих программистов 6 13.11.2005 07:02
Как написать функцию находящую минимальное количество символов Bag Java 2 03.07.2005 01:30
Написать функцию, которая бы выдавала Т Sever Lisp 0 23.04.2005 21:08



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов