« Project Euler - Problem 4 再び | トップページ | Project Euler - Problem 39 : ループの抽象化 »

2009年4月23日 (木)

Project Euler - Problem 44

問題はこちらを参照してください。


特定の範囲の五角数を列挙して、その中で条件に合うものを探していく方法もありますが、それだと、

  • 範囲の上限を決めるのが難しい。
  • 差 D が最小であることを確認するのが難しい。

という問題があると思います

そこで今回は、次のような作戦を考えました。

  1. P1 = 1 を list に push しておく。
  2. 小さい順に五角数 (Pn) を求める。
  3. Pn と list の中の数を list の先頭から比較していく。
  4. 条件に合うペアが見つかれば終了。見つからなければ Pn を list の先頭に push して 2. に戻る。

この方法だと、上限を設定せずにペアが見つかるまで探索を続けられます。また、list の中の数は大きい順に並んでいるので、条件に合うペアが見つかった時点で、差 D は最小になっているはずです。


まずは Scheme 版です。

;;; ;;; (pentagon-number n) ;;; ;;; * n 番目の五角数 ;;; * Pn = n * (3 * n - 1) / 2 ;;; (define pentagon-number (lambda (n) (/ (- (* 3 n n) n) 2))) ;;; ;;; (pentagon-number? n) ;;; ;;; * n が五角数なら何番目かを返す ;;; (define pentagon-number? (lambda (n) (let* ([a (sqrt (+ 1 (* 24 n)))] [b (/ (+ 1 a) 6)]) (if [integer? b] b #f)))) ;;; Problem 44 (define problem-044 (lambda () (define pentagon-lst '(1)) (define check (lambda (p) (exists (lambda (x) (if [and (pentagon-number? (- p x)) (pentagon-number? (+ p x))] (cons p x) #f)) pentagon-lst))) (let loop ([i 2]) (let* ([p (pentagon-number i)] [ans (check p)]) (if ans (let ([a (car ans)] [b (cdr ans)]) (printf "~d : (~d, ~d)~%" (- a b) a b)) (begin (set! pentagon-lst(cons p pentagon-lst)) (loop (+ i 1)))))))) (problem-044)

ちょっと時間はかかりますが、約 10 秒で答が出ます。


次に Ruby 版です。

class Integer def pentagon return ((3 * self * self - self) / 2) end def pentagon? x = (1 + Math.sqrt(1 + 24 * self)) / 6 return (x == x.to_i) end end penta_list = [1] 2.upto(1/0.0) do |i| p = i.pentagon penta_list.each do |j| if ((p - j).pentagon? and (p + j).pentagon?) then print"#{p - j}\n" exit end end penta_list.unshift(p) end

今回はちょっと驚くことがありました。

これまで同じアルゴリズムでコードを書いた場合、 Chez Scheme のほうが Ruby1.8 より数倍速く結果が出たのですが、なぜか今回はほぼ同じ時間で結果が出ました。Ruby1.9 を使った場合は、約 5 秒で答がでました。

原因ははっきりしませんが、Chez Scheme の list 処理よりも Ruby の配列の処理のほうが効率が良いのでしょうか?

« Project Euler - Problem 4 再び | トップページ | Project Euler - Problem 39 : ループの抽象化 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 4 再び | トップページ | Project Euler - Problem 39 : ループの抽象化 »

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            
フォト

最近のトラックバック

無料ブログはココログ