算法设计与分析期末试题_考试版1、用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3、算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：
有穷性：确定性：
可行性：输入：输出：算法设计的质量指标：
正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。
126
f算法设计与分析期末试题_考试版复杂性的渐近性态设TN是算法A的复杂性函数，使得当N→∞时有：TNT’NTN→0那么，我们就说T’N是TN当N→∞时的渐近性态，或叫T’N为算法A当N→∞的渐近复杂性而与TN相区别。
PNP
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法
分而治之法1、基本思想将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法所能解决的问题一般具有以下几个特征：
226
f算法设计与分析期末试题_考试版
（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。3、分治法的基本步骤（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。递归：直接或间接的调用自身的算法，叫做递归算法。
1期盘覆盖
用分治策略，可以设计解棋盘问题的一个简捷的算法。当k0时，将2k2k棋盘分割为4个2k12k1子棋盘
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小的棋盘的汇合处，如下图所示，这3个子棋盘上被L型骨牌r