SICP第57回[tube_worm死す]

練習問題4.35

(define (an-integer-between low high)
    (require (<= low high))
    (amb low (an-integer-between (+ low 1) high)))

練習問題4.36

(define (a-pythagorean-triple-between)
  (let ((high (an-integer-starting-from 1)))
    (let ((i (an-integer-between 1 high )))
      (let ((j (an-integer-between i high )))
        (let ((k high))
          (require (= (+ (* i i) (* j j)) (* k k)))
          (list i j k))))))

練習問題4.37

予想に反してBenのアルゴリズムのほうが効率が良い.

4.35のアルゴリズムが調べるのはn個の数字から3個を選ぶやり方なので _nC_3=O(n^3)

Benのものは n個の数字から2個を選ぶやり方なので _nC_2 = O(n^2)