ホーム - Project Euler

Problem 39¶

Integer Right Triangles¶

If $p$ is the perimeter of a right angle triangle with integral length sides, ${a, b, c}$, there are exactly three solutions for $p = 120$.

${20,48,52}$, ${24,45,51}$, ${30,40,50}$

For which value of $p \le 1000$, is the number of solutions maximised?

整数の直角三角形¶

辺の長さが整数の3つ組{a,b,c}である直角三角形を考え, その周囲の長さを p とする. p = 120のときには3つの解が存在する:

{20,48,52}, {24,45,51}, {30,40,50}

p ≤ 1000 のとき解の個数が最大になる p はいくつか?

(import (scheme base)
        (gauche base))

(define triangle-list
  (let loop1 ([p 3] [result '()])
    (if (< 1000 p)
      result
      (let ([a-max (div p 3)])
        (let loop2 ([a 1]
                    [result result]
                    [temp-result '()])
          (if (< a-max a)
            (loop1 (+ p 1)
                   (if (null? temp-result)
                     result
                     (cons temp-result result)))
            (let loop3 ([b a]
                        [result result]
                        [temp-result temp-result])
              (let ([c (- p a b)])
                (if (< c b)
                  (loop2 (+ a 1) result temp-result)
                  (if (= (+ (* a a)
                            (* b b))
                         (* c c))
                    (loop3 (+ b 1)
                           result
                           (cons `(,a ,b . ,c) temp-result))
                    (loop3 (+ b 1)
                           result
                           temp-result)))))))))))

(define count-triangle
  (map (^[lis]
         (let* ([current (car lis)]
                [a (car current)]
                [b (cadr current)]
                [c (cddr current)])
           `(,(+ a b c) . ,(length lis))))
       triangle-list))

(define max-count-triangle
  (fold (^[c max-lis]
          (if (< (cdr max-lis) (cdr c))
            c
            max-lis))
        '(0 . 0)
        count-triangle))

(define answer-39
  (car max-count-triangle))

(format #t "39: ~d~%" answer-39)