πとeの道
円周率(π)と自然対数の底(e)を構成する数字をはじめから(3,1,4,1,5･･･,や 2,7,1,8,2･･･)100個の数を
10行10列に並べ(左上から右へ10個並べ、第２行をやはり左から右へ10個並べていくことを繰り返す。)
左上からスタートし右下をゴールとするコースについて進むものとし
途中では上、下、左、右へどこの方向にも進めて行けるものとする。
この時進むコースにある数字を拾って進むことにするとき、ゴールに
辿り着いた時に拾った数の合計数が最小になるのはどちらがより
小さいものになるでしょうか？
それぞれの最小合計数を見つけて下さい。
問題の解釈とプログラムが正しければ
πは
進み方: 右下下下右右下下右下右下右右下下右右
合計: 3+1+8+2+5+0+2+3+2+0+3+0+6+2+0+4+0+6+7=54
eは
進み方: 下右下右下右下下右下右右右下下右下右
合計: 2+4+5+0+2+6+2+0+7+4+7+2+4+0+4+2+1+2+7=61
のようになると思います。
しかし、せっかく「上下左右どの方向へも進める」という条件なのに
右と下しか出てきませんね。
100×100=10000桁にすると、「上」や「左」が出てきます。
（特に、πの場合は最小値となるために上も左も必要です。eは右と下だけでも最小値が得られます。）
また、10×10の場合は最小となる進み方は1通りずつしかありませんが、
100×100の場合は複数通りになります。
では、100×100の場合、π・eそれぞれについて、最小値はいくつで
最小となる経路の数はそれぞれいくつあるでしょうか？
πでの最小値430
e での最小値455
でしょうか？(先人のやり方を大いに参考にしてやってみましたが･･･自信はありません。)
なお何通りの行き方があるのかやコースがどの様に辿っているか知るためのプログラムは
今は手も足もでません。
よかったらπのコースでなるだけ上や左へのコースを辿るものがあれば教えて下さい。
430と455は正解です。πの経路は4608通り、eの経路は48通りです。
100×100のπはすべて「上」を2個含み、「左」は2個(768通り)・
3個(2304通り)・4個(1536通り)のいずれかです。
「左」を4個含むものは、例えば
右右右下右右右下右下右下下下下右下下下右右右下右右下右下右右
右上右右右右右右下下右右右下下右右右右右右右右右下下右下下左
下下右右右下下下下右下右右下右右下下下右右右右右下右右右右右
上右右右右下下下下下右右右下右下下右右右右右右下右右下右下下
右右右右下右右右下下右下右右右下下下下右下下下下右右下下下下
右下下右右右下右下下下下右下下左左下下右下下右右下右右下下下
左下下下下下右右右下下右下下右下右下下下下下下下下下下下下下
(追記)
図を作ってみましたが、ここでは粗くてよく見えませんので
精細な画像はこちらでどうぞ → http://www10.plala.or.jp/rascalhp/image/pi10000.gif
私もエクセルに数値を貼り付け、教えてもらったコースを塗り潰してコースを眺めていました。
ふと思ったのですが、このコースを見つける方法は最小値を求めるために利用していたπの数値と
対応させていた100×100行列のデータを逆から辿っていけば見つけられるかも？
(10×10の時はそうやってコースを手作業で見つけていた。)
でもプログラムの構成方法はまだ分かりませんが･･･
全部で4608通りのコースが存在できるとはおったまげ～です。
ちなみにもし進路を右と下だけに限定させて進めるとしたら最小値は442である。
は合っていますか？
> ふと思ったのですが、このコースを見つける方法は最小値を求めるために利用していたπの数値と
> 対応させていた100×100行列のデータを逆から辿っていけば見つけられるかも？
はい、そうですね。私のプログラムではそのようにしてコースを調べています。
やり方は人間が手作業でやるのと同じで、「このマスにはどこから来たか」を
4方向調べ、値が一致する方向に進んでそれを繰り返す、というのを再帰的に
処理すれば、自動的に何通りかもわかります。
既に通過した場所に再度行かないように、マップの大きさ分の「通過済みフラグ」も
必要です（それがないと0が二つ隣り合っているところで無限ループします）。
> もし進路を右と下だけに限定させて進めるとしたら最小値は442である。
> は合っていますか？
はい、確かに442でした。その場合の経路数は3456通りです。
