В задаче нужно использовать рекурсию. Вообще не понимаю эту тему :(

@Ginraf · Регистрация: 16.10.2015

На форуме уже есть эта задача, а решения стоящего нет

Связать базу данных (потомок, родители) с глобальной переменной FAMILY:

Lisp

(setf family ’((colin nil nil) (deirdre nil nil) (arthur nil nil) (kate nil nil) (franknil 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)))

Определить функцию GENERATION-GAP, которая возвращает количество поколений между предком и потомком в генеалогическом дереве. Например,

Lisp

> (GENERATION-GAP ‘SUZANNE ‘COLIN)
1
> (GENERATION-GAP ‘FRADERICK ‘COLIN)
3
> (GENERATION-GAP ‘FRADERICK ‘LINDA)
NIL

@nullxdth · 22.10.2015, 18:23

Отформатируйте код. Так невозможно читать.

@Ginraf · 23.10.2015, 14:05 **[ТС]**

nullxdth,

Lisp

(setf family ’((colin nil nil)
 (deirdre nil nil)
 (arthur nil nil) 
(kate nil nil) 
(franknil 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)))

@helter · 23.10.2015, 14:34

Ginraf, напишите сначала функции
father person family => person or nil
mother person family => person or nil
Функции обозначены жирным, потом указаны аргументы и значения.

Потом пишите вашу функцию
generation-gap ancestor descendant => integer or nil
Она очень простая. Рекурсивная идея: если вы знаете промежуток n между А и Б, то промежуток между А и детьми Б равен n + 1.

Если ancestor и descendant — одно лицо, возвращаем 0. В противном случае рассматриваем родителей descendant. Если они оба не указаны (nil), придётся вернуть nil. Иначе вычисляем наименьший generation-gap от ancestor до имеющихся родителей, и если он не будет nil, прибавляем к нему 1.

Вперёд!

@Ginraf · 23.10.2015, 15:53 **[ТС]**

helter,
С первым примером работает, а со вторым - нет.

Lisp

(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 father (name)
  (second (assoc name family)))
 
(defun mother (name)
  (third (assoc name family)))
 
(defun parents (name)
  (remove-if #'null (rest (assoc name family))))
;   (remove-if #'null (list (father name) (mother name))))
 
(defun children (name)
  (and name
       (mapcar
         #'first
         (remove-if-not
           #'(lambda (row) (member name (rest row)))
           family))))
 
(defun siblings (name)
  (remove name (union (children (father name))
                      (children (mother name)))))
 
(defun mapunion (func x)
  (reduce #'union (mapcar func x)))
 
(defun grandparents (name)
  (mapunion #'parents (parents name)))
 
(defun cousins (name)
  (mapunion #'children (mapunion #'siblings (parents name))))
 
(defun descended-from (succ pred)
  (let ((both-parents (parents succ))
        (dad (father succ))
        (mom (mother succ)))
    (cond ((null succ) nil)
          ((member pred both-parents) t)
          (t (or (descended-from dad pred)
                 (descended-from mom pred))))))
 
(defun ancestors (name)
;  (declare (notinline ancestors))
  (let ((both-parents (parents name))
        (dad (father name))
        (mom (mother name)))
    (cond ((null name) nil)
          (t (union both-parents (union (ancestors dad)
                                        (ancestors mom)))))))
 
(defun generation-gap (person ancestor)
  (let* ((both-parents (parents person))
         (dad (father person))
         (mom (mother person))
         (person-ancestors (ancestors person))
         (dad-ancestors (ancestors dad))
         (mom-ancestors (ancestors mom)))
    (cond ((null person) nil)
          ((not (member ancestor person-ancestors)) nil)
          ((member ancestor both-parents) 1)
          ((and (member ancestor dad-ancestors)
                (member ancestor mom-ancestors))
           (min (+ 1 (generation-gap dad ancestor))
                (+ 1 (generation-gap mom ancestor))))
          ((member ancestor dad-ancestors)
           (+ 1 (generation-gap dad ancestor)))
          (t (+ 1 (generation-gap mom ancestor))))))
 
(let ((parta1 '(father 'suzanne))
      (parta2 '(mother 'suzanne))
      (parta3 '(parents 'suzanne))
      (parta4 '(parents 'frederick))
      (parta5 '(children 'arthur))
      (partb1 '(siblings 'bruce))
      (partb2 '(siblings 'zelda))
      (partc1 '(mapunion #'rest '((1 a b c)(2 e c j)(3 f a b c d))))
      (partd1 '(grandparents 'suzanne))
      (partd2 '(grandparents 'frederick))
      (partd3 '(grandparents 'yvette))
      (parte1 '(cousins 'julie))
      (partf1 '(descended-from 'tamara 'arthur))
      (partf2 '(descended-from 'tamara 'linda))
      (partg1 '(ancestors 'marie))
      (parth1 '(generation-gap 'suzanne 'colin))
      (parth2 '(generation-gap 'frederick 'colin))
      (parth3 '(generation-gap 'frederick 'linda))
      (parti1 '(descended-from 'robert 'deirdre))
      (parti2 '(ancestors 'yvette))
      (parti3 '(generation-gap 'olivia 'frank))
      (parti4 '(cousins 'peter))
      (parti5 '(grandparents 'olivia)))
  (format t "~s = ~s~%" parta1 (eval parta1))
  (format t "~s = ~s~%" parta2 (eval parta2))
  (format t "~s = ~s~%" parta3 (eval parta3))
  (format t "~s = ~s~%" parta4 (eval parta4))
  (format t "~s = ~s~%" parta5 (eval parta5))
  (format t "~s = ~s~%" partb1 (eval partb1))
  (format t "~s = ~s~%" partb2 (eval partb2))
  (format t "~s = ~s~%" partc1 (eval partc1))
  (format t "~s = ~s~%" partd1 (eval partd1))
  (format t "~s = ~s~%" partd2 (eval partd2))
  (format t "~s = ~s~%" partd3 (eval partd3))
  (format t "~s = ~s~%" parte1 (eval parte1))
  (format t "~s = ~s~%" partf1 (eval partf1))
  (format t "~s = ~s~%" partf2 (eval partf2))
  (format t "~s = ~s~%" partg1 (eval partg1))
  (format t "~s = ~s~%" parth1 (eval parth1))
  (format t "~s = ~s~%" parth2 (eval parth2))
  (format t "~s = ~s~%" parth3 (eval parth3))
  (format t "~s = ~s~%" parti1 (eval parti1))
  (format t "~s = ~s~%" parti2 (eval parti2))
  (format t "~s = ~s~%" parti3 (eval parti3))
  (format t "~s = ~s~%" parti4 (eval parti4))
  (format t "~s = ~s~%" parti5 (eval parti5)))

@helter · 23.10.2015, 20:26

Алгоритм потому что кривой. Я вам даю ценные указания, а вы вываливаете кучу кода, написанного в разное время всеми вашими друзьями и знакомыми. Зачем вы вычисляете предков и предков родителей? Я говорил вам вычислять всех предков? Если вы интуитивно не понимаете, как вычислять разницу поколений (хотя мне неясно, как это можно не понимать), перечитайте ещё и ещё раз то, что я вам написал. Потом сделайте так же на лиспе. Уточнение: действительно, удобно возвращать nil, если один из аргументов есть nil. И вам не нужны все эти тонны кода, кроме функций father и mother, которые к тому же написаны плохо.

Я не буду вникать в вашу функцию и почему она не работает, потому что алгоритм, как было сказано, кривой. Но проверьте на опечатки ещё разок, у вас их много. К тому же сначала у вас была одна семья, потом — другая; может, в программе они путаются.

Но я дам вам ценные советы по вашему коду.

Во-первых: переменные объявляются. Повторите несколько раз: переменные — объявляются. Если вам нужна глобальная величина, которая не обязательно будет меняться, объявите её с помощью defparameter.

Далее, глобальной переменной сделайте *ушки*. Все так делают. Если вы фанат Дага Хойта, не делайте. Если нет — сделайте.

Далее, зачем хардкодить внешнюю глобальную переменную внутрь функций. Если ваша программа преимущественно работает с одной семьёй, и вам лень её каждый раз передавать аргументом, заведите-таки глобальную *family* и делайте опциональный аргумент. Например:

Lisp

1 2	(defun father (person &optional (family family)) (second (assoc person family)))

И да, у меня всё работает.

Добавлено через 3 минуты
Хотя почему я решил, что разные семьи, одна вроде. Но всё равно проверьте на опечатки. fraderick, например, это что?

@nullxdth 2303 / 1061 / 77 Регистрация: 12.03.2013 Сообщений: 4,978
	22.10.2015, 18:23	2
	Отформатируйте код. Так невозможно читать. 1

@helter 4320 / 3329 / 339 Регистрация: 12.03.2013 Сообщений: 5,828
	23.10.2015, 14:34	4
	Ginraf, напишите сначала функции father person family => person or nil mother person family => person or nil Функции обозначены жирным, потом указаны аргументы и значения. Потом пишите вашу функцию generation-gap ancestor descendant => integer or nil Она очень простая. Рекурсивная идея: если вы знаете промежуток n между А и Б, то промежуток между А и детьми Б равен n + 1. Если ancestor и descendant — одно лицо, возвращаем 0. В противном случае рассматриваем родителей descendant. Если они оба не указаны (nil), придётся вернуть nil. Иначе вычисляем наименьший generation-gap от ancestor до имеющихся родителей, и если он не будет nil, прибавляем к нему 1. Вперёд! 1

Опции темы