征求高效算法

ipaddr

你的算法肯定能得到结果，

即使不考虑溢出的话，计算a(6,4)也需要很长很长很长时间的。

所以，这主要是题目问题。题目比较变态。！！！

shock_bn

我用一直漂写的方法算出结果是61，不知道对不对，哈哈，谢谢斑竹

ipaddr

原帖由 shock_bn 于 2006-2-11 16:23 发表
我用一直漂写的方法算出结果是61，不知道对不对，哈哈，谢谢斑竹

肯定不对。

我那算法，最大能算A(3,5)，因为数组只定义了a[10][200]，如果a(m,n)大于２００的话，我那算法肯定有问题，

但速度，比直接用递归要快很多很多。

richardhesidu

我觉得有点像微分方程的初值问题。或许可以先求通解，再编程。

ipaddr

原帖由 richardhesidu 于 2006-2-11 21:45 发表
我觉得有点像微分方程的初值问题。或许可以先求通解，再编程。

没有通解,

m=1,2,3,4,5时,通解都不一样的,

为6时,m(6,1)我估计都是一个超级大的数了.

yzc2002

A(4,n)=2^2^...^2(n+3层)-3
A(5,0)=A(4,1)=65533
A(6,0)=A(5,1)=A(4,A(5,0))=A(4,65533)=2^2^2...^2(65536层)-3
这个数有多大?估计如果用10进制表示,在屏幕上输出的话,到太阳灭亡还没输完...更不用说A(6,4)了
记得在一本书上看到过,说人类只能认识到5层以内,6层以上,别指望了.

ArXoR

阿克曼函数
是本质递归的,没有办法转成非递归形式

liubaochen

前面我写了 m为3以前的通式
下面是临时写的程序只计算 A(3,n) 已知A(3,0)=5 ==A(2,1) A(2,n)可另写程序.

#include <stdio.h>
double m3x = 0.0;
int main(int argc, char *argv[])
{
        int m, n, i,tmp;
        m = atoi(argv[1]);
        n= tmp = atoi(argv[2]);
        int s = 8;
        int m30 = 5;

        m3x = m30;
        double subs = s;
        if ( --n >= 0)
        {
                m3x = m3x +subs;
        }

       
        for ( ; n > 0; n-- )
        {
                subs *= 2;
                m3x = m3x + subs;
        }

        printf("A(%d,%d)=%f\n",m,tmp,m3x);
        return 0;
}

gcc 3.4.2 通过

zhpzh

#include <stdio.h>
#include <stdlib.h>

int A( int m , int n )
{
        int  rst;

        if(m < 0 || n < 0)
        {
                rst = -1;
        }else
        {
               
                if(0 == m)
                {
                        rst = n+1;
                }else
                {
                        if(0 == n)
                                rst = A(m-1, 1);
                        else
                                rst = A(m-1, A(m, n-1));
                }
        }

        return rst;
}

void main(int argc, char *argv[])
{
        int m, n, result;
        m = atoi(argv[1]);
        n = atoi(argv[2]);
       
        printf("已知：\n");
        printf("\tA(m, n) = n + 1                      当 m = 0 时  \n");
        printf("\tA(m, n) = A(m – 1, 1)               当 m ! = 0 且 n = 0 时 \n");
        printf("\tA(m, n) = A(m – 1, A(m, n - 1))     当 m ! = 0 且 n ! = 0 时 \n");
        printf("编程求解： A(m, n).\n");

        result = A(m, n);
    if(-1 == result)
                printf("Invalid arguments!\n");
        else
                printf("\n答：\n\t A(%d,%d) = %d\n", m, n, result);

        return;
}


假设上面程序名为 test .

>>> 执行：

D:\>test 3 9

>>> 输出：

已知：
        A(m, n) = n + 1                      当 m = 0 时
        A(m, n) = A(m – 1, 1)               当 m ! = 0 且 n = 0 时
        A(m, n) = A(m – 1, A(m, n - 1))     当 m ! = 0 且 n ! = 0 时
编程求解： A(m, n).

答：
         A(3,9) = 4093

>>> 当执行：
D:\>test 6  4

>>> 结果：堆栈溢出！

[ 本帖最后由 zhpzh 于 2006-2-18 15:52 编辑 ]