标签: ackermann

我想知道是否可以有一个阿克曼函数的版本，其时间复杂度比标准变体更好。

这不是作业，我只是好奇。我知道阿克曼函数除了作为性能基准之外没有任何实际用途，因为它具有深度递归。我知道数字增长得非常快，而且我对计算它不感兴趣。

尽管我使用Python 3并且整数不会溢出，但我的时间确实有限，但我根据维基百科上的定义自己实现了它的一个版本，并计算了极小的值的输出，只是为了使确保输出正确。

def A(m, n):\n    if not m:\n        return n + 1\n    return A(m - 1, A(m, n - 1)) if n else A(m - 1, 1)\n

上面的代码是直接翻译图片，速度极慢，不知道如何优化，难道就不能优化了吗？

我能想到的一件事是记住它，但是递归是向后运行的，每次递归调用函数时，参数都是以前没有遇到过的，每次连续的函数调用参数都会减少而不是增加，因此函数的每个返回值都需要要计算，当您第一次使用不同的参数调用函数时，记忆并没有帮助。

仅当您再次使用相同的参数调用它时，记忆化才有帮助，它不会计算结果，而是检索缓存的结果，但如果您使用 (m, n) >= (4, 2 ）无论如何它都会使解释器崩溃。

我还根据这个答案实现了另一个版本：

def ack(x, y):\n    for i in range(x, 0, -1):\n        y = ack(i, y - 1) if y else 1\n    return y + 1\n

但实际上它更慢：

In [2]: …

我想计算A(3, 20)应该2^23 - 3 = 8388605使用的Ackermann函数(见维基百科)的值Data.MemoCombinators.我的代码是:

{-# LANGUAGE BangPatterns #-}
import      Data.MemoCombinators as Memo

ack = Memo.memo2 Memo.integral Memo.integral ack'
    where
        ack' 0 !n = n+1
        ack' !m 0 = ack (m-1) 1
        ack' !m !n = ack (m-1) $! (ack m (n-1))

main = print $ ack 3 20

但它最终会出现堆栈溢出错误;-)是否可以进行调整或计算链真的那么长,即使是memoization也无济于事？

我试图在Coq中定义Ackermann-Peters函数,我收到一条我不明白的错误消息.正如你所看到的,我把a, bAckermann 的论据打包成一对ab; 我提供了一个定义参数的排序函数的排序.然后我使用Function表单来定义Ackermann本身,为它提供ab参数的排序函数.

Require Import Recdef.    
Definition ack_ordering (ab1 ab2 : nat * nat) :=
    match (ab1, ab2) with
    |((a1, b1), (a2, b2)) => 
       (a1 > a2) \/ ((a1 = a2) /\ (b1 > b2))   
    end.
Function ack (ab : nat * nat) {wf ack_ordering} : nat :=
match ab with
| (0, b) => b + 1
| (a, 0) => ack (a-1, 1)
| (a, b) => ack (a-1, …

任何人都能直接解释为什么Ackermann函数http://en.wikipedia.org/wiki/Ackermann_function与用于不相交集的联合查找算法的摊销复杂性有关http://en.wikipedia.org/ wiki/Disjoint-set_data_structure？

Tarjan的数据结构书中的分析不是很直观.

我也在算法入门中查了一下,但它看起来也太严格且不直观.

谢谢你的帮助!

我读过 Grossman 和 Zeitman 发表的论文《阿克曼函数的本质迭代计算》，其中提出了一种优化阿克曼函数的算法。

我们知道阿克曼函数产生子序列 A(m,n) 的结果

\n

m=0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,... \
n m=1: 2, 3 , 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,...
\n m=2: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33,...
\n m=3: 5, 13, 29, 61, 125, 253, 509, 1021, …

我正在尝试在haskell中编写一个hyperoperation函数.

它通常是写的,ackermann(a,b,n)但对于部分应用目的,我认为n放在第一位更有意义.因此,我称之为hypOp n a b

我发现最自然的形式折叠ao replicate列表如下:

Prelude> replicate 3 5
[5,5,5]
Prelude> foldr1 (*) $ replicate 3 5
125

根据折叠的函数参数,这可以是加法,多重,取幂,四元组等.

非正式概述:

hypOp 0 a _ = succ a
hypOp 1 a b = a + b = foldr1 (succ a) (replicate b a) --OFF BY ONE ISSUES, TYPE ISSUES
hypOp 2 a b = a * b = foldr1 (+) $ replicate b a
hypOp 3 a b = a ^ b = …

有人知道用big-O表示法计算ackermann函数ack(m,n)的时间复杂度或者它属于哪个复杂类？Just Ack(3,n)也足够了.我在哪里读到它是无关紧要的？

谢谢.

代码片段:

public class Ackermann {

    public static int ackermann(int n, int m) {

        if (n == 0)
            return m + 1;
        else if (m == 0)
            return ackermann(n - 1, 1);
        else
            return ackermann(n - 1, ackermann(n, m - 1));
    }

}

这是7个月前的一个老问题,当时堆栈溢出器同意Haskell计算Ackermann函数的低效率是由于编译器错误造成的.

Ackermann与Haskell/GHC的效率非常低

7个月后,这似乎是固定的.似乎ack使用线性内存运行,但它运行速度非常慢.

main = print (ack 4 1)
-- Ackermann function
ack 0 n = n + 1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n - 1))

$ time ./ack
65533

>real   8m53.274s
>user   8m47.313s
>sys    0m4.868s


Processor  2.8 GHz Intel Core i7
Memory  8 GB 1333 MHz DDR3
Software  Mac OS X Lion 10.7.5 (11G63)

我只是要求对此有任何见解.更详细的将得到投票.请记住,我是函数式编程的新手,甚至关于尾递归与常规递归的简单评论也会受到赞赏和赞成.

在我的Ackermann功能的家庭工作中,我已经解决了以下问题

int main()
{
    int y = ack(4,1);
    cout<<"ans is :::: "<< y;

    getch();
    return 0;
}

int ack(int m, int n)
{
    if(m == 0)
    {
        return n+1; 
    }
    else if(m > 0 && n == 0)
    {
        return ack(m-1,1);  
    }
    else if(m > 0 && n>0)
    {
        int x = ack(m,n-1);
        return ack(m-1,x);
    }
    else 
    {
        cout<< "did not worked properly";
    }   
}

这个函数适用于低于m = 3和n = 10的低值但是当我给出m = 4 /更高或n = 15 /更高时,这不起作用.我没有出局.程序退出时没有任何警告或错误或结果.

请一些人告诉我这种情况发生的原因以及如何解决这个问题.

我尝试编写此代码来计算Ackerman值以及该函数被调用的次数。但是，计数器始终保持为0。你能帮我吗？

/*
A(m,n) =    n+1, if m==0
A(m,n) =    A(m-1,1), if m>0 and n==0
A(m,n) =    A(m-1,A(m,n-1)), if m>0 and n>0
*/
#include<stdio.h>
static int w=0;
int ackerman(int m,int n)
{

    w=w+1;
    if(m==0)
        return n+1;
    else if(m>0 && n==0)
        return ackerman(m-1,1);
    else if(m>0 && n>0)
        return ackerman(m-1,ackerman(m,n-1));
}
int mainackerman()
{
    int m,n;
    scanf("%d %d",&m,&n);
    printf("%d %d",ackerman(m,n),w);
    return 0;
}