Problem 149
の編集
http://odz.sakura.ne.jp/projecteuler/index.php/image/pukiwiki.png?Problem+149
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[Problem 149:http://projecteuler.net/problem=149]] 「和が最大となる部分列の探索」 [#q0ee6343] 下の表において, 任意の方向(縦横斜め)に隣り合うものの和の最大値は 16 (= 8 + 7 + 1) となることは簡単に確かめられる. |-2|5|3|2| |9|-6|5|1| |3|2|7|3| |-1|8|-4|8| いま, 同じ探索をより大きなものについてもしてみることにする. まず, 400万個の擬似乱数を "Lagged Fibonacci Generator" によって生成する. 1 ≤ &tex{k}; ≤ 55 について, &tex{s_{k} = [100003 - 200003k + 300007k^{3}] (modulo 1000000) - 500000}; ~ 56 ≤ &tex{k}; ≤ 4000000 について, &tex{s_{k} = [s_{k-24} + s_{k-55} + 1000000] (modulo 1000000) - 500000}; つまり, &tex{s_{10} = -393027 , s_{100} = 86613}; となる. &tex{s}; の項は, 最初の 2000 個を最初の行に(順番に), 次の 2000 個を 2 番目の行に, というように, 2000x2000 の表に並べ替えられる. 任意の方向(縦横斜め)に隣り合うものの和の最大値を求めよ. (連続して足す領域は 3 マス以上でもよい, 斜め 4 マス等も認める)
タイムスタンプを変更しない
*[[Problem 149:http://projecteuler.net/problem=149]] 「和が最大となる部分列の探索」 [#q0ee6343] 下の表において, 任意の方向(縦横斜め)に隣り合うものの和の最大値は 16 (= 8 + 7 + 1) となることは簡単に確かめられる. |-2|5|3|2| |9|-6|5|1| |3|2|7|3| |-1|8|-4|8| いま, 同じ探索をより大きなものについてもしてみることにする. まず, 400万個の擬似乱数を "Lagged Fibonacci Generator" によって生成する. 1 ≤ &tex{k}; ≤ 55 について, &tex{s_{k} = [100003 - 200003k + 300007k^{3}] (modulo 1000000) - 500000}; ~ 56 ≤ &tex{k}; ≤ 4000000 について, &tex{s_{k} = [s_{k-24} + s_{k-55} + 1000000] (modulo 1000000) - 500000}; つまり, &tex{s_{10} = -393027 , s_{100} = 86613}; となる. &tex{s}; の項は, 最初の 2000 個を最初の行に(順番に), 次の 2000 個を 2 番目の行に, というように, 2000x2000 の表に並べ替えられる. 任意の方向(縦横斜め)に隣り合うものの和の最大値を求めよ. (連続して足す領域は 3 マス以上でもよい, 斜め 4 マス等も認める)
テキスト整形のルールを表示する
![[PukiWiki]](pukiwiki.png "[PukiWiki]")
