Serendip

Web Studio

問題2.64a

partial-tree はリストとその長さを引数として与えられ、長さからリストを半分に分ける。
中間の要素でエントリを、前のリストで左部分木を、後ろのリストで右部分木を作る。
結果は"エントリと左部分木と右部分木とで構成された木" と "木に含まれなかった要素から成るリスト" を cons したものを返す。

(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
           (let ((left-result (partial-tree elts left-size)))
                (let ((left-tree (car left-result))
                      (non-left-elts (cdr left-result))
                      (right-size (- n (+ left-size 1))))
                     (let ((this-entry (car non-left-elts))
                           (right-result (partial-tree (cdr non-left-elts) right-size)))
                          (let ((right-tree (car right-result))
                                (remaining-elts (cdr right-result)))
                               (print "left-size: " left-size)
                               (print "left-result: " left-result)
                               (print "right-result: " right-result)
                               (print "this-entry: " this-entry)
                               (print "left-tree: " left-tree)
                               (print "right-tree: " right-tree)
                               (print (cons (make-tree this-entry left-tree right-tree) remaining-elts))
                               (newline)
                               (cons (make-tree this-entry left-tree right-tree)
                                     remaining-elts))))))))

(list->tree '(1 3 5 7 9 11))

left-size: 0
left-result: (() 3 5 7 9 11)
right-result: (() 5 7 9 11)
this-entry: 3
left-tree: ()
right-tree: ()
((3 () ()) 5 7 9 11)

left-size: 0
left-result: (() 1 3 5 7 9 11)
right-result: ((3 () ()) 5 7 9 11)
this-entry: 1
left-tree: ()
right-tree: (3 () ())
((1 () (3 () ())) 5 7 9 11)

left-size: 0
left-result: (() 7 9 11)
right-result: (() 9 11)
this-entry: 7
left-tree: ()
right-tree: ()
((7 () ()) 9 11)

left-size: 0
left-result: (() 11)
right-result: (())
this-entry: 11
left-tree: ()
right-tree: ()
((11 () ()))

left-size: 1
left-result: ((7 () ()) 9 11)
right-result: ((11 () ()))
this-entry: 9
left-tree: (7 () ())
right-tree: (11 () ())
((9 (7 () ()) (11 () ())))

left-size: 2
left-result: ((1 () (3 () ())) 5 7 9 11)
right-result: ((9 (7 () ()) (11 () ())))
this-entry: 5
left-tree: (1 () (3 () ()))
right-tree: (9 (7 () ()) (11 () ()))
((5 (1 () (3 () ())) (9 (7 () ()) (11 () ()))))

(5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

問題2.64b

list->tree が n 個の要素のリストを変換するのに必要なステップ数は θ(n)。

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る