这些算法是不是真的很难啊。。。。。有懂的哥们姐们帮帮忙啊。。。。。(200分)

  • 主题发起人 主题发起人 youou
  • 开始时间 开始时间
Y

youou

Unregistered / Unconfirmed
GUEST, unregistred user!
回溯法。。。。迭代法。。。。递归。。。
说说吧~~我不懂。。。。。。。。。。。。。帮帮忙啊。。。。。
 
当你有需要用到就不难了。
比如说,要编个程序用FTP下载一个目录,就要用到递归--碰到列表中的是目录就进入它,否则,下载它
 
递归我知道,
其他不懂!
 
1、八皇后问题,典型的回溯法。模拟人找答案的方法。在一个系统中,有N个变量,它们的组
合有N!种情况,其中有的组合是符合要求的,即“解”。回溯法就是用循环的方式让变量们
尽可能的变化,去找解,某个变量变到头了,就“回溯”回去,再变其他的变量。最终找到
所有的解。
2、菲波那契数列,可用迭代法。想求结果数列A的第n项A[n],先从A[0]开始求A[1],再从
A[1]求A[2],一直迭代到A[n]。如已知A[0]=5,A[n]=A[n-1]+3,求A[10],则解法为:
A[0]=5,A[1]=A[0]+3=5+3=8,A[2]=A[1]+3=8+3=11....一直推到A[10]=A[9]+3即可。
3、菲波那契数列,也可用递归。递归就是函数自己调用自己(包括直接或间接)。例如
A[n]=A[n-1]+3,那么,如果A[0]=5,求A[20],用递归法就是:A[20]=A[19]+3;再将A[19]
展开为A[18]+3,则A[20]=(A[18]+3)+3,一直到A[20]=(...(((A[0]+3)+3)+3).....+3),
将A[0]=5代入,就求出来了。
 
谢谢大家。。。。。。特别感谢fatalexception~
---------------------------------------------------
简单的递归可以看得懂。。。就如:菲波那契数列用递归。
一有点复杂就傻了。。例:汉诺塔的问题用递归。。怎么看也不懂。。。。
还有就是最讨厌是回溯法。。知道其它基本原理,但是看代码老是不懂。。。我要填空的
因为要考高程。。。
 
  回溯确实难了一些,递归是用效率换可读性,回溯则是用可读性换效率。回溯有几个要
点:当前控制的参量、当前的层次、当前方向、本轮结束条件,将这几个要点搞清楚了就不
会乱了。
  汉诺塔的递归算法本质是:
  1、将A针上的N-1个盘子移动到C针上;
  2、将A针上的最大的盘子移动到B针上;
  3、将C针上的N-1个盘子移动到B针上;
  其中Move(a,b,c)就是递归的原子函数。
  在调用的时候,A针B针C针是来回变的,但操作方式是一样的。被借助的针,由于总是
  保持放相对较大的盘子,因此其他盘子往上放的时候可以视为空针。
 
TO fatalexception:
可以把你QQ号给我吗?或者把我加为好友可以吗?QQ:171720804
 
大富翁上高手如云,小弟只不过才出道,还是将问题发出来让大家指教吧!
 
老老实实看高程书吧!
上面的算法很经典!
递归最好的还是看看N!的算法!很简单。
 
这些算法是最基本的,如果你看不懂最好别去考高程了。浪费money。
 
  严格来讲,“递归”不是算法,而是算法的一个分类。而且递归类型的算法一般都
是基于一个递归定义的模型的。例如树的中序遍历,它基于一个递归定义:先访问左子树,
再根节点,最后访问右子树。其中“子树”可以是“树”或“叶子”,这就是一个递归
定义。在理解了这个模型之后,直接把模型写成递归的程序就可以了。所以看懂一个递归
算法,关键是看懂模型,程序反而是其次。(当然,如果你编程比数学好,可以通过程序
去理解模型,但最终了解问题的递归模型是最重要的)
  迭代同样也是一类算法,它在数学上的定义是把不断地函数的结果作为自变量代入同
一函数,也就是f(f(f(...f(f(x))...))))。但函数的设计应该保证每一次的计算结果都能
逼近最终结果。因此要了解迭代算法,主要是了解这个函数的本身。例如辗转相除求最大公
约数,就是不停的把A,B两个数进行一定的处理,然后把上一步得出的A,B作为下一步开始
的A,B。
  而回溯法是一个纯粹的计算机算法,说白了就是高级版的穷举。它的思路是:如果能前
进,就前进。如果不能前进,就后退。如果找到结果,就成功,如果退回到起点,就失败。
按我的个人经验,理解回溯法就应该从简单的例程(走迷宫,八皇后,回溯法求全排列)去
分析。关键是了解:1)前进条件,2)前进时的处理,3)回溯条件,4)回溯时的处理
回溯的关键是从例程上去分析,理解前进和后退的
 
厉害厉害!
楼上老兄学数学的吧!辗转相除求最大公约数,的确是迭代法的经典啊!
 
谢谢大家。。。
我知道这些算法的原理,可是复杂点的程序看起来比较费尽的。。。。。。
----------------------------------------------------------------------
来自:delphilai, 时间:2002-10-5 11:28:00, ID:1360273
这些算法是最基本的,如果你看不懂最好别去考高程了。浪费money。
--------
这位兄弟说得对。。。可是我简单点的看得懂的。。还是有可能会浪费money..
特别感谢fatalexception,kidneyball
 
后退
顶部