Comments

Collatz 予想 by ぱるも日記 — last modified 2006-07-13 00:05

キミならどう書く 2.0 - ROUND 2 - が発表されました。前回の問題「100までの整数から素数を列挙せよ」にもPerl で答えたので、今回も Perl で自分なりに挑戦してみます。(^_^) ちょっと長いですが、以下問題の引用です。 Collatz予想の収束までのステップ数の最大値を求め

Collatz予想(Mathematica, Lisp) by inquisitor — last modified 2006-07-13 00:02

f[1] = 1; f[n_?EvenQ] := Hold[f[n/2]]; f...

Collatz予想 in Haskell (Stack Overflow回避) by haskellのある暮らし — last modified 2006-07-12 15:11

昨日のものを使って、引数があまりに大きい(1000000 とか)ケースではスタックオーバフローになってしまった。 理由は2つある。第一に、 hState のケースなどだが、値が大きくなりすぎて Int がオーバフローしてしまい負値になり、 g の計算がおかしくなってしまう場合。こういう場合には IntMap を使うことができない。あるいは maxBound までは IntMap を使い、それ以外の場合には計算結果を保持しないようにするべきか……。 第二の理由は、 maximum の評価が lazy ...

collatz予想 in Haskell (State and HashTable example) by haskellのある暮らし — last modified 2006-07-12 15:10

http://ll.jus.or.jp/2006/blog/doukaku2 とりあえずこうかなあ。 ふつうすぎてつまらんので、State をつかって効率化を図ってみよう。 効率化の差は？ さすがに顕著に速い。ちなみに IntMap というのは、 Map に似て木構造を使って高速に索引可能な連想コンテナですが、キーには Int しか使えません。かわりに高速に動作するらしい。内部構造にはパトリシア木が使われているらしい。そんな感じのブツです。 IO を使った場合。 だいぶふつうの ...

LL2006 君ならどう書く ROUND2 by FloralCompany.log — last modified 2006-07-12 14:01

Round2はCollatz予想というものらしい. で、早速 #!perl # ...

キミならどう書く 2.0 - ROUND 2 - by ヒビルテ — last modified 2006-07-12 11:37

与えられた範囲の中でCollatz予想の収束までのステップ数が最大となる値を求める問題。とりあえず、Haskellで超素朴なコードで試してみたら「h 1000000」に40秒くらいかかった。
import List

g 1 = 1
g n = 1 + g (if even n then n `div` 2 else 3*n + 1)

h n = fst $ maximumBy c [(k, g k) | k <- [1..n]]
where c (_,x) (_,y) = x `compare` y
実行結果。
Main> h 100
97
Main> h 1000000
837799
以下のようにして100000までの値をテーブル化すると7秒まで縮んだ。
更に効率化するにはどうすれば良いだろう?
import List
import Array

tableMax = 100000
table = array (1, tableMax) [(i, g' i) | i <- [1..tableMax]]

g n = if n <= tableMax then table ! n else g' n

g' 1 = 1
g' n = 1 + g (if even n then n `div` 2 else 3*n + 1)

h n = fst $ maximumBy c [(k, g k) | k <- [1..n]]
where c (_,x) (_,y) = x `compare` y

Collatz予想のRubyによる実装と言い替え by ratio - rational - irrational — last modified 2006-07-12 10:18

LL Ringのキミならどう書く 2.0 ROUND 2だけど、昨日は別の言語で...

[ruby]Collatz予想の収束までのステップ数の最大値 by sshi.Continual — last modified 2006-07-12 04:47

http://ll.jus.or.jp/2006/blog/doukaku2 LLRingの「キミならどう書く 2.0」でお題がでてたので、rubyで書いてみた。素朴なメモ化以外の工夫なし。コメントはずすとメモした値が見れます。 @memo = {1=>1} def g(n) @memo[n] ||= 1 + if (n % 2) == 0 then g(n/2) else