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

2009年6月26日 (金)

Project Euler - Problem 18

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


まず、最初に考えついた方法。

def select(i, j) return 0 unless $arr[i] v1 = select(i + 1, j) v2 = select(i + 1, j + 1) return $arr[i][j] + [v1, v2].max end $arr = Array.new DATA.each_line do |data| $arr.push(data.chomp!.split.map{|st| st.to_i}) end puts select(0, 0)

三角形の上の方から再帰的に最大値を求めています。

再帰的なアプローチは、終了条件と再帰手続きのルールさえ決めてしまえば終わりなので、慣れると結構簡単にできてしまいます。

しかしこの場合は、結局すべての経路を探索することになるし、メソッドを再帰的に呼び出すコストもかかるので、当然非常に遅くなります。

この問題ではまだいいのですが、Problem 67 を同じ方法で試してみたら、とても遅くて話になりませんでした。


ということで、次に考えたのがこちら

def check(arr1, arr2) ans = arr2.map.with_index do |v, i| v + [arr1[i], arr1[i + 1]].max end return ans end arr = Array.new DATA.each_line do |data| arr.push(data.chomp!.split.map{|st| st.to_i}) end arr.reverse! ans = arr.shift arr.each do |a| ans = check(ans, a) end puts ans[0]

三角形の底辺の方から、隣接する数字のうち大きいものを上の段の数字に足していく方法です。

この方法は、上記の再帰的な方法とは逆に、どんどん候補が減っていくので、Problem 67 のようなデータの数が多い問題でも、非常に速く答が出ます。

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

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

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

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

最近のトラックバック

無料ブログはココログ