Hatena::Groupcsnagoya-sicp

mzpの日記

2008-10-27

パスカルの三角形

はてなブックマーク - パスカルの三角形 - mzpの日記

(use srfi-1)
(define (pascal n k)
  (cond [(= n 0) 1]
	[(= k 0) 1]
	[(= n k) 1]
	[else (+ (pascal (- n 1) k) (pascal (- n 1) (- k 1)))]))

(define (pascal-line n)
  (map (cut pascal n <>) (iota (+ n 1))))

(define (pascal-tri n)
  (string-join
   (map (lambda (k)
	  (string-append 
	   (make-string (- n k) #\space)
	   (string-join (map number->string (pascal-line k)) " ")))
	(iota n))
   "\n"))

id:clairvyさんが描画もしろー、っていっていたので。

(print (pascal-tri 4))
    1
   1 1
  1 2 1
 1 3 3 1
#<undef>

;; 2桁になると崩れる
gosh> (print (pascal-tri 10))
          1
         1 1
        1 2 1
       1 3 3 1
      1 4 6 4 1
     1 5 10 10 5 1
    1 6 15 20 15 6 1
   1 7 21 35 35 21 7 1
  1 8 28 56 70 56 28 8 1
 1 9 36 84 126 126 84 36 9 1
#<undef>

末尾再帰だけど、反復的プロセスじゃないやつ

はてなブックマーク - 末尾再帰だけど、反復的プロセスじゃないやつ - mzpの日記

いわゆるCPS

(define (fact k n)
  (if (= n 1)
      (k 1)
      (fact (lambda (m) (k (* n m))) (- n 1))))

こうすると末尾再帰だけど、呼ぶたびにkがどんどん膨らんでいくので、反復的じゃなくなる。

てすと

はてなブックマーク - てすと - mzpの日記

(display "Hello,world!!")

ゲスト



トラックバック - http://csnagoya-sicp.g.hatena.ne.jp/mzp/20081027