« Project Euler - Problem 13 | トップページ | Project Euler - Problem 15, 16, 17 »

2009年6月22日 (月)

Project Euler - Problem 14

問題はこちらをご覧ください。


有名な「Collatz の問題」です。

以前、この「Collatz の問題」を知ったときに、大変興味深かったので、こんなスクリプトを書いて、いろんな数がどうやって 1 に収束していくかを実験したことがありました。

;; Chez Scheme 版 (define collatz (lambda (n) (let loop ((s 1) (i n)) (printf "step ~3d : ~8d~%" s i) (cond ((= i 1) (printf "終了~%")) ((even? i) (loop (+ s 1) (/ i 2))) (else (loop (+ s 1) (+ (* i 3) 1)))))))

今回は生成される数列の長さだけが必要なので、まずこんなスクリプトを書いてみました。

MAX = 100_0000 max = [1, 1] 2.upto(MAX - 1) do |n| v = n c = 1 begin if v.even? then v = v / 2 else v = v * 3 + 1 end c = c + 1 end until v == 1 max = [n, c] if c > max[1] end puts max[0]

このスクリプトは真面目にすべての数を計算するので、非常に遅いです。

Ruby 1.9 で 34 秒ほどかかりました。


ところで、この「Collatz の問題」ではすべての数が 1 に収束すると仮定されています。この仮定が正しいとするならば、すべての数はどこか途中から同じプロセスをたどって 1 に収束していくはずです。

そこで、小さい数の順に生成される数列の長さを記録していき、数列の中に既に記録された数が現れた場合はそれ以上計算しないようにしてみました。

いわゆる Memoize というやつです。『まつもとゆきひろ コードの世界』で「空間で時間を買う」と表現された高速化の一種です。

MAX = 100_0000 collatz = Array.new(MAX, 1) max = [1, 1] 2.upto(MAX - 1) do |n| v = n c = 0 while v >= n if v.even? then v = v / 2 else v = v * 3 + 1 end c = c + 1 end count = c + collatz[v] collatz[n] = count max = [n, count] if count > max[1] end puts max[0]

これだと、Ruby 1.9 で約 2 秒ほどで答が出ました。効果は絶大です。

しかし N88-BASIC の時代からコンピュータに触れている私にとって、「空間で時間を買う」という表現はとても贅沢な響きを持っています。

なんたって、私が初めて買った「PC-8801 MH」のメモリは 128KB でしたからねぇ……。ところが今や、1GB や 2GB は当たり前……。

時代の流れを感じますねぇ……。

« Project Euler - Problem 13 | トップページ | Project Euler - Problem 15, 16, 17 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 13 | トップページ | Project Euler - Problem 15, 16, 17 »

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

最近のトラックバック

無料ブログはココログ