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-16

L-99 (60)

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

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

P59変形で、高さの代わりにノード数を与え、バランス

の取れた木を生成するというお題。

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

P60

解答
N = 15のとき生成される木の組み合わせは、1553通り。
(length (hbal-tree-nodes 15))
=> 1553
;;; ---------------------------------------------------------------------------
;;; common lisp
;;; ---------------------------------------------------------------------------
(defun max-nodes (h)
  (1- (expt 2 h)))

(defun min-nodes (h)
  (do ((h h (1- h))
       (res 2 (+ 1 res acc))
       (acc 1 res))
      ((< h 3) res)))

#|(defun min-nodest (h a1 a2)
  (if (< h 3)
      a1
      (min-nodest (1- h) (+ 1 a1 a2) a1)))|#

(defun max-height (n)
  (do ((i 0 (1+ i)))
      ((> (min-nodes i) n) (1- i))))

(defun min-height (n)
  (1+ (truncate (log n 2))))

(defun hbal-tree-nodes (n)
  (let ((min-height (min-height n))
	(max-height (max-height n)))
    (do ((h min-height (1+ h))
	 res)
	((> h max-height) res)
      (setq res `(,@(remove-if-not (lambda (x) (= n (count-leaf x)))
				   (hbal-tree h))
		    ,@res)))))