Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2007-09-26

L-99 (63)

| 02:58 | L-99 (63) - わだばLisperになる を含むブックマーク はてなブックマーク - L-99 (63) - わだばLisperになる

L-99 P63に挑戦 - L-99:Ninety-Nine Lisp Problems

今回は、木の各ノードに番号を振ってゆくというお題。

左のノードを優先して埋めて行き、かつノードの番号付

けは、

         1
   2           3
 4    5     6     7
8 9 10 11 12 13 14 15

のようになるようなので、そういう風に作ったつもりで

ございます。

残りの問題:'(66 80-94 96-99) 解答状況 65/84

P63

回答
;;; ---------------------------------------------------------------------------
;;; common lisp
;;; ---------------------------------------------------------------------------
(load "max-nodes")

(defun complete-binary-tree (n &optional (base 1))
  (if (zerop n)
      ()
      (let ((cn-max-size (max-nodes (1- (cbt-height n))))
	    (gcn-max-size (max-nodes (- (cbt-height n) 2)))
	    (cn (1- n)))
	(cond ((= cn (* 2 cn-max-size))
	       `(,base ,(complete-binary-tree cn-max-size (* 2 base))
		       ,(complete-binary-tree cn-max-size (1+ (* 2 base)))))
	      ((> cn cn-max-size)
	       `(,base ,(complete-binary-tree cn-max-size (* 2 base))
		       ,(complete-binary-tree (- cn cn-max-size) (1+ (* 2 base)))))
	      ((<= cn cn-max-size)
	       `(,base ,(complete-binary-tree (- cn gcn-max-size) (* 2 base))
		       ,(complete-binary-tree gcn-max-size (1+ (* 2 base)))))))))

(defun cbt-height (n)
  (if (zerop n) n (1+ (truncate (log n 2)))))