問題4.36 – SICP(計算機プログラムの構造と解釈)その210
2009年06月30日
問題4.36
単純に an-integer-between
を an-integer-starting-from
に変更しただけでは、任意の Pythagoras 三角形を生成する方法として適切でない理由は。
an-integer-starting-from
は継続を失敗することが無いために無限に継続するので、バックトラックできないため計算ができない。
正常に計算できるためには、最大値を与えて継続の範囲を限定し、バックトラックできるようにする必要がある。
三角形の長辺 k
をまず指定し、残りの2つの短辺の最大値を長辺の長さに限定し、バックトラックできるようにする。
(define (a-pythagorean-triple-from n) (let ((k (an-integer-starting-from n))) (let ((i (an-integer-between n k))) (let ((j (an-integer-between i k))) (require (= (+ (* i i) (* j j)) (* k k))) (list i j k)))))
実行結果
;;; Amb-Eval input: (define (require p) (if (not p) (amb))) ;;; Starting a new problem ;;; Amb-Eval value: ok ;;; Amb-Eval input: (define (an-integer-between low high) (require (< low high)) (amb low (an-integer-between (+ low 1) high))) ;;; Starting a new problem ;;; Amb-Eval value: ok ;;; Amb-Eval input: (define (an-integer-starting-from n) (amb n (an-integer-starting-from (+ n 1)))) ;;; Starting a new problem ;;; Amb-Eval value: ok ;;; Amb-Eval input: (define (a-pythagorean-triple-from n) (let ((k (an-integer-starting-from n))) (let ((i (an-integer-between n k))) (let ((j (an-integer-between i k))) (require (= (+ (* i i) (* j j)) (* k k))) (list i j k))))) ;;; Starting a new problem ;;; Amb-Eval value: ok ;;; Amb-Eval input: (a-pythagorean-triple-from 1) ;;; Starting a new problem ;;; Amb-Eval value: (3 4 5) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (6 8 10)
もう少しわかりやすいように、try-again
する度に、数が1増加していく手続きを作ってみる。
(define (num-from n) (let ((i (an-integer-starting-from n))) (let ((j (an-integer-between i (+ i 1)))) j)))
実行結果
;;; Amb-Eval input: (define (num-from n) (let ((i (an-integer-starting-from n))) (let ((j (an-integer-between i (+ i 1)))) j))) ;;; Starting a new problem ;;; Amb-Eval value: ok ;;; Amb-Eval input: (num-from 1) ;;; Starting a new problem ;;; Amb-Eval value: 1 ;;; Amb-Eval input: try-again ;;; Amb-Eval value: 2 ;;; Amb-Eval input: try-again ;;; Amb-Eval value: 3 ;;; Amb-Eval input: try-again ;;; Amb-Eval value: 4
計算機プログラムの構造と解釈
posted with amazlet at 08.11.07
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
ピアソンエデュケーション
売り上げランキング: 6542