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