-1

可能不需要太多解释这是什么，它甚至完全按照我想要的方式工作。我真正的问题是程序终止。我已经输出跟踪了我的返回值和我在我的主函数中使用的嵌套 for 循环来单步执行值。我看不出发生这种情况的原因，但是在最后一次通过我的循环后，程序需要多花 10 分钟才能真正终止。尽管我的循环索引正在增加（因为预检查），但我的 Ackermann 函数显然没有执行额外的迭代（无论如何我都不想这样做）。另一方面，唯一合乎逻辑的解释是循环没有中断，但如果是这种情况，我的 Ackermann 函数应该返回一个新的 b 值。所以我能想到的唯一其他原因是它 s 需要很长时间的垃圾收集来清除我的数据结构并刷新内存堆。对于那些不熟悉的人，这里的想法是将传统上呈现为超级繁琐的递归函数的东西实现为迭代函数。递归：

给定正整数 m 和 n：如果 m = 0，则返回 n + 1；否则，如果 n = 0，则返回 Ackermann(m - 1, 1); 否则返回 Ackermann(m - 1, Ackermann(m, n - 1))。所以迭代地，这个想法是使用堆栈来模拟递归函数调用，这样您就可以使用堆中的内存并且您不依赖于调用堆栈大小，这会限制您的执行时间。我担心我忽略了我的流程中的某些东西，这会导致计算完成时间和我的程序到达用户干净退出的时间之间的这些长时间延迟。

这是我的代码：

 static void Main(string[] args)
    {
        ulong i, j;
        i = j = 0;
        for (i = 1; i <= 3; i++)
            for (j = 1; j <= 15; j++)
                Console.WriteLine("[{0}] Ackermann({1},{2}) = {3}", DateTime.Now, i, j, Ackermann(i, j));
        Console.WriteLine("Press any key to continue...");
        Console.ReadKey();
    }

    static ulong Ackermann(ulong a, ulong b)
    {
        Stack<ulong> ackStack = new Stack<ulong>();

        ackStack.Push(a);
        while (ackStack.Count > 0)
        {
            a = ackStack.Pop();
            if (a == 0)
                b++;
            else if (b == 0)
            {
                ackStack.Push(--a);
                b = 1;
            }
            else
            {
                ackStack.Push(--a);
                ackStack.Push(++a);
                b--;
            }
        }
        return b;
    }

想法？旁注，这是 c#，但这种行为也发生在使用 MinGW 编译的 C++ 中。

4

1 回答 1

0

非常感谢 Pieter Witvoet！事实证明，我的 Writeline 中的评估顺序是错误的。只有在改变它之后，它才变得明显增加了整个事情的整体运行时间！

于 2015-10-12T03:19:36.337 回答