久々のプログラミングネタです。
L-99: Ninety-Nine Lisp Problems の P58 です。
P58
Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
Example:sym-cbal-trees(5,Ts).
Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]
How many such trees are there with 57 nodes?
Investigate about how many solutions there are for a given number of nodes?
What if the number is even?
Write an appropriate predicate.
Q1 ノードが 57 個のとき、シンメトリーな木のパターンはいくつありますか?
これはまともに木と作っていたのでは解けない問題です。
いつものようにエクセル先生に計測結果のデータをはっつけて傾向と対策を探ります。
事象を計測し、データを集め、法則性を導き出します。物理測定的な解法アプローチです。
;; シンメトリになる木の形状数とノード数の関係 ;; A ... 木が完全に釣り合い、かつ底辺の部分のノードが全てそろっているときの底辺のノード数 ;; B ... A の補完用の数 ;; C ... ノードの総個数 ;; D ... シンメトリな木がいくつ出来るかの数 ;; A B C D ;; 1 1 1 ;; 2 3 1 ;; 3 5 2C1 ;; 4 7 1 ;; 5 9 4C1 ;; 6 11 4C2 ;; 7 13 4C3 ;; 8 15 1 ;; 9 17 8C1 ;; 10 19 8C2 ;; 11 21 8C3 ;; 12 23 8C4 ;; 13 25 8C5 ;; 14 27 8C6 ;; 15 29 8C7 ;; 16 31 1 ;; 17 33 16C1 ;; 18 35 16C2 ;; 19 37 16C3 ;; 20 39 16C4 ;; 21 41 16C5 ;; 22 43 16C6 ;; 23 45 16C7 ;; 24 47 16C8 ;; 25 49 16C9 ;; 26 51 16C10 ;; 27 53 16C11 ;; 28 55 16C12 ;; 29 57 16C13 ;; 30 59 16C14 ;; 31 61 16C15 ;; 32 63 1 ;; ...
こうなります。
このように書き出す事で、法則性があることが簡単にわかります。
ではプログラムを書いていきましょう。
まず組み合わせを計算する手続きを定義します。
(define (fact n x) (if (= n 0) x (fact (- n 1) (* n x)))) (define (perm n r) (/ (fact n 1) (fact (- n r) 1))) (define (comb n r) (/ (perm n r) (fact r 1)))
もっと最適化したほうが良い気がしますが、とりあえずこれで良いです。
次に sym-cbal-trees 手続きを定義します。
(define (sym-cbal-trees num) (if (even? num) 0 (let ((node (log (ceiling (/ num 2)) 2))) (if (integer? node) 1 (let* ((n (expt 2 (x->integer (floor node)))) (r (/ (- num (- (* n 2) 1)) 2))) (comb n r))))))
評価してみます。
gosh> (sym-cbal-trees 57) 560
ノードが 57 個ある場合のシンメトリーな木のパターン数は 16C13 = 560 通りあります。
gosh> (time (sym-cbal-trees 9999)) ;(time (sym-cbal-trees 9999)) ; real 0.031 ; user 0.016 ; sys 0.016 11436577103049044761221198452518585133677289942544128222443208541369564296810237881125967457185479641859012730749157186026337918310836632184920317429918436832010257712575772912316220048781763180094007260818057119503806472024206237596484037000140955340252760462967607750042611650203259940138602730532492794523053088567877493404920122261243367706161155208567426628443813443651696627343049842580327429128644640369480496760583320982834694512737735411260748844111840176823690848814303441663535288847068276026265786809416498272260267278458991790785446499622063519550479432824371337083954743633428654825784779186826178487299263070808528918377649365725029528130681578375288057135466767026007948970298778625485276413177715104731228883683342449139314942649780402785046948110513608918309676805587816441279133004480534189254221248137175247422703164594490199643957079542420945088581088725822489773787042972410242180451209340578022707144445821125127680
ノードが 9999 個の場合もすぐ求まります。
巨大な数字すぎて読み方がわかりませんが、これだけの組み合わせがあります。
Q2 ノード数が偶数の場合はどうなりますか?
ノード数が偶数の場合は、シンメトリーな木は作れません。ノード数が偶数の場合は、0 通りです。