問題4.36 – SICP(計算機プログラムの構造と解釈)その210

問題4.36

単純に an-integer-betweenan-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
計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
«
»