円周率の山下り
______________ 3_________________
_____________ 1 4 ________________
____________ 1 5 9________________
____________2 6 5 3_______________
___________8 9 7 9 3______________
__________2 3 8 4 6 2_____________
_________ .............. _____________
(アンダーラインは俵積み状態に表現するための空白の代役で使っています。)
の様に円周率の数字が俵積み状態に配置されているとする。
頂上の3の数字から拾い始めて左斜め下かまたは右斜め下いずれかの数字を拾いながら
その拾った位置から同様にして段を降りて行くものとする。
全部で8と9と10段の山の場合
こうして最下段の所まで拾い集めた時のその拾った数字の和のそれぞれの最大値と最小値は？
ところで円周率は小数点以下762位から9が連続して6個並ぶというファインマンポイント
が存在している。
そこでその並びが最下段に並んでいるように山の高さを39段（1+2+3+･･･+39=780)
と俵積み状態にしている場合の山では,はてその時の最大値と最小値は？
なお最下段は
4,7,7,1,3,0,9,9,6,0,5,1,8,7,0,7,2,1,1,3,4,9,9,9,9,9,9,8,3,7,2,9,7,8,0,4,9,9,5 の並びです。
コンピュータで挑戦しているんだが全部で2^38=274877906944通りのコースがあるので
通常の検索プログラムでは3日間計算させ続けていますが歯が立ちません。
何かしらバックトラック法とかダイクストラ法などの手法がありそうとは本では紹介
されていますが、如何せんこれらを使いこなす知識も技も身に着けておりません。
何方かこの壁を越えられる方の挑戦をお願いします。
プログラムが正しければ、ですが
8段: 最小19、最大50
9段: 最小20、最大59
10段: 最小22、最大67
39段: 最小76、最大260
100段: 最小207、最大693
1000段: 最小2055、最大6964
10000段: 最小20334、最大69638
一段ずつ（全要素それぞれの）最小と最大を更新していくと早いです。
最初最大値,最小値の位置だけに着目すればいいのかと思ったのですが
6段から7段では
6段での最大値38だがここからは右斜め下だろうが左斜め下でも共に3が加わるしかなく
7段での合計は41である。
一方6段での和34である地点(3か所ある)の一つからは34+8,34+3という可能性があり前の41
を越えられる42が発生する。
従ってただ単に最大値がある位置から次の最大値が発生することにならない！（でも可能性は高い)
下に並ぶ数は円周率のある意味ランダムな数字の列であるので、結局その次の和がどうなるかは
トータルで見るしかない様に思われました。
そこで
a(n)=floor(Pi*10^(n-1))-10*floor(Pi*10^(n-2)) //円周率の小数点以下第n位に現れる数字
f(k)=k*(k-1)/2+1
g(k)=k*(k+1)/2
を先に定義しておき
gp > L=List([3]);
gp > for(k=2,25, //ｋは俵積みの段を示す。
for(n=1,#L,listinsert(L,L[2*n-1],2*n-1)); //Lの配列を同じ数字を二度繰り返して並べる。
A=[];for(n=1,2^(k-1),A=concat(A,[hammingweight(2*n-1)])); //今いる位置からどちらのコースへ行くかの選択可能な並び。
V=[];for(n=f(k),g(k),V=concat(V,[a(n)])); //次の段に降りたときの具体的数（πの小数点以下の数の並び。)
V=vecextract(V,A); //コースの方向に対応するπの小数部分の数字に置き換える。
L=List(Vec(L)+V); //各2つのコースを辿ったときに元からの数字とのの和状態を並べたもの。次のステップでの和での配列となる。
print(k";"vecmin(Vec(L))" VS "vecmax(Vec(L)))) //並んだすべての和の候補での最小、最大を見つける。
2;4 VS 7
3;5 VS 16
4;7 VS 21
5;12 VS 30
6;14 VS 38
7;17 VS 42
8;19 VS 50
9;20 VS 59
10;22 VS 67
11;26 VS 76
12;26 VS 84
13;28 VS 88
14;28 VS 97
15;30 VS 102
16;30 VS 111
17;34 VS 115
18;35 VS 119
19;39 VS 128
20;43 VS 137
21;45 VS 143
22;46 VS 148
23;49 VS 154
24;50 VS 160
25;50 VS 166
････････････
が並ぶが（ここまで3時間程度経過する。)
一段ごとに掛かる時間は倍々に膨れて行く。
益々この先の段での結果を得るまでには、莫大な時間が掛かる様子になってくる。
例え一段ごとの算出時間が一瞬でも指数関数的に増大していく見積もりで
39段、１00段、10000段などとんでもないことが予想できる。
これを
らすかるさんは一体どんな手を使えば、こんな膨大な時間を要する問題に対処されているのか？
なお別の行列を利用した個別のやり方では（行列への入力が自動化できなく手間がかかる)
20段；24秒程度
21段；53秒程度
22段；1分50秒程度
23段；4分４秒程度
24段；9分13秒程度
25段 ; 20分11秒程度
の経過なので、前のプログラムよりスピードアップしても、この先倍々となるとこれも本筋とは思えない。
1段目(3)
最小3、最大3
2段目(1,4)
端は単に足すしかないので
1番目は最小=最大=3+1=4
2番目は最小=最大=3+4=7
3段目(1,5,9)
1番目は最小=最大=4+1=5
2番目は
上の段の左側の最小は4、右側の最小は7で4の方が小さいので最小4+5=9
上の段の左側の最大は4、右側の最大は7で7の方が大きいので最大7+5=12
3番目は最小=最大=7+9=16
3段目までで
最小5,9,16
最大5,12,16
4段目(2,6,5,3)
1番目は最小=最大=5+2=7
2番目は
上の段の最小の5と9では5の方が小さいので最小は5+6=11
上の段の最大の5と12では12の方が大きいので最大は12+6=18
3番目は
上の段の最小の9と16では9の方が小さいので最小は9+5=14
上の段の最大の12と16では16の方が大きいので最大は16+5=21
4番目は最小=最大=16+3=19
4段目までで
最小7,11,14,19
最大7,18,21,19
同様に5段目は(5,8,9,7,9)なので最小と最大を更新して
最小12,15,20,21,28
最大12,26,30,28,28
6段目は(3,2,3,8,4,6)なので最小と最大を更新して
最小15,14,18,28,25,34
最大15,28,33,38,32,34
7段目は(2,6,4,3,3,8,3)なので最小と最大を更新して
最小17,20,18,21,28,33,37
最大17,34,37,41,41,42,37
8段目は(2,7,9,5,0,2,8,8)なので最小と最大を更新して
最小19,24,27,23,21,30,41,45
最大19,41,46,46,41,44,50,45
従って8段目までの最小と最大はそれぞれの中での最小、最大を調べることにより
最小は19、最大は50とわかります。
つまり一段処理するたびに「その要素までの経路の最小値と最大値」を
一段の要素数分覚えておいて更新していけば、
100段でも1000段でもあっという間に終わりますね。
遅くしていたのは円周率の配列をいちいち元のPiから計算で集めていたことと、
出来上がる和の方に着眼点が向かい過ぎていて、どうしても調査範囲が2倍、２倍と広がっていったと気付かされました。
次の段の円周率の数に対するそれぞれの最小、最大の可能性の方に視点を向けることでその段の個数分のデータだけで済むわけですね。
そこで円周率の小数点以下6000桁までをDでdigits化させて(1+2+3+･･･+100=5050まで小数点が伸びるので)
gp > P(n)=D[n*(n-1)/2..n*(n+1)/2-1]
の拾い取りで定義させると
gp > S1=[5,9,16]
gp > S2=[5,12,16]
gp > for(r=4,100,S11=vector(r,i,0);S11[1]=P(r)[1]+S1[1];\
for(k=2,r-1,S11[k]=min(S1[k-1],S1[k])+P(r)[k]);\
S11[r]=P(r)[r]+S1[r-1];\
S22=vector(r,i,0);S22[1]=P(r)[1]+S2[1];
for(k=2,r-1,S22[k]=max(S2[k-1],S2[k])+P(r)[k]);\
S22[r]=P(r)[r]+S2[r-1];\
print(r";"vecmin(S11) " VS "vecmax(S22));S1=S11;S2=S22)
2;4 VS 7
3;5 VS 16
-----------
4;7 VS 21
5;12 VS 30
6;14 VS 38
7;17 VS 42
8;19 VS 50
9;20 VS 59
10;22 VS 67
11;26 VS 76
12;26 VS 84
13;28 VS 88
14;28 VS 97
15;30 VS 102
16;30 VS 111
17;34 VS 115
18;35 VS 119
19;39 VS 128
20;43 VS 137
21;45 VS 143
22;46 VS 148
23;49 VS 154
24;50 VS 160
25;50 VS 166
26;52 VS 175
27;52 VS 176
28;53 VS 185
29;53 VS 190
30;53 VS 198
31;61 VS 205
32;61 VS 211
33;61 VS 220
34;63 VS 227
35;65 VS 234
36;70 VS 241
37;72 VS 245
38;72 VS 253
39;76 VS 260
40;77 VS 268
41;77 VS 276
42;80 VS 283
43;81 VS 291
44;83 VS 300
45;83 VS 303
46;83 VS 310
47;88 VS 315
48;89 VS 321
49;91 VS 328
50;94 VS 337
51;97 VS 342
52;98 VS 349
53;101 VS 358
54;105 VS 366
55;109 VS 372
56;111 VS 379
57;112 VS 383
58;116 VS 392
59;118 VS 400
60;120 VS 406
61;123 VS 413
62;126 VS 422
63;128 VS 428
64;128 VS 436
65;131 VS 444
66;135 VS 453
67;137 VS 460
68;139 VS 467
69;142 VS 473
70;146 VS 481
71;146 VS 486
72;150 VS 495
73;154 VS 501
74;157 VS 508
75;157 VS 516
76;157 VS 525
77;158 VS 534
78;159 VS 541
79;162 VS 550
80;166 VS 559
81;171 VS 565
82;172 VS 574
83;174 VS 579
84;176 VS 586
85;181 VS 592
86;183 VS 597
87;185 VS 605
88;186 VS 613
89;186 VS 619
90;190 VS 625
91;190 VS 634
92;194 VS 638
93;194 VS 645
94;198 VS 654
95;199 VS 658
96;199 VS 665
97;202 VS 674
98;204 VS 678
99;207 VS 687
100;207 VS 693
time = 47 ms.
ほんとにアッと言う間でした。
答えが一致して安心しました。
