发布时间 : 星期五 文章大学计算机应用基础实用教程[09]第7章 软件技术基础更新完毕开始阅读
图是用流程图表示的程序基本结构。其中“选择”结构具体画了两种：两分支和多 分支。“循环”结构也画了两种：DO-WHILE 型和DO-UNTIL 型。 4. 算法设计的基本方法
通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。
算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计算法，又常常采用递归技术，用递归描述算法。 （1） 迭代法
1) 2) 3)
选一个方程的近似根，赋给变量x0；
将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；
当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。
第5页共35页
若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0
就认为是方程的根。算法的基本运算和操作 算法的基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
具体使用迭代法求根时应注意以下两种可能发生的情况：
1)
如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；
2)
方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。
（2） 穷举搜索法
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众
找出那些符合要求的候选解作为问题的解。按穷举法编写的程序通常不能适应变化的情况。最重要的因素就是确定某种方法来确定所有的候选解。
（3） 递推法
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题
规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，?，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。 （4） 递归
递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分
用，为此在进一步介绍其他算法设计方法之前先讨论它。
解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当
递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列
第6页共35页
“简单问题”层，它们各有自己的参数和局部变量。
由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的
执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。 （5） 回溯法
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题
的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。 （6） 贪婪法
贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快
速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。 （7） 分治法
任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，?。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题（1 第7页共35页 （8） 动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。 为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。 7.1.2算法复杂度 评价一个算法优劣的主要标准是算法的执行效率和存储需求,即时间复杂度和空间复杂度。 1. 算法的时间复杂度 算法的时间复杂度即指执行这个算法所需要的计算工作量。一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量。时间复杂度大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=O(f(n)), 称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 第8页共35页