Serendip

Web Studio

問題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

Amazon.co.jp で詳細を見る