算法笔记 - 设计与修改 - 轩辕春秋文化论坛 20周年


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

发表于 2005-1-19 15:30 资料主页个人空间短消息看全部作者

QUOTE:

原帖由Maxwell于2005-01-19, 14:30:53发表
呵呵，我记得有本书上定义是对于任何有效输入都可以在有限步内停机的自动机，更抽象吧

这个好像是可计算理论里的有限自动机的可计算性（不要求结束时回到开始处）的定义

对算法，搞竞赛的有这么个说法：给到题要求40分钟内解决，至少要花20分钟在考虑算法上当然过于简单的题不算

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

发表于 2005-1-23 07:02 资料主页个人空间短消息看全部作者

QUOTE:

原帖由loranrowe于2005-01-21, 10:52:15发表
1、递归
递归是什么呢？
递归是一组根据较小输入项的值来描述函数的方程或不等式(生活，是一团麻)
递归是一组方程或不等式
较小输入项是有直观解的，可以称作边界情形和边界值
根据边界值，用方程(方程的另一个意思就是等式)或不等式来描述一个函数，就是递归
在应用中，我们只需要描述边界并定义相应方程或不等式，递归的具体执行，亟递推求解过程，是由机器完成的
这种解是针对某种具体问题的具体解
在分析递归过程的效率时，我们需要一个形式上的解，或者叫做通解，递推的方法不再有效了

说到递归，我来说两句。
递归的好处不用说了，自然是结构清晰，但递归也有不小的坏处。
最直接的就是调试程序变麻烦了，还有就是内存的使用，若在递归里要开数组的话就要小心了。
另外有一点可能大家不注意，就是工具的限制。每个工具因为内存原因都对递归的层数有限制。VC可以将全部硬盘虚拟为内存，这个问题自然不明显（似乎递归的上限是200+）。但若是比较古老的工具，比如说TURBO PASCAL，只能用640K内存，递归上限是30层（也可能多两层，反正不超过33）。用这样的工具，则要注意用非递归的方式来写递归的程序（比如引入一个表示层数的变量，若原来的递归里要开数组，则可以把结构改成十字链表）

要说的就这么多，有时间的话附个程序给大家看一下。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！