本帖最后由 阿三 于 2013-12-9 15:49 编辑
“程序=算法+数据结构”,是众人皆知的道理。但是在我们实际的学习中,我们可能会忽视算法的分析与讲解。更可能有些人不知道什么是算法。久而久之,势必造成死板地学习一个个语法格式,结果语句是懂了,但面对具体问题时,还是不知从何下手。因为我对于算法也算略有了解，所以我就结合自己地理解再根据一些具体的题目的讲解，希望大家也能认识到算法的重要性，能够理解并掌握一些算法，说不定对于程序的编写会有所帮助。
递推
递推法是一种重要的数学方法。这种算法的特点是：一个问题的求解需要一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系。在计算时，如果可以找到前后过程之间的数量关系（即递推式）。那么顺推还是逆推，其关键是找到递推式。这种处理问题的方法能使复杂运算转化为若干步重负的简单运算，充分发挥计算机擅长于重复处理的特点。
我们来看一道题：数字三角形。请编一个程序计算从顶到底的一条路径，使该路径所经过的数字总和最大，输出数字总和的最值。每一步可沿斜线向左下或右下走
该数字三角形可转化为上。这样每一步就相当于沿向下或向右下行走。我们可以采用倒推的手段，设数字(i,j)
存放从i，j出发到达n层的最大值。具体算法过程是：因为每一步都可以沿向下或向右下行走。
于是当我们走到倒数第2层的时候（在这道题上是第4层，即i=4）。我们该考虑最后一层该如何走。请看图
种颜色就代表每一种路径的所有选择。所以。在每一种路径中，我们都找出当前最大的一条路继续走
解为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]。
这个递推式就是著名的斐波那契数，在很多问题上都可正解。
|
[复制链接]
/2 
发表于 2013-12-9 14:43:56
