Рекурсивная функция ANCESTORS

@NadezdaFox · Регистрация: 18.03.2014

Студворк — интернет-сервис помощи студентам

2.Определить рекурсивную функцию ANCESTORS, которая возвращает список предков для любого представителя генеалогического дерева. Например,

Lisp
1
2
> (ANCESTORS ‘MARIE)
(ELLEN ARTHUR KATE GEORGE FRANK LINDA)

Для дерева вида:

Lisp
1
2
3
4
5
6
7
8
9
FAMILY:
(setf family ’((colin nil nil) (deirdre nil nil) (arthur nil nil) (kate nil nil) (frank
nil nil) (linda nil nil) (suzanne colin deirdre) (bruce arthur kate) (charles
arthur kate) (david arthur kate) (ellen arthur kate) (george frank linda) (hillary
frank linda) (andre nil nil) (tamara bruce suzanne) (vincent bruce suzanne)
(wanda nil nil) (ivan george ellen) (julie george ellen) (marie george ellen)
(nigel andre hillary) (frederick nil tamara) (zelda vincent wanda) (joshua ivan
wanda) (quentin nil nil) (robert quentin julie) (olivia nigel marie) (peter nigel
marie) (erica nil nil) (yvette robert zelda) (diane peter erica)))

Я написала простым перечислением предков, но так не принимают, а как рекурсивно сделать вычисление родителей у родителей в несколько поколений я не понимаю( . Помогите пожалуйста))

Lisp
1
2
3
(defun dbsearch (name db)
(cond ((null db) nil) ((equal name (car (car db))) (car db))
(t (dbsearch name (cdr db)))))

Папа:

Lisp
1
 (defun father (name f) (cadr (dbsearch name f)))

Мама:

Lisp
1
(defun mother (name f) (caddr (dbsearch name f)))

@Catstail · 29.09.2015, 17:40

Вопрос: каждый элемент списка имеет вид (персона отец мать). Так?

Добавлено через 36 минут
HomeLisp:

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
35
36
37
38
39
40
41
(setf family '((colin nil nil)
  (deirdre nil nil) 
  (arthur nil nil) 
  (kate nil nil) 
  (frank nil nil) 
  (linda nil nil) 
  (suzanne colin deirdre) 
  (bruce arthur kate) 
  (charles arthur kate)
  (david arthur kate) 
  (ellen arthur kate) 
  (george frank linda) 
  (hillary frank linda) 
  (andre nil nil) 
  (tamara bruce suzanne) 
  (vincent bruce suzanne)
  (wanda nil nil) 
  (ivan george ellen) 
  (julie george ellen) 
  (marie george ellen)
  (nigel andre hillary) 
  (frederick nil tamara) 
  (zelda vincent wanda) 
  (joshua ivan wanda) 
  (quentin nil nil) 
  (robert quentin julie) 
  (olivia nigel marie) 
  (peter nigel marie) 
  (erica nil nil) 
  (yvette robert zelda) 
  (diane peter erica)))
 
(defun all-anc (family person)
  (let ((cell (car (remove-if #'(lambda (x) (not (eq (car x) person))) family))))
    (setof (append 
      (when (cadr cell) (cons (cadr cell) (all-anc family (cadr cell))))
      (when (caddr cell)(cons (caddr cell) (all-anc family (caddr cell))))))))
 
(all-anc family 'peter)
 
==> (nigel andre hillary marie george frank linda ellen arthur kate)

@helter · 29.09.2015, 19:55

Сообщение от NadezdaFox

Я написала простым перечислением предков, но так не принимают, а как рекурсивно сделать вычисление родителей у родителей в несколько поколений я не понимаю( . Помогите пожалуйста))

Я не люблю писать решений, но что тут писать-то? Предки - это папа и мама и предки папы и мамы. Если папа и мама не указаны, значит, родителей игнорируем. Перепишите то же самое скобочками:

Lisp
1
2
3
4
5
6
7
8
9
10
(defun ancestors (person)
  (let ((father (father person))
        (mother (mother person)))
    (let ((father-and-his-ancestors (if (null father)
                                        nil
                                        (cons father (ancestors father))))
          (mother-and-her-ancestors (if (null mother)
                                        nil
                                        (cons mother (ancestors mother)))))
      (append father-and-his-ancestors mother-and-her-ancestors))))

Можно, наверно, написать короче, и тут if-ы по сути дублируются, что тоже можно убрать, но код, в принципе, читаемый. Наверно, он работает, потестьте.

Не надо злоупотреблять cadadr-ами а-ля Catstail. Помните об инкапсуляции. Функциям высокого уровня абстракции не следует лезть в детали реализации низкого уровня. По крайней мере, инкапсуляция делает код более читаемым. Например, для меня приведённый код Catstail-а нечитаемый.

Добавлено через 1 минуту

Сообщение от helter

Наверно, он работает, потестьте.

Вижу, что не работает: нужно по крайней мере добавить аргумент family и засунуть его в father и mother.

@NadezdaFox · 29.09.2015, 20:51 **[ТС]**

Сообщение от Catstail

(setof (append

Вы не подскажите почему ругается Common LISP на функцию setof ?)

@Catstail · 29.09.2015, 21:01

NadezdaFox, просто добавь эту функцию:

Lisp
1
2
3
4
(defun setof (x)
    (COND ((NULL x) NIL) 
              ((member (CAR x) (CDR x)) (setof (CDR x))) 
              (T (CONS (CAR x) (setof (CDR x))))))

Добавлено через 4 минуты

Сообщение от helter

Вижу, что не работает: нужно по крайней мере добавить аргумент family и засунуть его в father и mother.

- точнее, достать из famyly очередных father и mother. И как при этом обойтись без car/cdr?

@NadezdaFox · 29.09.2015, 21:01 **[ТС]**

Огромное спасибо))))

@helter · 29.09.2015, 21:12

Сообщение от Catstail

точнее, достать из famyly очередных father и mother. И как при этом обойтись без car/cdr?

Элементарно, Ватсон:

Lisp
1
(let ((father (father person family))) ...)

@Catstail · 29.09.2015, 21:17

helter, так Вы же вызываете функцию, в которой все эти car/cdr... А, понял, что Вы имели в виду. Да, Вы, конечно, правы!

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

Рекурсивная функция ANCESTORS

Решение

Решение

Решение

@NadezdaFox 2 / 2 / 0 Регистрация: 18.03.2014 Сообщений: 32
	29.09.2015, 21:01 [ТС]
	Огромное спасибо)))) 0

@Catstail Супер-модератор 38180 / 21115 / 4307 Регистрация: 12.02.2012 Сообщений: 34,724 Записей в блоге: 14
	29.09.2015, 21:17
	helter, так Вы же вызываете функцию, в которой все эти car/cdr... А, понял, что Вы имели в виду. Да, Вы, конечно, правы! 0