黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

Project Euler Problem 18:部分和問題と同じやりかたで、「15*15」のピラミッド型の整数の総和の最大値を求めた

問題(本サイトより)

Project Euler 18の問題はこちら。要はn段のピラミッド型に並んでいる整数があり、一番上の段から計算を始め、今居る数字に隣接する数字を一番下の段まで足し合わせていく。その総和の最大値を求めると言うもの。問題はn=4の場合について書かれている。


f:id:program_study:20150606122858p:plain

この場合においては3+7+4+9=23を選択した場合が最大となる。ここで問題は、以下のn=15段のピラミッド型の総和の最大値を求める事がテーマだ。


f:id:program_study:20150606123838p:plain


n=4の場合で解答を練る

部分和問題を解く流れ

この問題は部分和問題で、以前紹介した「【アルゴリズム】プログラミングコンテストチャレンジブック[第2版] P34の部分和問題を、boolを使わないで解いてみた」の類題に当たる。

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

さて部分和問題を解く際のコツは、ある整数xを含む場合とある整数xを含まない場合とで再帰を取り、その大きい物を現在の部分和として採用する方法をとる事だ。

自分はまず簡単な状況で答えが出せるかを確認し、実際の問題に取りかかることにした。今回は二次元配列を用い、数字が省略された部分の整数は全て0として設定。隣接する数字と言う条件に注意した。下の図のように再帰を組む事にした。


f:id:program_study:20150606123123p:plain

ソースコード

上の図の矢印の方向に注目し再帰を組み、以下のようなコードを書いた。

n=4の場合の実行結果

その結果以下の順序で探索*1が行われた。

ここで以下のsum(i,j)が現在の探索している位置における総和の値、maxがその最大値に当たる。max=23より、n=4のときの最大値は23である事が分かる。

sum(0,0)=3
sum(1,1)=7
sum(2,2)=13
sum(3,3)=16
sum(3,2)=22
sum(2,1)=11
sum(3,2)=20
sum(3,1)=16
sum(1,0)=10
sum(2,1)=14
sum(3,2)=23
sum(3,1)=19
sum(2,0)=12
sum(3,1)=17
sum(3,0)=20
max=23

本問題(n=15)の解答

そして準備ができたので、いよいよ本題の場合で問題を解こう。問題の配列の設定を変えて部分和を求める。このとき念のためピラミッドの段数が多いので、計算結果を配列にメモし既に計算した値は配列から呼び出すように設定を変更した(動的計画法)。

プログラムの実行結果は割愛するが、以下のソースコードにより、最大値1074である事が分かる。

ちなみにUNIXのtime関数における実行速時間を1度だけ計測すると、「user 0m0.002s」より2[ms]であった。ピラミッドの段数nが大きくなると実行時間はどう変化するか気になる所だ。

最後に

とりあえず問題ができたので、復習と皆さんに見てもらう事をかねて掲載。又機会があったらproject Eulerの近況をブログに書きたいなと思っている。

*1:恐らく深さ優先探索アルゴリズムだとおもうが、断言する自信無い(汗)。詳しくはこちらを参照