« Project Euler --- Problem 2 | トップページ | ジレンマ »

2009年1月17日 (土)

Project Euler --- Problem 9

今日は時間があるので、「Project Euler」ネタをもう一つ。

Problem 9 は「a + b + c = 1000 となるピタゴラスの三つ組を見つけて a, b, c の積を計算しなさい」という問題でした。

いろいろな解き方があると思いますが、自分が考えた方法のうち、最速なものを紹介します。


a² + b² = c² ...(1)
a + b + c = n ...(2)

とすると、(2) を変形して

c = n - (a + b) ...(3)

が導かれます。これを (1) に代入してさらに変形すると、

b = (n² - 2 * a * n) / (2 * (n - a))
  = n - n² / (2 * (n - a)) ...(4)

実際に (4) を計算して、b が整数になれば、それが答えになります。

(define pythagorean-triples
  (lambda (n)
    (if (odd? n)
        '()
        (let loop ([a 1][result '()])
          (let ([b (- n (/ (* n n) (- n a) 2))])
            (cond
              ([> a b] (reverse result))
              ([integer? b]
               (loop (+ a ) (cons (list a b (- n a b)) result)))
              (else (loop (+ a 1) result))))))))

  

(define problem-009
  (lambda (n)
    (printf "~d~%"
      (apply * (car (pythagorean-triples n))))))

  

(problem-009 1000)

« Project Euler --- Problem 2 | トップページ | ジレンマ »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/43768098

この記事へのトラックバック一覧です: Project Euler --- Problem 9:

« Project Euler --- Problem 2 | トップページ | ジレンマ »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ