| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2913 人关注过本帖
标题:[原创]递归的艺术-递归程序的非递归化
取消只看楼主 加入收藏
stnlcd
Rank: 1
等 级:新手上路
帖 子:177
专家分:1
注 册:2004-11-21
收藏
得分:0 
以上测试函数在运行时建议关闭其他所有无关的应用程序!

要让一个男人破产,请给他一架相机,要让一个男人倾家荡产,请给他一架望远镜。
2005-06-11 09:50
stnlcd
Rank: 1
等 级:新手上路
帖 子:177
专家分:1
注 册:2004-11-21
收藏
得分:0 
你拿去试试不就知道了吗

要让一个男人破产,请给他一架相机,要让一个男人倾家荡产,请给他一架望远镜。
2005-06-11 11:45
stnlcd
Rank: 1
等 级:新手上路
帖 子:177
专家分:1
注 册:2004-11-21
收藏
得分:0 
在tc下测试,在tc下测试,结果是什么都有可能,在tc下的测试结果根本没有任何参考价值!必要要到vc下才可以!! 这句:“栈是一步到位”,我不是很清楚,请详细说明一下。还有,你理解的回溯是:在解空间树上查找/搜索不到问题的解的时候需要进行回溯重试,所以标准的回溯算法有相应的“剪枝函数”来去除树上不合理的分支,但在comb_dd上使用的迭代回溯本质上是对树的遍历,它只有到达叶子结点时才产生回溯(而一般的回溯问题:比如0/1背包问题,在树的任何一个不合理的结点上都有可能产生回溯)。事实上上面所有函数:comb(递归),comb_w_w,comb_w_if,comb_dd(comb_fz除外)和你的f函数,在本质上都是对解空间树的深度优先搜索(comb_fz是对树的广度优先),也就是进行树的先序遍历,都涉及到从树叶子结点回溯的问题,而不是我的comb_dd所特有的!这些个函数只是在具体实现的时候有差别,而这差别就体现了效率的高低。 还有你说我的hanoi程序“这个方法只可用于参数变化有一定规律的情况”的确如此!但是就hanoi程序而言(其它的我们不肯定),它的效率绝对比同样的“全部参数”进栈高!!!因为它的“全参数进栈”的非递归形式和hanoi_w_if,hanoi_w_w的形式是完全一样的!我就是从“全参数进栈”形式删除x,y,z的进栈语句才得到的,其他的问根本没改,事实上,就hanoi程序而言(有许多函数也是如此):x,y,z的进栈是根本不需要的! 我很喜欢和你这样的人交流,希望继续保持!谢谢你评论我的帖子! 最后:请用vc从新测试。

要让一个男人破产,请给他一架相机,要让一个男人倾家荡产,请给他一架望远镜。
2005-06-11 20:00
stnlcd
Rank: 1
等 级:新手上路
帖 子:177
专家分:1
注 册:2004-11-21
收藏
得分:0 
好! 何为BCB6(borland c++??)?是IDE的界面吗?不要在dos下运行的编译系统。
waiting you!

要让一个男人破产,请给他一架相机,要让一个男人倾家荡产,请给他一架望远镜。
2005-06-11 20:55
stnlcd
Rank: 1
等 级:新手上路
帖 子:177
专家分:1
注 册:2004-11-21
收藏
得分:0 
回复牛虻:在类似vc的ide环境内的函数调用方式和在tc的dos环境方式下的函数调用方式不同!特别是调用bios等低层函数方面。这个问题我理解的不透彻就不谈了。我只知道printf("worst case resolution = %5.4f usec\n", resolution);的输出和 printf("meaningful precision = %d decimal digits\n", prec);的输出以及执行完 BEGIN_TEST("(cache & vm load)");END_TEST();的输出,在vc中每次都一样(我的机器每次都为:1000,100,和0.12),而在tc下差别极大(有时为0,有时为1万多),而下面的程序测试语句都是根据这三句的结果来作为测试的基准,我在tc下的测试,一会comb执行时间为0,而comb_w_w执行时间为1万多,一会它们又反过来了,这样的效果能用来判断程序的效率吗?我不知道是我的机器有问题还是tc环境下不适合做这种测试,我只知道在我的机器上用vc测试,每次得到的效率排序都是一样的:要么所有的测试结果都偏高一点,要么所有的测试结果都偏低但最终测试下来效率排序都是一样的(无论我运行多少次这个测试程序)。

要让一个男人破产,请给他一架相机,要让一个男人倾家荡产,请给他一架望远镜。
2005-06-11 21:32
stnlcd
Rank: 1
等 级:新手上路
帖 子:177
专家分:1
注 册:2004-11-21
收藏
得分:0 
回复wellerweldon:谢谢你的支持!

要让一个男人破产,请给他一架相机,要让一个男人倾家荡产,请给他一架望远镜。
2005-06-11 21:36
stnlcd
Rank: 1
等 级:新手上路
帖 子:177
专家分:1
注 册:2004-11-21
收藏
得分:0 
我觉得我们的分歧在于:你是从大局出发,我从细微之处分析程序的结构。这些函数毕竟是我亲手编写,我觉得我已经掌握了程序中的细节。我再写一个四个参数都进栈的函数:
 void hanoi_all(int n,char x,char y,char z)  {
     struct  {
   int  n;
   char x;
   char y;
   char z;
  }s_all[100];  /*定义栈保存所有参数*/
     int topa=0;
  char t;
  while(n>1||top)  {
   if(n>1)  {
    s_all[top].n=n--;  s_all[top].x=x;  s_all[top].y=y;  s_all[top++].z=z;
    t=y; y=z; z=t;
   }
   else  {
    move(x,1,z);
    n=s_all[--top].n; x=s_all[top].x;  y=s_all[top].y;  z=s_all[top].z;
    move(x,n,z);
    --n;  t=x;  x=y;  y=t;
   }
  }
 }

    程序的效率体现在细微之处,我的观点是:在自己的能力范围内,能让程序效率多高就多高。
不知道我说:”hanoi_all函数的效率测试结果比hanoi_w_w(hanoi_w_if)好“你会不会相信?(反正你也没有vc++)
   好了,我不争论了,我太累了,要sleeping去了。
   对了,这个程序可以用”广度优先策略“重写其非递归算法,不知道simpley同学有没有这个兴趣改写一下?

要让一个男人破产,请给他一架相机,要让一个男人倾家荡产,请给他一架望远镜。
2005-06-11 23:29
stnlcd
Rank: 1
等 级:新手上路
帖 子:177
专家分:1
注 册:2004-11-21
收藏
得分:0 
simpley:测去吧!

要让一个男人破产,请给他一架相机,要让一个男人倾家荡产,请给他一架望远镜。
2005-06-12 18:46
快速回复:[原创]递归的艺术-递归程序的非递归化
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021849 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved