TC官方合作论坛

标题: [教程] 【算法教程】递推算法(有图有真相)!!! [打印本页]

作者: 阿三 时间: 2013-12-9 14:43
标题: [教程] 【算法教程】递推算法(有图有真相)!!!
本帖最后由阿三于 2013-12-9 15:49 编辑

“程序=算法+数据结构”,是众人皆知的道理。但是在我们实际的学习中,我们可能会忽视算法的分析与讲解。更可能有些人不知道什么是算法。久而久之,势必造成死板地学习一个个语法格式,结果语句是懂了,但面对具体问题时,还是不知从何下手。因为我对于算法也算略有了解，所以我就结合自己地理解再根据一些具体的题目的讲解，希望大家也能认识到算法的重要性，能够理解并掌握一些算法，说不定对于程序的编写会有所帮助。　

递推
递推法是一种重要的数学方法。这种算法的特点是：一个问题的求解需要一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系。在计算时，如果可以找到前后过程之间的数量关系（即递推式）。那么顺推还是逆推，其关键是找到递推式。这种处理问题的方法能使复杂运算转化为若干步重负的简单运算，充分发挥计算机擅长于重复处理的特点。
我们来看一道题：数字三角形。请编一个程序计算从顶到底的一条路径，使该路径所经过的数字总和最大，输出数字总和的最值。每一步可沿斜线向左下或右下走
[attach]13198[/attach]
该数字三角形可转化为上。这样每一步就相当于沿向下或向右下行走。我们可以采用倒推的手段，设数字(i,j)
存放从i，j出发到达n层的最大值。具体算法过程是：因为每一步都可以沿向下或向右下行走。
于是当我们走到倒数第2层的时候（在这道题上是第4层，即i=4）。我们该考虑最后一层该如何走。请看图
[attach]13199[/attach]
种颜色就代表每一种路径的所有选择。所以。在每一种路径中，我们都找出当前最大的一条路继续走
[attach]13201[/attach][attach]13202[/attach][attach]13203[/attach]

解为30。这只是其中的一种解法，其他解法在介绍别的算法的时。我们用i和j表示行和列，利用数学关系计算。用tc代码表示为:

再得出递推式:

翻译一下就是比较下一层的下方的一个数和右下方的一个数。谁

大就把谁加到上一层上。用这种倒循环和正循环配合，正好能完

美得配合上这道题的结构。

再来看一个题
楼梯有n级台阶，上楼可以一步上一个台阶，也可以一步上两个台

阶。编写一个程序计算共有多少种不同的走法。我们设一个数组f

存放走法。一开始看这个题可能没有头绪，不急，我们很容易地

可以知道当n=1，f[1]=1。n=2，f[2]=2。现在我们来看有3级台阶

的时候。我们分2种情况。
第一种，如果第一步走一层，那么还剩下3-1级台阶，这时候就是

n=2的时候的走法。
第二种，如果第一步走两层，那么还剩下3-2级台阶，这时候就是

n=1的时候的走法。
所以我们得出。f[n]=f[n-1]+f[n-2]。
这个递推式就是著名的斐波那契数，在很多问题上都可正解。

作者: 星.月 时间: 2013-12-9 15:03
一点一点学习

作者: netboy 时间: 2013-12-9 15:06
收藏学习

作者: jianqiumy 时间: 2013-12-9 21:55
看看~~

作者: haizhen005 时间: 2014-1-9 01:03
看看

作者: JSDYWZ 时间: 2014-1-16 15:54
递推算法

作者: 1034520808 时间: 2014-1-19 12:34
学学

作者: yrt 时间: 2014-2-1 00:34

收藏学习

作者: faithk 时间: 2014-3-7 13:32
恢复看看啊

作者: 言术 时间: 2014-3-22 19:45
了解一下

作者: 贾南 时间: 2014-10-29 21:30
学习一下

作者: laowantong 时间: 2015-6-16 09:03

作者: yangningwei3373 时间: 2015-6-27 12:05
花样百出花样百出

作者: aa112233 时间: 2015-7-25 14:36
ADFDSAFDSFB

作者: tbmbx2017 时间: 2016-9-11 03:19
喜闻乐见的帖子呀！

作者: ysfx8296 时间: 2018-8-29 20:41
学习学习

欢迎光临 TC官方合作论坛 (http://bbs.52tc.co/)