向大家请教一个计算循环次数的问题

cobranail

这是专业课笔试中的一道填空题：

1. 
   
2. fun(int n, int *s){
   
3.         int f1, f2;
   
4.         if( n==1 || n==2 )
   
5.                 *s=1;
   
6.         else{
   
7.                 fun( n-1, &f1 );
   
8.                 fun( n-2, &f2 );
   
9.                 *s=f1+f2;
   
10.         }
    
11. }
    
12. 
    
13. main(){
    
14.         int x;
    
15.         fun( 6 , &x );
    
16.         printf("%d\n",x);
    
17. }
    

复制代码

问程序的输出是多少。

在纸上模拟递归是可以做出来的，不过对于一个填空来说花费的时间太多了，有没有什么简便的方法来计算呢？


还有一个问题，

1. 
   
2. void sum(int n, int &s){
   
3.         int i,j,k;
   
4.         s=0;
   
5.         for(i=1;i<=n;i++)
   
6.                 for(i=1;i<=j;j++)
   
7.                         for(k=1;k<=j;k++)
   
8.                                 s=s+i*j*k;
   
9.        
   
10. }
    

复制代码

问，对s赋值了多少次，也是一个填空题。有什么好办法么？
数列求和是可以求的，问题也是时间花费太多。

langue

====

对于题目 1：实质是从数列的递推公式求它的同项公式。如从 “A_(n) = A_(n-1) * 2 且 A_1 = 2” 求得 “A_(n) = 2^n”，这样等于是把函数简化了。

====

cobranail

这样啊，我回去研究研究

langue

====

万分抱歉，“通项”，不是 “同项”



====

Edengundam

第一题不就Fibonacci数列嘛.........................................
第二题就高数极数吧...

tyc611

第一个：
f(1) = f(2) = 1;
f(n) = f(n-1) + f(n-2);
知道这是什么了吧

langue

====

不错。学习编程的时候，有点数学基础会受益无穷。

====

tyc611

第二个代码错了，应该是这样吧：

1. 
   
2. void sum(int n, int &s){
   
3.         int i,j,k;
   
4.         s=0;
   
5.         for(i=1;i<=n;i++)
   
6.                 for(j=1;j<=i;j++)
   
7.                         for(k=1;k<=j;k++)
   
8.                                 s=s+i*j*k;
   
9.         
   
10. }
    
11. 
    

复制代码

让你计算复杂度

Edengundam

第二题就这个解, 比高数极数容易多了...嘿嘿不用判敛...

1. 
   
2. 1 + (1/2) * (n*(n+1)*(2n+1)/6 + n*(n+1)/2)
   

复制代码

[ 本帖最后由 Edengundam 于 2007-1-18 19:38 编辑 ]

tyc611

原帖由 Edengundam 于 2007-1-18 19:36 发表
第二题就这个解, 比高数极数容易多了...嘿嘿不用判敛...

1. 
   
2. 1 + (1/2) * (n*(n+1)*(2n+1)/6 + n*(n+1)/2)
   

复制代码

其实这样写更清晰，又不是做数学题，呵呵