Правильно подсчитать количество пар в нерегулярной структуры список


Из SICP:

На фоне, вот это упражнение 3.16:

Упражнение 3.16

Бен Bitdiddle решает написать процедуру для подсчета количество пар в любой структуре списка. Это легко," он рассуждает.В количество пар в любой структуре количество в машине количество в цхд плюс еще один подсчет текущая пара". Так что Бен пишет следующей процедурой:

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))

Показывают, что эта процедура не правильно. В частности, рисовать поле и указатель схем, представляющих структуры список составила ровно три пары, для которых процедура Бена вернется 3; Возвращение 4; вернуться 7; никогда не вернуться на всех.

Мое решение на следующий вопрос:

Упражнение 3.17

Разработать правильно версия графа-пар процедуры упражнения 3.16, которая возвращает количество пар в любом структура. (Подсказка: Траверс структура, содержание вспомогательных структура данных, которая используется, чтобы держать отслеживать, какие пары уже были посчитаны.)

Вот это:

(define (count-pairs x)
  (define (iter x sum already-counted)
    (if (or (not (pair? x))
            (member x already-counted))
        (list sum already-counted)
        (let ((car-result (iter (car x) (+ sum 1) (cons x already-counted))))
          (iter (cdr x) (car car-result)
                (cadr car-result)))))
  (car (iter x 0 '())))

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

(define a '(a b c))
(count-pairs a)

(set-cdr! (last-pair a) a)
(count-pairs a)

(define b '(a b c))
(set-car! b (last-pair b))

(count-pairs b)

Его можно улучшить?



633
1
задан 20 мая 2011 в 03:05 Источник Поделиться
Комментарии