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

L-99 (59)

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

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

今度は、木の高さのバランスを取りつつ与えられた高さ

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

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

P59

;;; ---------------------------------------------------------------------------
;;; common lisp
;;; ---------------------------------------------------------------------------
(load "comb2")

(defun hbal-tree (h)
  (remove-if-not #'hbal-tree-p (gen-tree-h h)))

(defun gen-tree-h (h)
  (cond ((zerop h) '(()))
	((= h 1)   '((x () ())))
	((= h 2)   '((x (x () ()) () )
		     (x () (x () ()))
		     (x (x () ()) (x () ()) )))
	((> h 2)
	 (let ((h-1 (gen-tree-h (1- h)))
	       (h-2 (gen-tree-h (- h 2))))
	   (map 'list (lambda (item) `(x ,@item))
		`(,@(comb2 h-1 h-1)
		  ,@(comb2 h-1 h-2)
		  ,@(comb2 h-2 h-1))))
	('T (error "Bad arg to gen-tree-h"))))

(defun hbal-tree-p (tree)
  (>= 1 (abs (- (tree-height (cadr tree))
		(tree-height (caddr tree))))))

(defun tree-height (tree)
  (if tree
      (1+ (max (tree-height (cadr tree)) 
	       (tree-height (caddr tree))))
      0))

ゲスト



トラックバック - http://cadr.g.hatena.ne.jp/g000001/20070913