09/03/04 18:56:15
みんなー、アッカーマン関数の話しようぜー。
>>174のコードだと、m=0, n=int.MaxValue-1みたいなケースが計算できない
のが嫌だ。ていうかそもそもの問題は多分アッカーマン関数の表を一気に計算する
コードじゃなくって、与えられたm,nに対してアッカーマン関数の値を計算するコード。
なので、>>187のスタック使ってヒープを使って再帰する方法と、ハッシュ使って
計算済みの値を再利用する方法を組み合わせたアプローチにしてみた。値を再利用
するので、表を生成する用途でも有効。
うちの環境(メモリ1GB)では
m=0でn=int.MaxValue-1まで
m=1でn=10000000くらいまで
m=2でn=5000000くらいまで
m=3でn=20まで
m=4でn=1まで
計算できた。
スレの空気読まずにコードアップするぜ！
static Dictionary<int, Dictionary<int, int>> Ack
= new Dictionary<int Dictionary<int, int>>();
static Stack<int> argM = new Stack<int>();
static Stack<int> argN = new Stack<int>();
static int Ackermann(int m, int n)
{
argM.Clear();
argN.Clear();
argM.Push(m);
argN.Push(n);
while (argM.Count>0) {