求助一个用堆栈来模拟fibr递归函数实现

feiyang21687

>> 7,3,1,2,1,1,4,2,1,1,2,1,1
这个是怎么得来的？

这个序列就是递归调用时候堆栈里面的存储数据的顺序，我是通过把递归式展开得到的这个序列。这个序列可以用一棵二叉树来描述。
PS.你也是北邮的吗？

cobras

修正LZ递推式f(n)=f(n/2)+f((n+1)/2)+n,f(1)=1

tyc611

原帖由 cobras 于 2007-2-4 11:18 发表
修正LZ递推式f(n)=f(n/2)+f((n+1)/2)+n,f(1)=1

楼主的递推式是正确的

原本的式子是要计算f( more(n/2) ) + f( less(n/2) ) + n，其中more(n/2)表示不大于n/2的最大的整数，less(n/2)表示大于n/2最小的整数

例如：
当 n = 2 时，more(n/2) = more(2/2) = 1, less(n/2) = less(2/2) = 2，所以 f(2) = f(1) + f(2) + 2 （无限递归）
而你的递推式有：f(2) = f(1) + f(1) + 2，所以你的是不正确
（注意：上面递推式中n/2作了向下取整计算）

另外，按照楼主的要求，必须给定 f(1) 和 f(2) 的初值才行

more(n/2) <= n/2 <less(n/2)，more和less相差1

tyc611

原帖由 feiyang21687 于 2007-2-4 11:15 发表

这个序列就是递归调用时候堆栈里面的存储数据的顺序，我是通过把递归式展开得到的这个序列。这个序列可以用一棵二叉树来描述。
PS.你也是北邮的吗？

不知道你是按哪个公式展开的，我展开结果不是这样的

PS：不是的^_^

cobras

用我的递推式才可得到楼主需要的序列

tyc611

原帖由 cobras 于 2007-2-4 11:13 发表
如下是模拟栈的递归实现（如果学过编译原理就不难理解）
fibr函数是C递归代码，main中的是模拟递归代码
[code]
#include <stdio.h>
#include <stdlib.h>

#define ALEN(v) (sizeof(v)/sizeof(( ...

很不错，赞一个

用我的递推式才可得到楼主需要的序列

恩，不过，就怕他序列推错了，呵呵

upstorm

原帖由 cobras 于 2007-2-4 11:13 发表
如下是模拟栈的递归实现（如果学过编译原理就不难理解）
fibr函数是C递归代码，main中的是模拟递归代码
[code]
#include <stdio.h>
#include <stdlib.h>

#define ALEN(v) (sizeof(v)/sizeof(( ...

强

如果按楼主所说的，要求效率高，空间利用率高，这不是摆明了要再去增加一个寄存器吗？

feiyang21687

1. 
   
2.         while(ip>=0){
   
3.                 switch(ip){
   
4.                 case 0:
   
5.                         push(bp);
   
6.                         bp=sp;
   
7.                         printf("%d ", ss[bp+2]);
   
8.                         if(ss[bp+2]<=1){
   
9.                                 ax=1;
   
10.                                 ip=4;
    
11.                         }else{
    
12.                                 ip=1;
    
13.                         }
    
14.                         break;
    
15.                 case 1:
    
16.                         push(ss[bp+2]/2);
    
17.                         call();
    
18.                         break;
    
19.                 case 2:
    
20.                         sp+=1;
    
21.                         push(ax);
    
22.                         push((ss[bp+2]+1)/2);
    
23.                         call();
    
24.                         break;
    
25.                 case 3:
    
26.                         sp+=1;
    
27.                         ax+=pop()+ss[bp+2];
    
28.                         ip=4;
    
29.                         break;
    
30.                 case 4:
    
31.                         bp=pop();
    
32.                         ret();
    
33.                         break;
    
34.                 }
    
35.         }
    

复制代码

小弟愚笨，这段代码不甚明白，是否可以说明一下。多谢了。