ex-1.10 | SICP | OSS-Web

Open Source WEB

Chat (Lingr.com)

Informaiton

Daily

今日の一行(2010-04-02)

Column

Zope Solution

Extra

JavaCube

OSS案内所

Site Info

##(link2sicp "book-Z-H-11.html#%_thm_1.10" "Exercise 1.10")

原始再帰関数(primitive recursive function)ではない関数の例として教科書にでてくる Ackermann 関数は以下のような定義になっている。

(define (Ackermann x y)
  (cond ((= x 0) (+ y 1))
        ((= y 0) (Ackermann (- x 1) 1))
        (else (Ackermann (- x 1)
                         (Ackermann x (- y 1))))))

閑話休題

解答例

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* y 2))
        ((= y 1) 2)
        (else (A (- x 1)
              (A x (- y 1))))))

(A 1 10) ;==> 1024
(A 2 4)  ;==> 65536
(A 3 3)  ;==> 65536

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))

; (f n) == 2 * n
; (g n) == 2 ^ n
; (h n) == 2 ^ 2 ^ ... ^ 2
;          |-------------|
;                n個

コード

##(sicp-answer-code "ex-1.10.scm")

このサイトは、 IPA の「平成15年度オープンソフトウエア活用基盤整備事業」の委託事業として開発されたKahuaで試験的に運用しております。