08/02/08 16:24:10
>>65
アッカーマン関数は、ack(3, 12)の段階で呼び出し回数が7億を越えるからシンプルな実装じゃその所要時間は無理でしょ。
>54に書かれている、キャッシュする配列を用意する方法でも呼び出し回数は大して減らないから(ハンドリングコストの所為で)遅くなるし。
# フィボナッチ数の場合は、キャッシュすると爆速だけど。
ということで、手元の所要時間を。
./ackCache 3 7
ack(3, 7):1021
0.01sec
./ackCache 3 8
ack(3, 8):2045
0.04sec
./ackSimple 3 12
ack(3, 12):32765
2.29sec
./ackCache 3 12
ack(3, 12):32765
10.52sec
# あー気にいらね