計算機プログラムの構造と解釈　第二版 P52 問題2.5

sicp

これは素数の性質を生かした感じの問題すね。

  • 非負の整数の対は数と算術演算だけを使って表現できることを示せ。
  • これに対応する手続きcons、car、cdrの定義はなにか。


これ、素数の性質なんだけど、

素数(wikipedia)
http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

素因数分解の一意性
どんな自然数も、素数の積に表すことができる。しかもその表し方は、かけ算の順序を入れ替えることを除けば一通りしかない（素因数分解の一意性、算術の基本定理）。このことから、素数は自然数の構成要素としての役割を果たしていると見ることができる。つまり、素数の全体は、自然数の乗法に関して自然数全体の成す集合を生成する最小の生成系になる。

どういうことかって言うと、
2と3の素数をいっぱいがんばって掛け合わせても
素因数分解すると、最終的に同じ結果にしかならないよってこと。
あえて言おう。
「自明」であると。


んで、手続きだけど、こんな感じで実装しました。

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))

(define (car z)
  (define (even-count-i n i)
    (if (even? n)
      (even-count-i (/ n 2) (+ i 1)) 
      i)) 
  (even-count-i z 0)) 


(define (cdr z)
  (define (odd-count-i n i)
    (if (= (remainder n 3) 0)
      (odd-count-i (/ n 3) (+ i 1)) 
      i)) 
  (odd-count-i z 0)) 



(define p (cons 100 25))


;; main
(define (main args)

  (display "あらかじめ、(define p (cons 100 25))を実行しておく")(newline)

  (display "(car p): ")
  (display (car p)) 
  (newline)

  (display "(cdr p): ")
  (display (cdr p)) 

  (newline)
0)


実行

あらかじめ、(define p (cons 100 25))を実行しておく
(car p): 100
(cdr p): 25


できてるね。