Problem 9

三平方の定理。懐かしいな。

ピタゴラスの三つ組(ピタゴラスの定理を満たす整数)とはa

うぅん。

考えてみたけど、力ずくで解く方法しか思いつかず。

(define (problem9 n)
  (define (square x) (* x x))
  (define (iter a b c)
    (cond ((= (square c) (+ (square a) (square b))) (list a b c))
          ((>= a (+ b c)) (error "not found."))
          ((>= b c) (iter (+ a 1) (+ a 2) (- (- n (+ a 1)) (+ a 2))))
          (else
            (iter a (+ b 1) (- c 1)))))
  (iter 1 2 (- n 3)))

(problem9 (+ 3 4 5)) ; (3 4 5)
(problem9 1000) ; (200 375 425)

時間は思った程かからなかったけど、力ずくで解く以外のスマートな方法がありそうだ。

調べてみる

回答は出たけれど、やっぱり力づく以外の方法があるに違いない。気になるので調べてみると、

ピタゴラスの定理

「ピタゴラス数」

あった。

つまり

2m(m + n) = 1000になるm,nを見つければいい。

(define (problem9 x)
  (define (square x) (* x x))
  (define (calc m n)
    (list (- (square m) (square n))
          (* 2 m n)
          (+ (square m) (square n))))
  (define (iter m n cont)
    (let ((result (* 2 (+ (square m) (* m n)))))
         (cond ((= result x) (cont m n))
               ((negative? (- (square m) (square n)))
                (iter (+ m 1) 1 cont))
               ((> result x)
                (if (= n 1)
                    (error "not found.")
                    (iter (+ m 1) 1 cont)))
               (else
                 (iter m (+ n 1) cont)))))
  (iter 2 1 (lambda (m n)
              (format "~a\n~a" (list m n) (calc m n)))))

(problem9 1000) ; (20 5)
                ; (375 200 425)

aとbが逆だけど、O^3がO^2になったし、無駄も少ない。まだ判定がイマイチかも。