рэкет: подсчет количества братьев и сестер

Имея вложенные списки в качестве входных данных, я пытаюсь найти, как вывести количество «братьев и сестер» элемента. С точки зрения деревьев, сколько других листовых узлов принадлежат одному и тому же родительскому/корневому узлу.

Мой код дает неправильные результаты (это действительно плохой код), и я не уверен, как полностью подойти к вопросу

(define (siblings lst n)
 (cond
     [(empty? lst) false]
     [(member? n lst) (sub1 (length lst))]
     [else (siblings (rest lst) n)]))

выборочные результаты: если дано (список (список 2 1) 3 (список 4)) и 3, выведите 0

(список (список 1 2 3) (список (список 4 5 6 ))) и 5 ​​-> 2


list nested tree siblings racket
person Fate Kyougo    schedule 10.03.2015    source источник
comment
Опубликуйте несколько примеров с их ожидаемым результатом.   -  person soegaard    schedule 11.03.2015
comment
member? не существует в языке #!racket. Есть member, memv и memq.   -  person Sylwester    schedule 11.03.2015

Ответы (1)


arrow_upward
0
arrow_downward

Ваш код должен делать две отдельные вещи:

  1. Найдите ветку, содержащую n
  2. Подсчитайте количество братьев и сестер в этой ветви с учетом возможности начала других ветвей.

Поиск ветки, содержащей n, при условии, что n может появиться только один раз:

(define (find-branch root n)
  (cond ((empty? root) empty)
        ((memq n root)
          root)
        ((list? (first root))
         (let ((subresult (find-branch (first root) n)))
           (if (not (empty? subresult))
               subresult
               (find-branch (rest root) n))))
        (else (find-branch (rest root) n))))

Поскольку вы используете «Начинающий студент», это лишает вас всех инструментов. К счастью, у него все еще есть number?, поэтому, если можно с уверенностью предположить, что все, что не является числом в этом присвоении, является списком, вы можете определить list? следующим образом:

(define (list? n) (not (number? n)))

Учитывая ваше дерево примеров в качестве входных данных, оно вернет:

(4 5 6)

В приведенном выше примере многократно используется memq для rest входного списка в результате использования рекурсии для итерации по одному и тому же списку.

Вот более эффективная версия вышеизложенного, но вы не можете реализовать ее в Beginning Student:

(define (find-branch root n)
  (cond ((empty? root) false)
        ((memq n root) root)
        (else (foldl (λ (a b)
                        (if (empty? a) b a))
                     empty
                     (map (λ (sublist)
                             (find-branch sublist n))
                       (filter list? root))))))

Вы передаете результат этой функции для подсчета братьев и сестер. Ранее я предоставил версию, которая будет работать в настоящей Racket, но не в версии для начинающих, используемой учителями:

(define (count-siblings root mem)
  (count (λ (sib)
            (and (not (eq? sib mem))
                 (not (list? sib)))) root))

Вот версия, совместимая с Beginning Student:

(define (count-siblings lst n counter)
  (cond
     [(empty? lst) counter]
     [(and (not (list? (first lst)))
           (not (eq? n (first lst)))) 
      (count-siblings (rest lst) n (add1 counter))]
     [else (count-siblings (rest lst) n counter)]))

Наконец, соедините их вместе:

(define (find/count-siblings root n)
   (count-siblings (find-branch root n) n 0))
person Throw Away Account    schedule 10.03.2015
comment
В настоящее время я использую язык для начинающих, есть ли способ написать это без локального определения или списка? - person Fate Kyougo; 11.03.2015
comment
(define (list? n) (not (number? n))), который дает вам версию list?, которая должна быть достаточно хорошей для этого задания (но она даст неправильные результаты, если вы используете ее в задании, которое включает строки, символы или что-либо еще, разрешенное в Beginning Student). Я переписал count-siblings и find/count-siblings, чтобы учесть отсутствие локальных определений. - person Throw Away Account; 11.03.2015