アッカーマン関数続

インデックスを一つの構造体で管理するようにしてすっきりした。

struct index2D
{
    public int m, n;
    public override int GetHashCode()
    {
        return m ^ n;
    }
}
static Dictionary<index2D, int> Ack = new Dictionary<index2D, int>();
static int Ackermann(index2D mn)
{
    System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
    watch.Start();
    Stack<index2D> arg = new Stack<index2D>();
    arg.Clear();
    arg.Push(mn);
    while (arg.Count > 0) {
        index2D index = arg.Peek();
        index2D index_;
        if (Ack.ContainsKey(index)) {
            arg.Pop();
            continue;
        } else {
            int value;
            if (index.m == 0) {
                value = checked(arg.Peek().n + 1);
            } else if (index.n == 0) {
                index_.m = index.m - 1;
                index_.n = 1;
                if (Ack.ContainsKey(index_)) {
                    value = Ack[index_];
                } else {
                    arg.Push(index_);
                    continue;
                }
            } else {
                index_.m = index.m;
                index_.n = index.n - 1;
                int n_;
                if (Ack.ContainsKey(index_)) {
                    n_ = Ack[index_];
                } else {
                    arg.Push(index_);
                    continue;
                }
                index_.m = index.m - 1;
                index_.n = n_;
                if (Ack.ContainsKey(index_)) {
                    value = Ack[index_];
                } else {
                    arg.Push(index_);
                    continue;
                 }
            }
            Ack[index] = value;
            continue;
        }
    }
    watch.Stop();
    Console.WriteLine(watch.Elapsed.ToString() + " elapsed.");
    return Ack[mn];
}

いてー

今日も朝から疲労倦怠感、風邪気味の倦怠感、風邪気味の症状、微熱、どれも強かったのだけど、数日休んでばかりだったからか肉体的な疲労はそんなに強くなかった。それで午後から出かけて、いつも通り死にそうになって帰ってきた。でもその時点でも肉体的疲労は強くなくて、「脳の疲労」とでも言うべき一連の症状が強くなっただけだったのだが、夕食と風呂で負荷がかかった後、足がめちゃくちゃ筋肉痛。まじで痛え。

アッカーマン関数

2chのC#初心者スレに投稿したアッカーマン関数を計算するC#メソッド。
あからさまに宿題くさかったが、ジェネリッククラスのスタックを使って再帰をヒープで行う方法が提案されるなど、興味深かったので。

方針は、ハッシュを使って計算済みの値を保存し再利用する事で無駄な再帰を減らす事と、上記のヒープを使っての自前再帰。計算済みの値を再利用するので表作成にも有効。うちの環境(メモリ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 int Ackermann(int m, int n)
{
    Stack<int> argM = new Stack<int>();
    Stack<int> argN = new Stack<int>();
    argM.Push(m);
    argN.Push(n);
    while (argM.Count>0) {
        if (!Ack.ContainsKey(argM.Peek())) Ack[argM.Peek()] = new Dictionary<int, int>();
        if (Ack[argM.Peek()].ContainsKey(argN.Peek())) {
            argM.Pop();
            argN.Pop();
            continue;
        } else {
            int value;
            if (argM.Peek() == 0) {
                value = checked(argN.Peek() + 1);
            } else if (argN.Peek() == 0) {
                if (Ack.ContainsKey(argM.Peek() - 1) && Ack[argM.Peek() - 1].ContainsKey(1)) {
                    value = Ack[argM.Peek() - 1][1];
                } else {
                    argM.Push(argM.Peek() - 1);
                    argN.Push(1);
                    continue;
                }
            } else {
                int n_;
                if (Ack.ContainsKey(argM.Peek()) && Ack[argM.Peek()].ContainsKey(argN.Peek() - 1)) {
                    n_ = Ack[argM.Peek()][argN.Peek() - 1];
                } else {
                    argM.Push(argM.Peek());
                    argN.Push(argN.Peek() - 1);
                    continue;
                }
                if (Ack.ContainsKey(argM.Peek() - 1) && Ack[argM.Peek() - 1].ContainsKey(n_)) {
                    value = Ack[argM.Peek() - 1][ n_];
                } else {
                    argM.Push(argM.Peek() - 1);
                    argN.Push(n_);
                    continue;
                }
            }
            Ack[argM.Pop()][argN.Pop()] = value;
            continue;
        }
    }
    return Ack[m][n];
}