Получить размер самого длинного подсписка из списка в схеме - PullRequest
Новая
       6

Получить размер самого длинного подсписка из списка в схеме

0 голосов
/ 29 сентября 2011

Я хотел бы получить размер самого длинного подсписка из списка.

например

(getlongest ((a) b (d e m n) (a d (c g g c yu l d) a)))

возвращает 9, поскольку (c g g c y u m l d) имеет размер 9.

Я написал эту функцию 

(define getlongest
  (lambda (ls)
    (cond 
     ((null? ls)0)
     (else
      (cond
        ((atom? (car ls))
       (+ 1 (getlongest (cdr ls))))
         (else
          (max (getlongest(car ls)) (getlongest(cdr ls)))))))))

Однако, если я напишу

(getlongest ((a) (a (d d d e) m)))

я получаю 5. Кто-нибудь может мне помочь исправить это?

Спасибо

1 Ответ

1 голос
/ 29 сентября 2011

Таким образом, проблема с вашим кодом состоит в том, что вы подсчитываете 1 длину для части списка, которую вы уже просчитали, даже если вы продолжите, чтобы найти, что подсписок этого списка на самом деле самый длинный. Например, ваш код возвращает 5 и для этого случая: (getlongest '(a (b (c (d (e)))))).

Ваш подход трудно исправить. Я думаю, вам нужно будет передать больше данных, когда вы вернетесь; если каждый вызов getlongest знает текущую длину, то вы сможете получить правильный максимум.

Если это не домашнее задание, вот как я инстинктивно написал бы ту же функцию (не настолько эффективную, насколько это возможно, но просто:) 

(define (get-longest x)
  (cond ((null? x) 0)
        ((atom? x) 1)
        ; else take either the length of this list, or of the longest sub-list
        (else (apply max (length x) (map get-longest x)))))
...