Euler : Problem 81

Posted by YpsilonTAKAI On 2012年5月2日水曜日 0 コメント
四角に並んだ数の角から角まで行くときの最小コストの計算

これは動的計画法ですね。
67の問題とほぼ同じなので、同じやりかたで解いてます。







この問題は三角にならんでないですけど、無いところは適当な数を入れます。
問題は、最小になるルートなので、1000000を入れてます。
nilとかにして、計算対象外にしようかとも思ったのですが、面倒なのでやめ。

コードも67とほとんど同じ。



・ get-nth-line
 今回の問題は、四角にならんでますが、斜めに見ていくので、n番目の列を取る関数。

0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9

4番目は4のところが取れるわけです。
で、データの無いところでは、1000000 が出てきます。

・ change-form
 三角形になるように順にデータを取ってくる関数。
 問題文の内容を食わせると、一番下のようになります。

・pe-80
 できた三角形を上から下にたどっていって、最大値を残してリストを生成します。

・pe-80-with-file
 ファイルから読んだデータで計算する。




0 コメント:

コメントを投稿