id:Nabetani:20041014:p1 の続き。
四則演算と n 個の変数で作れる式の数を数えるという問題。
もちろん、a+b-c+d と b-(c-a)+d は同じ式と見なす。
a/(b/c)+d と ac/b+d は、c=0 の時に計算できるかどうかという点で異なる式ではあるが、同じ式と見なすというルールにする。
ついでに、単項マイナス演算子の扱いが面倒なので、-a-b-c-d と a+b+c+d も同じ式と見なす。
で。
以前書いたプログラムは非常に効率が悪かったし、いい加減なプログラムだったので、n=5 の計算も困難だった。
真面目に数えるようなプログラムを書いたら、
- n=1 : 1 (0秒)
- n=2 : 5 (0秒)
- n=3 : 47 (0.06秒)
- n=4 : 733 (1.6秒)
- n=5 : 15907 (155秒)
となった。()内は、計算時間。処理系は、ruby。あまり高速化を考慮してないが、真面目ではある。
ちなみに、5, 47, 733, 15907 は全て素数。
n=6 は、四十万〜六十万ぐらいか。このままだと、計算時間は数日を要するにちがいない。まだまだ高速化の余地はあるので、もうちょっと考えてからトライしてみようか。
