阿克曼函数
2020-12-21 00:11:35    5    0    0
starryoo

这个问题真没想到,没留意M最大只有3,也完全没有想到用公式啥的,当时没往这方面想,直接按递归公式写的算法,结果狠狠的巴掌:超时了。。。。


问题描述
众所周知,阿克曼函数中扮演一个重要的角色在理论计算机科学领域。然而,在另一方面,戏剧性的快速增长速度引起的功能很难calcuate阿克曼的价值功能。

阿克曼函数可以递归地定义如下:


现在艾迪给你两个数字:m和n,你的任务是计算的价值(m,n)。这是如此简单的问题,如果你解决这个问题,你将收到一个奖(艾迪将邀请你,6餐厅吃晚饭)。
 


输入
的每一行输入两个整数,即m,n,0 < m < = 3。
注意,当m < 3,n可以是任意整数不到1000000,而m = 3,n的值限制在24。
输入终止结束的文件。
 


输出
为每个值m,n,打印出的价值(m,n)。
 


样例输入
1 3
2 4
 


样例输出
5
11
 

下面是超时的代码:

 

 

[cpp] view plain copy
 
  1. int fun(int m, int n)  
    {  
        if(m==0)  
        return n+1;  
        if(m>0 && n == 0)  
        {  
            fun(m-1,1);  
        }  
        if (m>0 && n>0)  
        {  
            fun(m-1,fun(m,n-1));  
            if (m==3)  
            {  
                if(n>24)  
                n=24;  
            }  
        }  
    }  
    

 


 

M最大是3 所以可以直接把m=1,2,3
的公式推出来,推导m=1时要结合m=0时推
推导m=2时用m=1时 同理可得到
m=0    n+1;
m=1    n+2;
m=2   2*n+3
m=3   dp[3][i]=2*dp[3][i-1]+3;


 

 

[cpp] view plain copy
 

#include<stdio.h>  
long int A(long int,long int);  
main()  
{  
    long int n,m;  
    while(scanf("%ld%ld",&m,&n)!=EOF)  
        printf("%ld\n",A(m,n));  
}  
long int A(long int m,long int n)  
{  
    if(n==0) return A(m-1,1);  
    else if(m==0)return n+2;  
    else if(m==1) return n+2;  
    else if(m==2) return 2*n+3;  
    else  if(m==3)return A(m,n-1)*2+3;<pre name="code" class="cpp">       //else if(m==3) return (1<<n+3)-3;  

}


上一篇: kruskal

下一篇: 蚯蚓题解

5 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航