5

有没有办法让我的 Ackerman 函数不创建堆栈溢出是针对相对较小的数字,即 (4,2)。这是错误

{无法计算表达式,因为当前线程处于堆栈溢出状态。}

private void  Button1Click(object sender, EventArgs e)
        {
            var t = Ackermann(4,2);
            label1.Text += string.Format(": {0}", t);
            label1.Visible = true;
        }

        int Ackermann(uint m, uint n)
        {
            if (m == 0)
                return  (int) (n+1);
            if (m > 0 && n == 0)
                return Ackermann(m - 1, 1);
            if (m > 0 && n > 0)
                return Ackermann(m - 1, (uint)Ackermann(m, n - 1));
            else
            {
                return -1;
            }
        }
4

2 回答 2

26

避免的最好方法StackOverflowException是不使用堆栈。

让我们摆脱否定的情况,因为当我们调用时它是没有意义的uint。或者,如果我们将否定测试作为方法中的第一件事,在考虑其他可能性之前,下面的内容也将起作用:

首先,我们需要一艘更大的船:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        if (m == 0)
            return  n+1;
        if (n == 0)
            return Ackermann(m - 1, 1);
        else
            return Ackermann(m - 1, Ackermann(m, n - 1));
    }

现在成功至少在数学上是可能的。现在,这个n == 0案例是一个足够简单的尾声。让我们手动消除它。我们将使用goto它,因为它是临时的,所以我们不必担心 velociraptors 或 Dijkstra:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
    restart:
        if (m == 0)
            return  n+1;
        if (n == 0)
        {
            m--;
            n = 1;
            goto restart;
        }
        else
            return Ackermann(m - 1, Ackermann(m, n - 1));
    }

这已经需要更长的时间来炸毁堆栈,但是炸毁它,它会的。不过看看这个表格,请注意,m递归调用的返回永远不会设置它,而n有时是。

扩展它,我们可以把它变成一个迭代形式,同时只需要处理跟踪以前的值m,并且我们将以递归形式返回的地方,我们以n迭代形式分配给。一旦我们用完m等待处理的 s,我们就返回 的当前值n

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
            if(m == 0)
                n = n + 1;
            else if(n == 0)
            {
                stack.Push(m - 1);
                n = 1;
            }
            else
            {
                stack.Push(m - 1);
                stack.Push(m);
                --n;
            }
        }
        return n;
    }

至此,我们已经回答了OP的问题。这将需要很长时间才能运行,但它会返回尝试过的值(m = 4,n = 2)。它永远不会抛出 a ,尽管它最终会在超过andStackOverflowException的某些值时耗尽内存。mn

作为进一步的优化,我们可以跳过向堆栈添加一个值,只是在之后立即弹出它:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
        skipStack:
            if(m == 0)
                n = n + 1;
            else if(n == 0)
            {
                --m;
                n = 1;
                goto skipStack;
            }
            else
            {
                stack.Push(m - 1);
                --n;
                goto skipStack;
            }
        }
        return n;
    }

这对堆栈没有帮助,对堆也没有任何意义,但考虑到循环的数量,这个东西会对大值进行,我们可以剃掉的每一点都是值得的。

在保持优化的同时消除goto,留给读者练习:)

顺便说一句,我对这个测试太不耐烦了,所以我做了一个作弊表格,当 m 小于 3 时使用 Ackerman 函数的已知属性:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
        skipStack:
            if(m == 0)
                n = n + 1;
            else if(m == 1)
                n = n + 2;
            else if(m == 2)
                n = n * 2 + 3;
            else if(n == 0)
            {
                --m;
                n = 1;
                goto skipStack;
            }
            else
            {
                stack.Push(m - 1);
                --n;
                goto skipStack;
            }
        }
        return n;
    }

使用这个版本,我可以在一秒多后得到truefor的结果Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3(Mono,Release build,在 Core i7 上运行)。鉴于非作弊版本在返回此类 值的正确结果方面是一致的m,我将此视为先前版本正确性的合理证据,但我将让它运行并查看。

编辑:当然,我真的不希望以前的版本在任何合理的时间范围内返回,但我想我还是让它继续运行,看看它的内存使用情况如何。6 小时后,它的大小正好低于 40MiB。我很高兴虽然显然不切实际,但如果在真机上有足够的时间,它确实会返回。

编辑:显然有人认为Stack<T>达到其 2³¹ 项目的内部限制也算作一种“堆栈溢出”。如果必须,我们也可以处理:

public class OverflowlessStack <T>
{
    internal sealed class SinglyLinkedNode
    {
        //Larger the better, but we want to be low enough
        //to demonstrate the case where we overflow a node
        //and hence create another.
        private const int ArraySize = 2048;
        T [] _array;
        int _size;
        public SinglyLinkedNode Next;
        public SinglyLinkedNode()
        {
            _array = new T[ArraySize];
        }
        public bool IsEmpty{ get{return _size == 0;} }
        public SinglyLinkedNode Push(T item)
        {
            if(_size == ArraySize - 1)
            {
                SinglyLinkedNode n = new SinglyLinkedNode();
                n.Next = this;
                n.Push(item);
                return n;
            }
            _array [_size++] = item;
            return this;
        }
        public T Pop()
        {
            return _array[--_size];
        }
    }
    private SinglyLinkedNode _head = new SinglyLinkedNode();

    public T Pop ()
    {
        T ret = _head.Pop();
        if(_head.IsEmpty && _head.Next != null)
            _head = _head.Next;
        return ret;
    }
    public void Push (T item)
    {
        _head = _head.Push(item);
    }
    public bool IsEmpty
    {
        get { return _head.Next == null && _head.IsEmpty; }
    }
}
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
    var stack = new OverflowlessStack<BigInteger>();
    stack.Push(m);
    while(!stack.IsEmpty)
    {
        m = stack.Pop();
    skipStack:
        if(m == 0)
            n = n + 1;
        else if(m == 1)
            n = n + 2;
        else if(m == 2)
            n = n * 2 + 3;
        else if(n == 0)
        {
            --m;
            n = 1;
            goto skipStack;
        }
        else
        {
            stack.Push(m - 1);
            --n;
            goto skipStack;
        }
    }
    return n;
}

同样,调用Ackermann(4, 2)返回:

在此处输入图像描述

这是正确的结果。使用的堆栈结构永远不会抛出,因此唯一剩下的限制是堆(当然还有时间,如果输入足够大,您将不得不使用“宇宙寿命”作为衡量单位......)。

由于它的使用方式类似于图灵机的磁带,我们想起了任何可计算函数都可以在足够大小的图灵机上计算的论点。

于 2012-08-30T00:27:50.553 回答
1

使用记忆。就像是:

private static Dictionary<int, int> a = new Dictionary<int, int>();

private static int Pack(int m, int n) {
 return m * 1000 + n;
}

private static int Ackermann(int m, int n) {
  int x;
  if (!a.TryGetValue(Pack(m, n), out x)) {
    if (m == 0) {
      x = n + 1;
    } else if (m > 0 && n == 0) {
      x = Ackermann(m - 1, 1);
    } else if (m > 0 && n > 0) {
      x = Ackermann(m - 1, Ackermann(m, n - 1));
    } else {
      x = -1;
    }
    a[Pack(m, n)] = x;
  }
  return x;
}

然而,这个例子只展示了这个概念,它仍然不会为 Ackermann(4, 2) 给出正确的结果,因为它int太小而无法容纳结果。为此,您需要一个 65536 位而不是 32 位的整数。

于 2012-08-29T21:41:41.590 回答