#author("2022-11-03T02:32:24+00:00","","")
*[[Problem 67:http://projecteuler.net/problem=67]] 「最大経路の和 その2」 [#jde9a29d]

以下の三角形の頂点から下まで移動するとき, その数値の合計の最大値は23になる.

CENTER:
&color(red){3};~
&color(red){7}; 4~
2 &color(red){4}; 6~
8 5 &color(red){9}; 3

この例では 3 + 7 + 4 + 9 = 23

100列の三角形を含んでいる15Kのテキストファイル [[triangle.txt:https://projecteuler.net/project/resources/p067_triangle.txt]] (右クリックして, 『名前をつけてリンク先を保存』)の上から下まで最大合計を見つけよ.

''注'':これは, [[Problem 18]]のずっと難しいバージョンです. ~
全部で2&sup{99}; 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません!~
あなたが毎秒1兆本の(10&sup{12};)ルートをチェックすることができたとしても, 全てをチェックするために200億年以上かかるでしょう. ~
全部で&tex{2^{99}}; 通りの組み合わせがあるので, この問題を解決するためにすべてのルートをためすことは可能でありません!~
あなたが毎秒1兆本の(&tex{10^{12}};)ルートをチェックすることができたとしても, 全てをチェックするために200億年以上かかるでしょう. ~
解決するための効率的なアルゴリズムがあります. ;o)

IP:112.68.65.182 TIME:"2022-11-03 (木) 11:32:24" REFERER:"http://odz.sakura.ne.jp/projecteuler/?cmd=edit&page=Problem+67" USER_AGENT:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/107.0.0.0 Safari/537.36"

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS