征求高效算法

shock_bn

大家好，我有如下题：
     已知：
         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(6, 4)

粗略想一下，感觉就是一个递归嘛，写个简单思路,但好像运行需要很长时间，望各位能写个高效算法，小弟先谢过：）
#include <stdio.h>
int func( int m , int n )
{
    if( 0 == m )
{
    return n+1;   //递归出口
}
   else
  {
      if ( 0 == n )
     {
        return func( m-1, 1 );
     }
  else
   {
    int b;
    b = func( m, n-1 );
    return func( m-1, b );
   }
  }
}

int  main()
{
    int a;
    a = func( 6, 4 );
    printf(“A( 6, 4 ) = %d ”, a );
    return 0;
}

shock_bn

这是某著名外资企业的笔试题目，上述算法会造成segment fault，即使改成long类型也不知道要运行到何年何月才出结果，所以恳请大家想个高效算法，不胜感激

ipaddr

按道理是这样写的，

我算了一下，
a(1,n)=n+2
a(2,n)=(n+1)*2+1
a(3,n)=a(3,n-1)*2+3

a(4,n)几乎就没法算了，
a(4,0)=13
a(4,1)=65533

更不用说a(5,n),a(6,n)了。

liubaochen

在A(0,n) {n| 0,1,2,3...} 是 A是1, 2,3,4....n+1的序列
在 A(1,n)  A是 an=2,3,...n+2的数列
在A(2,n) A是3,5,.....2(n+1)+1的数列
在A(3,n) A是5,13,... an=a(n-1)+8^(2^n-1); a0=5

*在A(4,n) 不知道了 但是A(4,0)=13,  
                                  A(4,1) = 65533 == A(3,13)
因为
a(m,n) = a(m-1,a(m-1,a(m-1,...a(m,0)...)
当m = 4, 时 a(4, n) = a(3,a(3,.....a(4,0)..)
当n = 2 时 a(4,2) = a(3,a(3,a(4,0))) = a(3,a(3,13))=a(3,65533);
已经太大了 double 都溢出

不知道对不对 请指正

我想最好有高手归纳出通式来

ipaddr

应该没公式的。

ipaddr

我写了一个函数，效率方面，肯定要比楼主的要高很多，但也没法解决问题，

先看看代码：

1. 
   
2. 
   
3. 
   
4. #include <stdio.h>
   
5. 
   
6. long a[10][300];
   
7. long count=0;
   
8. long func(long m,long n)
   
9. {
   
10. count++;
    
11. if (m==0)
    
12. {
    
13.         a[m][n]=n+1;
    
14.         return n+1;
    
15. }
    
16. else
    
17. {
    
18. if (n==0)
    
19. {
    
20.         if (a[m-1][1]>0)
    
21.         {
    
22.         return a[m-1][1];
    
23.         }
    
24.         else
    
25.         {
    
26.         a[m-1][1]=func(m-1,1);
    
27.         return a[m-1][1];
    
28.         }
    
29. }
    
30. else
    
31. {
    
32.         if (a[m][n-1]<0)
    
33.         {
    
34.         a[m][n-1]=func(m,n-1);
    
35.         }
    
36.         if (a[m-1][a[m][n-1]]>0)
    
37.         {
    
38.         return a[m-1][a[m][n-1]];
    
39.         }
    
40.         else
    
41.         {
    
42.         a[m-1][a[m][n-1]]=func(m-1,a[m][n-1]);
    
43.         return a[m-1][a[m][n-1]];
    
44.         }
    
45. }
    
46. }
    
47. }
    
48. 
    
49. int main()
    
50. {
    
51. long i,k;
    
52. for (i=0;i<11;i++)
    
53. for (k=0;k<301;k++)
    
54. {
    
55. a[i][k]=-1;
    
56. }
    
57. k=3;
    
58. i=5;
    
59. printf("A(%ld,%ld)=%ld \n",k,i,func(k,i));
    
60. printf("count:%ld\n",count);
    
61. return 0;
    
62. }
    
63. 
    
64. 
    
65. 
    
66. 
    

复制代码

ipaddr

上面算法的主要思想是用数组来存放计算过的A(m,n)，以免A(m,n)计算多次，

按这算法，比楼主写的效率要高很多，
比如计算A(3,4)，楼主的算法需递归４２４３８次，我的算法只需递归636次，

但这样仍不能解决问题。

shock_bn

嗯，好像用递归的方式不能解决问题了，多谢大家！

ipaddr

原帖由 shock_bn 于 2006-2-11 15:50 发表
嗯，好像用递归的方式不能解决问题了，多谢大家！

这问题，只有用递归了，

只是这算法有些变态罢了，a(4,1)就65533，那a(6,4)估计是个天文数字。

shock_bn

好，那我用long long试一下看看