精品文档
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棋盘。
精品文档
算法设计与分析期末试题-考试版(汇编)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)