2002-06-07 [長年日記]
SuperCON2002
スーパーコンピュータコンテストの予選問題の考察。の前に、去年のプログラムは見事に間違っていた。ごめんなさい。
ということで今回はリベンジなのである。リベンジという言葉も廃れてしまった感はあるが。問題についてはここを参照していただきたい。みていただければ分かると思うが、問題としては非常に簡単である。ということでいきなりプログラム。
f(n,m)=f(n-1,m+1)+f(n-2,m+2)/2というふうに再帰的に定義されている為、素直に再起呼び出しを行っている。しかし、nの数が増えると計算数が(まさに)鼠算式に増えていくのでとてもじゃないが実用的ではない。PentiumIII700MHzでは、f(35,35)までは数秒で計算できるが、f(70,70)では数分経っても終らなかった。
ここで最初に立ち戻って、この計算の性質について考えてみる。例として、f(35,35)を用いることにしよう(nとかmとか記号で考えるのが苦手なのだ)。上記の式にあてはめると以下のようになる。
f(35,35)=f(34,36)+f(33,37)/2={f(33,37)+f(32,38)}+{f(32,38)+f(31,38)/2}/2=.......
と人間にとっては無限とも思えるほど続くのだが、最近のパソコンだとこれが数秒で終ってしまうのだ。すごいなぁ。とそういう話ではない。まず各々の関数の引数に注目していただきたい。すべて35+35=70になっている。式の定義から言えばあたりまえだが。これを最後まで展開するとどうなるかというと、f(0,70)もしくはf(1,69)にそれぞれ係数がかかったものが沢山(そりゃもう嫌になるほど沢山)並んでいるはずである。ここまできてようやくfを数字に変換することができるのだが、なんとまぁf(0,70)=f(1,69)=70となり、f(0,70)だろうがf(1,69)だろうが関係ないことが分かる。これを一般的な表記で表すとこうなる。f(n,m)=x(n+m)(但しxは適当な係数)。ここまでくれば何とかなりそうだ。
次に、任意のn,mについて考える。以下f(n,m)をFn、f(0,m+n)をF0と表すことにする。このとき、F0,F1について考えると、
F0=f(0,m+n)=m+n
F1=f(1,m+n-1)=m+n
となり、先ほどの考察とも一致している。どんどん行こう。
F2=f(2,m+n-2)=f(1,m+n-1)+f(0,m+n)/2=(m+n)+(m+n)/2=3(m+n)/2
F3=f(3,m+n-3)=f(2,m+n-2)+f(1,m+n-1)/2=3(m+n)/2+(m+n)/2=2(n+m)
これがFnまで続くわけだが、これくらい書けばもういいだろう。ようはfor文書けばどうにかなるのである(投げ遣り)。ということでプログラム。ポイントとしては2個前の答えが必要となるので、buf[2]でバッファリングしているところ。f(35,35)について先ほどのプログラムと答え合わせしたので間違ってはいないと思うのだけど。というかこんな簡単なプログラムでいいのか？