本帖最后由 阿三 于 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]。
这个递推式就是著名的斐波那契数,在很多问题上都可正解。
|