我们学校开设的这门课，过于理论，实践太少，考试不会太难，一起学习，一起 不挂科！
但是算法平时一定要练哦！加油！
内容摘自老师PPT及复习资料，感谢！

感兴趣的话可以参考 算法竞赛、小白学DP(动态规划) 学习相关代码的具体实现(Java版)

课程介绍

算法分析基础

算法的定义

算法是指解决问题的一种方法或一个过程。
算法是若干指令的有穷序列。

算法正确性

对每一个输入实例算法都能终止，并给出正确输出。

算法的性质

(1)输入：有外部提供的量作为算法的输入。
(2)输出：算法产生至少一个量作为输出。
(3)确定性：组成算法的每条指令是清晰，无歧义的。
(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
（可行性）

程序的定义

程序是算法用某种程序设计语言的具体实现。

程序与算法的区别

程序可以不满足算法的性质(4)（有限性）。
例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。
操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，当子程序得到输出结果后便终止。

这个好像要考(*￣︶￣)

算法设计和分析的步骤

（1）问题的陈述。
（2）模型的选择。
（3）算法的设计。
（4）算法的程序实现。
（5）算法分析。

复杂度分析

算法复杂性 = 算法所需要的计算机资源
1、考虑算法的好坏主要有以下几点：
（1）执行算法所耗费的时间。
（2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间。
（3）算法应易于理解，易于编码，易于调试等。

2、影响程序运行时间的主要因素 ：
（1）程序的输入。
（2）由编译系统所产生的代码程序的质量。
（3）执行程序的计算机机器指令的性能与速度。
（4）程序所依据的算法的时间复杂度。

3、算法的复杂性测度主要有两个方面：
(1) 时间复杂度 T(n)
(2) 空间复杂度 S(n)
其中n是问题的规模（输入大小）。

算法的复杂性取决于：

(1)求解问题的规模N；
(2)具体的输入数据I；
(3)算法本身的设计

可操作性最好且最有实际价值的是最坏情况下的时间复杂性。

算法的时间复杂性

算法渐近复杂性

渐近分析的记号

渐近上界记号

渐近下界记号

非紧上界记号

非紧下界记号

紧渐近界记号

意义

算法分析中常见的复杂性函数

算法分析方法

算法分析的基本法则

递归

基本概念

递归的概念:

直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。

说明:

1、递归程序必须有终止条件。否则就总是自我调用，永不终止。
2、尽管递归程序在执行时间上往往比非递归程序要付出更多的代价，但有很多问题的数学模型或算法设计方法本来就是递归的。
3、用递归过程来描述它们不仅非常自然，而且证明该算法的正确性要比相应的非递归形式容易得多。
4、递归过程的优点：结构清晰，程序易读，正确性容易证明 。
5、缺点：运行的效率比较低 、花时间。
6、实现递归过程的关键在于为过程的递归调用建立一个先进后出型调用堆栈 。一个过程要有一个相应的递归调用堆栈。

欧几里得算法：已知两个非负整数m，n，且m>n>0，求这两个数的最大公因子。

欧几里得得出本算法基于这样一种观察，两个整数m和n的最大公因子等于n与m mod n的公因子。欧几里得算法如下：

GCD (m，n)
1       if n=0
2           then return m
3       return  GCD (n，m  mod n) 

递归优缺点

优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

递归树方法

基于递归树的方法可以更好地猜测一个问题的解，并用替换方法证明这个猜测。

递归树的生成规则：

1. 初始，递归树只有根结点，其值为W(m)；
2. 不断继续下述过程：
   将函数项叶结点的迭代式W(mi)表示成二层子树；
   用该子树替换该叶结点；
3. 继续递归树的生成，直到树中无函数项(只有初值)为止。

例题：解递归方程T(n)=3T(n/4)+cn2。假设n为4的幂。

递归树的构造过程如下：

分析：

图(a)表示T(n)。
图(b)表示对T(n)进行扩展，形成与递归方程等价的一棵树。cn2表示树的根，即递归顶层的开销。根的三棵子树为小一级的递归方程T(n/4)。
图( c )表示对T(n/4)的进一步展开。根据递归方程，继续展开树中的每个结点，直到问题规模变成1，每个开销为T(1)。
图(d)表示最终结果树。树的高度是log4n，深度为log4n+1。

例题： T(n)=2T(n/2)+n-1

T(n)=kn-(2k-1)=nlogn-n+1=O(nlogn)

主方法

主方法(master method)为我们提供了解如下形式递归方程的一般方法。
T(n)=aT(n/b)+f(n)

• 其中a≥1，b>1为常数，f(n)是渐近正函数。
• 递归方程 T(n)=aT(n/b)+f(n) 描述了算法的运行时间，算法将规模为n的问题划分成a个子问题，每个子问题的大小为n/b，其中a、b是正常数。求解这a个子问题，每个所需时间为T(n/b)。函数f(n)表示划分子问题与组合子问题解的开销。
• 每个子问题n/b未必为整数，但用T(n/b)代替T(⌈n∕b⌉)和T(⌊n∕b⌋ )并不影响递归方程的渐近行为，因此我们在表达这种形式的分治算法时将略去向下取整函数和向上取整函数。

主定理

主定理解析

主定理举例

分治法

总体思想

将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

分治法的设计思想是，将一个难以直接解决的大问题，
分割成一些规模较小的相同问题，以便各个击破，
分而治之。
凡治众如治寡，分数是也。
----孙子兵法

适用条件

分治法所能解决的问题一般具有以下几个特征：

• 该问题的规模缩小到一定的程度就可以容易地解决；
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
• 利用该问题分解出的子问题的解可以合并为该问题的解；
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
• 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。

归并排序

归并排序(merge sorting) 是分治法应用的一个实例，由以下三步组成：

(1)划分：将待排序n个元素的序列划分成两个规模为n/2的子序列。
(2)解决：用归并排序递归地对每一子序列排序。
(3)合并：归并两个有序序列，得到排序结果。
当划分的子序列规模为1时，递归结束。因为一个元素的序列被认为是有序的。

算法的复杂度分析

归并算法的改进

• MERGE-SORT算法将待排序集合一分为二，不停递归，直至排序集合只剩1个元素为止。然后不断合并2个排好序的数组段。
• 递归算法运行效率低，怎样从分治策略的机制入手，消除算法中的递归？
• 方案：首先将数组中相邻元素两两配对。用合并算法将他们排序，构成n/2组长度为2的排好序的子数组段，如此继续，直至整个数组排好序。

快速排序

快速排序由C. A. R. Hoare在1960年提出。

基本思想：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

动态规划

算法总体思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。

但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。

如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

动态规划基本步骤

1）找出最优解的性质，并刻划其结构特征。
2）递归地定义最优值。
3）以自底向上的方式计算出最优值。
4）根据计算最优值时得到的信息，构造最优解。

动态规划算法的基本要素

最优子结构

• 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
• 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
• 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）。

重叠子问题

• 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
• 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
• 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
  

备忘录方法

备忘录方法的控制结构与直接递归方法的控制结构相同(自顶向下)，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

0-1背包实例

最长公共子序列

矩阵连乘

分析最优解的结构

建立递归关系

递归的复杂性

计算最优值

DP求解的复杂度分析

构造最优解

贪心算法

贪心算法与分治法和动态规划算法的关系

1）分治法将原问题分解成独立的子问题，然后递归求解子问题，并组合成原问题的解。
2）动态规划应用于子问题不独立时，它的实质是分治思想和解决冗余，为避免重复计算，它将已经计算过的子问题存储起来，达到最优解决问题的目的。
3）贪心法与动态规划法和分治法类似，都是将问题分解为规模更小的、相似的子问题，并通过求解子问题产生一个最优解。
有些具有最优子结构性质的问题，可以用动态规划算法求解，但是用贪心算法更简单、更直接，且解题效率更高。

贪心算法的基本思想

贪心法的当前选择可能要依赖已经做出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地做出贪心选择。

贪心法总是做出在当前时刻看起来最优的决策，即希望通过局部最优决策导致问题的全局最优解。

特别说明：贪心法并不总是产生问题的全局最优解，但许多问题利用贪心法求解得到全局最优解。

贪心算法的基本要素

贪心选择(greedy-choice)的性质

• 利用贪心算法的第一步，是问题具有贪心选择的性质，通过局部最优选择(贪心)，可以得到问题的全局最优解。
• 当考虑要做出哪一个选择时，我们会选择当前看起来最优的，而不考虑子问题的结果。这就是贪心算法和动态规划算法的不同之处。
• 在动态规划算法中，当我们在每一步做出选择时，这个选择通常会依赖于子问题的解。 因而，我们一般会按照自底向上的方式，求解的过程从较小的问题到较大的问题，最后解决原问题。
• 而在贪心算法中，我们首先会做出当前看起来最优的选择，然后解决选择之后出现的子问题。 贪心算法的选择可能取决于到目前为止所做的选择， 但不会依赖于未来的选择，也不会依赖于子问题的解。因此，采用贪心策略解问题的过程通常按照自顶向下的方式逐次进行贪心选择，将每一给定问题实例减少到更小问题实例。

最优子结构(optimal substructure)

• 如果问题的最优解中包含子问题的最优解，则问题展示了最优子结构。这个性质是评价应用动态规划以及贪心算法的基本性质。背包问题和活动选择问题都具有最优子结构性质。
• 在背包问题中，如果问题的一个最优解包含物品j，我们从最优装包中去掉物品j的一个权值w，那么，余下至多为W-w的容量，一定包括n-1个物品以及物品j的权值为wj-w的最优装包方式。

两个背包问题

背包问题与0-1背包问题的不同点在于，在选择物品装入背包时，可以只选择物品的一部分，而不一定要选择物品的全部。

• 尽管这两个问题很相似，但是背包问题可用贪心法求解， 而0-1背包问题却不能。
• 对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。
• 事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上动态规划算法的确可以有效地解0-1背包问题。

前缀码

二元前缀码：用0-1字符串作为代码表示字符，要求任何字符的代码都不能作为其它字符代码的前缀。

回溯算法

使用回溯法的问题特征：当需要找出问题的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。

回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

搜索策略：回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

子集树的构造
0-1背包问题对应的解空间就是一棵子集树, 树中所有结点都可能成为问题的一个解。子集树中至多有2n个叶结点。
因此，任何算法遍历子集树所需运行时间为Ω(2n)。

排列树的构造

搜索树的构造

生成问题状态的方法

回溯法的基本思想

(1)针对所给问题，定义问题的解空间；
(2)确定易于搜索的解空间结构；
(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

常用剪枝函数：

用约束函数在扩展结点处剪去不满足约束的子树；
用限界函数剪去得不到最优解的子树。

n皇后问题

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

4皇后问题：棋盘上的行和列从1到4编号，同时也给皇后从1到4编号。由于每一个皇后应放在不同的行上，假设皇后i放在第i行上，因此4皇后问题可以表示成4元组(x1, x2, x3, x4)， 其中xi(i=1, 2, 3, 4)表示皇后i所放置的列号。

显式约束条件是Si={1, 2, 3, 4}，i=1, 2, 3, 4。在这种情况下，解空间为4^4个4元组组成。

隐式约束条件是没有两个xi相同(即所有皇后必须在不同列上)，且满足不存在两个皇后在同一条对角线上。加上隐式约束条件，问题的解空间可进一步减小。此时，解空间大小为4!，因为所有解都是4元组的一个置换。

4皇后问题的解空间

可以用一棵树表示4皇后问题的解空间。 由于4皇后问题的解空间为4!种排列，因此将要构造的这棵树是一棵排列树。

使用剪枝函数的4皇后问题的状态空间树

• 在实际中，并不需要生成问题的整个状态空间，可以通过使用剪枝函数来杀死那些还没有生成其所有子结点的活结点。
• 下图是使用剪枝函数的4皇后问题的部分状态空间树，图中一个结点一旦被剪枝函数杀死，则用B做上记号。

• 在4皇后问题中，惟一开始结点为根结点1，路径为()。开始结点既是一个活结点，又是一个扩展结点, 它按照深度优先的方式生成一个新结点2，此时路径为(1)，这个新结点2变成一个活结点和新的扩展结点，原来的扩展结点1仍然是一个活结点。
• 结点2生成结点3，但立即被杀死。于是，回溯到结点2，生成它的下一个结点8，且路径变为(1, 3)。
• 结点8成为扩展结点，由于它的所有子结点不可能导致答案结点，因此结点8也被杀死。回溯到结点2，生成它的下一个结点13，且路径变为(1, 4)。

n皇后问题及回溯算法

将4皇后问题推广到n皇后问题(n-queen problem)，即找出n×n的棋盘上放置n个皇后并使其不能互相攻击的所有解。

设X =(x1, x2, …, xn)表示问题的解，其中xi表示第i个皇后放在第i行所在的列数。

• 解向量：(x1, x2, …, xn)
• 显约束：xi=1,2, … ,n
• 隐约束：
  1)不同列：xixj
  2)不处于同一正、反对角线：|i-j||xi-xj|

N-QUEEN算法代码分析

• 第1~2行进行初始化。
• 第3行的while 循环表示，对于所有行执行循环体，计算xk值。
• 在第5~6行的while循环中，对于每一个xk值，调用PLACE过程测试它的合法性, 即寻找满足约束条件的xk值。
• 第7行中，如果找到一个放置位置，则进一步测试，所求(x1, x2, …, xk)是否为问题的解，这只需判断k是否等于n。如果是问题的解，则输出(第9行), 否则通过赋值语句将k值增加1, 继续外层while 循环。
• 如果第7行的条件为假，则表明不存在合法的xk值，此时将k值减1(第12行)，进行回溯。

分支限界法

分支限界法与回溯法的区别

（1）求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

分支限界法基本思想

• 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
• 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
• 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的两种分支限界法

(1) 先进先出(first in first out，简称FIFO)分支限界法(FIFOBB)。在先进先出的分支限界法中，用队列作为组织活结点表的数据结构，并按照队列先进先出的原则选择结点作为扩展结点。
(2) 优先队列(priority queue，简称PQ)分支限界法(PQBB)。 在优先队列分支限界法中，用优先队列作为组织活结点表的数据结构，每个结点都有一个成本或价值，按照最大价值(greatest value)/最小成本(least cost)的原则选择结点作为扩展结点。

两种分支限界法的异同

先进先出状态空间树

优先队列状态空间树

当用优先队列作为组织活结点表的数据结构，并按照结点估值函数值的大小选择下一个扩展结点时，就得到0-1背包问题优先队列状态空间树。

组合优化问题

• 目标函数（极大化或极小化）
• 约束条件：解满足的条件
• 可行解：搜索空间满足约束条件的解
• 最优解：使得目标函数达到极大（或极小）的可行解
• 典型的组合优化问题有：
  旅行商问题（TSP）、生产调度问题、0-1背包问题、装载问题、图着色问题、最大团问题等。

代价函数

• 计算位置：搜索树的结点
• 值：极大化问题是以该点为根的子树所有可行解的值的上界（极小化问题为下界）
• 性质：对极大化问题父结点代价不小于子结点的代价（极小化问题相反）

界

• 含义：当前得到可行解的目标函数的最大值（极小化问题相反）
• 初值：极大化问题初值为0（极小化问题为最大值）
• 更新：得到更好的可行解时

分支限界

停止分支回溯父结点的依据：

1. 不满足约束条件
2. 对于极大化问题，代价函数值小于当前界（对于极小化问题是大于界）。

界的更新：
对极大化问题，如果一个新的可行解的优化函数值大于（极小化问题为小于）当前的界，则把界更新为该可行解的值。

Sample Test

select question

1. 当输入规模为 n 时，算法增长率最小的是 B，最大的是 C。
   
2. 
3. 渐进算法分析是指 当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析
4. 递归通常用 栈 来实现。
5. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 问题规模不同，问题性质相同
6. 对于 0-1 背包问题和背包问题的解法 0-1 背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包 问题则可以用贪心算法求解
7. 具有最优子结构的算法有 动态规划法、贪心算法、分治算法
8. 关于回溯搜索法的介绍：

1）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解。
2）回溯法是一种既带系统性又带有跳跃性的搜索算法。
3）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯。

9. 关于回溯算法和分支限界法

1）分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入 活结点表中。
2）回溯法和分支限界法都是在解空间树上搜索问题解的方法。
3）回溯法和分支限界法都可以用来解决组合优化问题。

10. 优先队列通常用以下堆数据结构来实现。
11. 算法分析中，记号 O 表示 渐进上界。
12. 备忘录算法是动态规划算法的变形。
13. 回溯法 不具有最优子结构的算法

分治算法 动态规划算法 贪心算法 有最优子结构

14. 剪枝函数是回溯法中避免无效搜索采取的策略。
15. 用贪心法求解背包问题时的贪心选择策略是 单位容量带来的价值之比
16. 数学归纳法不是求解递归方程的方法。

替换法、 递归树方法、主方法是求解递归方程

17. 算法的性质包括输入、输出、确定性、有穷性、可行性。
18. 一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有有穷特性。
19. 最长公共子序列算法利用的算法是 动态规划算法。
20. 贪心算法的基本要素的是 贪心选择的性质。
21. 若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最坏情况下的时间复杂度为 O(n^2)
22. 回溯法的效率不依赖于下列哪些因素 确定解空间的时间

效率依赖于：满足显约束的值的个数、计算约束函数的时间、计算限界函数的时间。

23. 贪心算法与动态规划算法的主要区别是 贪心性质的选择

最优子结构、构造最优解、定义最优解。

24. 算法的实现依赖于数据结构的设计
25. 分支限界法 通常以广度优先方式系统搜索问题解。
26. 分治算法一定 由三个步骤组成：划分子问题、求解子问题、合并子问题的解。
27. 利用贪心法求解 0/1 背包问题时没有任何准则能够确保最优解。
28. 用递归算法求解 F(5) 时，需要7次加运算，该方法采用的是分治策略。
29. 若一个问题既可以用迭代方式也可以用递归方式求解，则迭代方法具有更高的时空效率。
30. 迪杰斯特拉 (Dijkstra) 算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了贪心算法策略。
31. 在下列算法中得到的解未必正确的是 拉斯维加斯算法
32. 对给定 n 元数组进行排序，应用比较方法进行排序，其时间复杂度下界是 O(n*log2^n)。
33. 回溯法和分支限界算法求解问题时，需要构造对该问题的解空间结构，期排列通常有个 n! 叶节点。
34. 用随机投点发发计算圆周率，在单位矩形上随机投了 n 次，有 k 次落在单位圆内（圆心在单位矩形的一个顶点上），则圆周率为： k/n=PI/4.
35. 有回溯算法求解活动安排问题，其解空间可以用排列树来表示
36. 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是 分支界限算法。
37. 子集树的构造

当所给的问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树(subset tree)。
有2^n个子集。

排列数的构造

为了构造出所有n!种排列，可以设一个具有n个元素的数组。第k个位置的候选解的集合就是那些不在前k-1个元素的部分解中出现的元素集合。

38. 用分治算法优化大整数相乘，算法复杂度可以达到 O(n^log3)。

O(n^2)

39. 3n2 +10n 的渐进表达式 n^2，10 ^ log3 n的渐进表达式是 n.
40. 在快速排序、插入排序和合并排序算法中，插入排序算法不是分治算法。
41. 应用Johnson法则的流水作业调度采用的算法是 动态规划算法
42. 汉诺塔问题

1~N从A移动到B，C作为辅助
等价于：
1，1~N-1从A移动到C，B为辅助
2，把N从A移动到B
3，1~N-1从C移动到B，A为辅助

void hanoi(int n, int A, int B, int C){
	if (n > 0) {
		hanoi(n-1,A,C,B);
		move(n,A,B);
		hanoi(n-1,C,B,A);
	}
}

43. 动态规划的基本要素为 最优子结构与重叠子问题性质
44. 算法分析中，O表示渐进上届，欧美大表示渐进下界，O心中有-表示：紧渐进界，o：非紧上界，w：非紧下界。
    
45. 贪心求解最优解问题，一般重要性质：最优子结构性质与贪心性质的选择。
46. 回溯法的效率不依赖于 问题的解空间形式

依赖于：产生x[k]的时间，产生显约束的x[k]值的个数，计算上界函数约束的所有x[k]的个数，计算约束函数的时间

47. O(g(n))：f(n)存在正常数 c和n0，使得对所有的 n>=n0有：0<=f(n)<=cg(n);（渐进上界）
48. 下列不是动态规划算法基本步骤的是：找出最优解的性质

构造最优解、算出最优解、定义最优解

49. 最大效益优先是（分支界限法）的一搜索方式。
50. 动态规划法 通常以自底向上的方式求解最优解。
51. 衡量一个算法好坏的标准是 时间复杂度低
52. 实现循环赛日程表利用的算法是 分治策略
53. 棋盘覆盖问题、选择问题、归并排序使用分治法求解

0/1背包问题不是。

54. 回溯法 通常以深度优先方式系统搜索问题解。
55. 备忘录方法是那种算法的变形 动态规划法。
56. 哈弗曼编码的贪心算法所需的计算时间为 O(nlogn)。
57. 贪心选择性质 是贪心算法的基本要素。
58. 剪枝函数 是回溯法中为避免无效搜索采取的策略。
59. P类问题包含在NP类问题中。
60. 最优子结构性质是贪心算法与动态规划算法的共同点。
61. Strassen算法采用分治法解决矩阵乘积问题，并通过排列组合的技巧使得分治法产生的递归树不那么“茂盛”以减少矩阵乘法的次数。
62. 使用分治法求解不需要满足的条件是 子问题必须是一样的

子问题不能够重复、子问题的解可以合并、原问题和子问题使用相同的方法解。

63. N皇后问题不能使用贪心法解决（用回溯算法解决）

单源最短路径问题、最小花费生成树问题、背包问题。

64. 贪心算法不能解决0/1背包问题

动态规划、回溯法、分支限界法

65. 动态规划算法基本要素的是 重叠子问题

动态规划算法以自底向下的方式求解最优解

66. 背包问题的贪心算法所需的计算时间为 O(nlogn)
67. 实现大整数的乘法是利用的分治策略算法
68. 0-1背包问题的回溯算法所需的计算时间为o(n*2n)
69. 拉斯维加斯算法找到的解一定是 正确解
70. 实现最大子段和利用的算法是 动态规划法
71. 优先队列式分支限界法选取扩展结点的原则是 结点的优先级
72. 背包问题的贪心算法所需的计算时间为 O(nlogn)
73. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的 最优子结构性质

fill blank

1. . 一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 时间复杂性 和 空间复杂性之分。
2. 算法具有以下五大特性是 确定性 有穷性 可行性 输入 输出
3. 一个直接或间接调用自身的算法称为 递归算法。 出自于“平衡子问题”的思想， 通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同。
4. 使用分治法的三个步骤是 划分 解决 合并
5. 贪心算法的基本要素是 贪心选择的性质 最优子结构
6. 动态规划算法有一个变形方法 备忘录。这种方法不同于动态规划算法“自底 向上”的填充方向，而是“自顶向下”的递归方向，将每个解过的子问题存储下来以 备需要时查看，同样也可避免相同子问题的重复求解。
7. 循环不变式具有以下三个性质 初始、维持、终止
8. 二分查找算法的实现前提是 列表已排好序
9. 动态规划算法的基本要素是 最优子结构性质、子问题重叠性质
10. 若序列 X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列 X 和 Y 的一个最长公共子序列 {BABCD}或{CABCD}或{CADCD}
11. 贪心法总是做出在当前时刻看起来最优的决策，即希望通过 局部最优决策导致问题的 全局最优解。
12. 最优子结构性质的意义是： 问题的最优解包含着其子问题的最优解
13. 回溯法定义问题的状态空间结构包括 子集树、排列树、搜索树
14. 前缀码是指 只用 0/1 对字符进行编码，并限定任一字符的编码都不是另一个字符编码的前缀。
15. 利用主方法可解递归方程的一般形式T(n)=aT(n/b)+f(n)
16. 回溯法与分支限界法搜索方式不同，回溯法按深度优先搜索解空间，分支限界法按广度优先或最小耗费优先搜索解空间。
17. 回溯法与分支限界算法求解问题时，需要构造对该问题的解空间结构，其解空间结构通常有 3 种形式，分别是子集树、排列树 、满 m 叉树。
18. 复杂度大小关系：
    
19. 背包问题与0-1背包问题的不同点在于，在选择物品装入背包时，可以只选择物品的一部分， 而不一定要选择物品的全部。
20. 贪心选择性质是指：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
21. 所谓最优子结构性质是指：问题的最优解包含子问题的最优解。
22. 回溯法：具有限界函数的深度优先生成法。
23. 用回溯算法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前结点扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径长度为 h(n)，则回溯算法所需的空间通常为 O(h(n))。
24. 回溯算法的框架按照问题的解空间一般分为子集树算法框架和排列树算法框架。
25. 用回溯算法求解批处理作业调度问题时，该问题的解空间结构是排列树结构。
26. 描述算法常用方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD图。
27. 算法设计的要求：正确性和可读性。
28. 算法由操作、控制结构、数据结构三要素组成。
29. 所有递归函数都能找到对应的非递归的定义。
30. 归并排序、二分搜索是分治算法的思想。
31. 动态规划中存储子问题是为了 避免重复求解子问题。
32. 最优子结构是问题能用动态规划求解的前提（也是其基本要素）。
33. 矩阵连乘可由动态规划求解。
34. 最优子结构的性质：原问题的最优解包含其子问题的最优解。（分解出的子问题不相互独立）。
35. 贪心算法不一定满足最优子结构的性质。
36. 回溯算法中限界函数的目的是减去得不到最优解的子树。
37. 活结点表的组织方式不同，分支界限法包括 队列式分支界限算法和优先队列式分支界限算法。
38. 分支界限按 广度优先搜索或最小耗费优先 搜索解空间。
39. 回溯算法与分支界限算法求解问题时，需要构造对该问题的解空间结构，子集树、排列树、满m叉树。
40. 活动安排：

最早开始时间：可以增大资源的利用率。
最早结束时间（更合理）：可以使下一个活动尽早开始。

41. 程序是 算法 用某种程序设计语言的具体实现。
42. 算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。
43. 算法是指解决问题的 一种方法 或 一个过程。
44. 从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法。
45. 问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。
46. 以深度优先方式系统搜索问题解的算法称为 回溯法。
47. 解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划，需要排序的是 回溯法 ，分支限界法。
48. 使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题。
49. 贪心算法的基本要素是 贪心选择性质和 最优子结构性质。
50. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题的解得到原问题的解。
51. 算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性、有限性四条性质。
52. 大整数乘积算法是用 分治法 来设计的。
53. 贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。
54. 快速排序算法是基于 分治策略 的一种排序算法。
55. 动态规划算法的两个基本要素是 最优子结构性质 和 重叠子问题 性质 。
56. 回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。
57. 分支限界法主要有 队列式（FIFO） 分支限界法 和 优先队列式 分支限界法。
58. 回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数。
59. 任何可用计算机求解的问题所需的时间都与其 规模 有关。
60. 某一问题可用动态规划算法求解的显著特征是具有 最优子结构性质
61. 用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含 一个最优解。
62. 0-1背包问题的回溯算法所需的计算时间为,用动态规划算法O(n*2n)，所需的计算时间为 O(min{nc,2n})。
63. 输入规模三种度量是 输入元素的个数，二进制表示的总个数 和 对于图可用图中顶点和边数。
64. 本书介绍三种求解递归方程的方法是 替换、递归树和主方法。
65. 动态规划的4个步骤是

①刻画最优解结构、②递归定义最优解的值、③计算最优解的值、④根据计算结果，构造最优解。

66. 算法是将转入转换成输出的计算步骤所组成的序列或描述输入输出关系的特定计算过程。
67. 渐进表示：是方便地表示算法的最坏情况下，计算的复杂度。
68. 运行时间：是指在某个输入时，算法执行操作的次数或者步数。
69. 动态：是所作的决策可能依赖当前状态，而此前所作的决策无关。
70. 算法设计和分析的步骤可概括为：

①问题的陈述。
②模型的选择。
③算法的设计。
④算法的程序实现。
⑤算法分析。

71. 循环不变式的三个性质： ① 初始、② 维持、③ 终止
72. 替换方法的两个步骤是 ①首先猜测问题的解的某个界限间、②然后用数字归纳法证明所测解的正确性
73. 分治方法的三个步骤是： ①划分、②解决、③合并
74. 算法分析：是指对一个算法所需要的计算机资源进行预测。
75. 算法正确性：对每一个输入实例算法都能终止，并给出正确输出。
76. 递归：对自己的调用。
77. 规划：意味着一系列的决策。
78. 运行时间：是指在某个输入时，算法执行操作的次数或者步数。
79. 最坏情况：是指算法的运行时间是任一输入运行时间的上界。
80. 哈夫曼编码：哈夫曼提出的贪心算法可以构造最优前缀编码，这样产生的编码称为哈夫曼编码。
81. 算法 将输入转化为输出的计算步骤所组成的序列或是描述输入输出关系的特定计算过程。
82. 平凡矩阵链乘：在矩阵链乘中不能进行分割矩阵链乘。
83. 快速排序算法的性能取决于划分的对称性。
84. 舍伍德算法是（概率算法）的一种。
85. 背包问题、哈夫曼编码的贪心算法所需的计算时间为 O(n*logn)，0-1背包问题的回溯算法所需的计算时间为 O(n * 2n)。
86. 实现最大子段和利用的算法是 动态规划法。
87. 下列是动态规划算法基本要素的是 重叠子问题。
88. Strassen矩阵乘法是利用（分治策略）实现的算法。
89. 回溯法解旅行售货员问题时的解空间树是 子集树。
90. 在下列算法中有时找不到问题解的是 拉斯维加斯算法。
91. 找出最优解的性质不是动态规划算法基本步骤。

构造最优解、算出最优解、定义最优解

short question

什么是算法？算法的特征有哪些？

算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法就是解决问题的方法或过程。
特征：
1.输入：有零个或多个外部量作为算法的输入。
2.输出：算法产生至少一个量或作为输出
3.确定性：组成算法的每条指令是清晰的，无歧义的
4.有限性 :算法中每条指令的执行次数有限，执行每条指令的时间也有限
5.可行性

考虑算法的好坏主要有以下几点：

1、执行算法所耗费的时间。
2、执行算法所耗费的存储空间，其中主要考虑辅助存储空间。
3、算法应易于理解，易于编码，易于调试等。

主定理

1. 简述递归方程 T(n)=4T(n/2)+n 是否可以使用主方法来进行求解。如果可以，写出满足主 定理的哪一种情形，并求解该递归方程；如果不满足，写出理由。

简述分治法的适用条件（特征）

(1)该问题的规模缩小到一定的程度就可以容易地解决；
(2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
(3)利用该问题分解出的子问题的解可以合并为该问题的解； (4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

设计动态规划算法的基本步骤

(1) 刻画问题最优解的结构
(2) 递归定义最优解的值
(3) 自底向上的计算问题最优解的值
(4) 根据计算的结果，构造问题最优解

动态规划算法的基本思想

简述分支限界法与回溯法的不同

(1) 求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在 某种意义下的最优解。
(2) 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

简述递归的定义及优缺点

定义：一个直接或间接调用自身的算法。
优点：结构清晰，程序易读，正确性容易证明。
缺点：运行的效率比较低、花时间。

简述回溯法的一般执行步骤

针对所给问题，定义问题的解空间；
确定易于搜索的解空间结构；
以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法的基本原理

子集树：O(2n) 2n个叶子结点 2n+1-1个结点。
排列树：O（n!）n!个叶子结点。

在问题的解空间中，按深度优先遍历策略，从根节点出发搜索解空间树。算法搜索至解空间的任意一个节点时，先判断该节点是否包含问题的解。如果肯定不包含，跳过对以该节点为根的子树的搜索，逐层向其祖先节点回溯，否则进入该子树，继续深度优先搜索。

简述分治法和动态规划算法的相同点和不同点

相同点：二者要求原问题具有最优子结构，都是将问题分而治之分解成若干个规模较 小的子问题；
不同点：分治法将原问题分解成独立的子问题，然后递归求解子问题，并组合成原问题的解。而动态规划应用于子问题不独立时，它的实质是分治思想和解决冗余，为避免重复计算，它将已经计算过的子问题存储起来，达到最优解决问题的目的。

简述常见的两种分支限界法

(1) 先进先出(first in first out，简称 FIFO)分枝限界法。在先进先出的分枝限界法中， 用队列作为组织活结点表的数据结构，并按照队列先进先出的原则选择结点作为扩展结点。
(2) 优先队列(priority queue，简称 PQ)分枝限界法。在优先队列分枝限界法中，用优先队列作为组织活结点表的数据结构，每个结点都有一个成本或价值，按照最大价值 (greatest value)/最小成本(least cost)的原则选择结点作为扩展结点。

（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

贪心算法与分治法和动态规划算法的异同

1）分治法将原问题分解成独立的子问题，然后递归求解子问题，并组合成原问题的解。
2）动态规划应用于子问题不独立时，它的实质是分治思想和解决冗余，为避免重复计算，它将已经计算过的子问题存储起来，达到最优解决问题的目的。
3）贪心法与动态规划法和分治法类似，都是将问题分解为规模更小的、相似的子问题，并通过求解子问题产生一个最优解。
有些具有最优子结构性质的问题，可以用动态规划算法求解，但是用贪心算法更简单、更直接，且解题效率更高。

贪心算法与动态规划算法的主要区别所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是利用贪心算法求解最优解的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

差异点：动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。

贪心算法的基本元素

贪心法自顶向下，一步一步地做出贪心选择。希望通过局部最优决策导致问题的全局最优解。

具有贪心选择的性质以及最优子结构。

哈夫曼编码：哈夫曼提出的贪心算法可以构造最优前缀编码，这样产生的编码称为哈夫曼编码。

分支限界法与回溯法的区别

都是在问题的解空间上搜索问题解的算法。

（1）求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

分支界限法的基本思想

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

分支限界法设计算法的步骤

(1)针对所给问题，定义问题的解空间（对解进行编码）；
(2)确定易于搜索的解空间结构（按树或图组织解） ；
(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

动态规划与备忘录算法的比较

常用的剪枝函数

1）用约束函数在扩展结点处剪去不满足约束的子树；
2）用限界函数剪去得不到最优解的子树。

矩阵连乘问题

请给出矩阵连乘问题的文字描述，然后用数学符号和公式表达出来。

什么是递归算法？递归算法的特点？两个要素？

递归方程和约束函数（递归终止条件）是递归的两个要素。

递归算法是一种直接或者间接地调用自身的算法。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

特点：

1. 每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算。（递归终止条件）
2. 递归中较小自变量函数值来表达较大自变量的函数值；（递归方程式）

适合用分治算法求解的问题具有的基本特征？

1、该问题的规模缩小到一定的程度就可以容易解决
2、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
3、利用该问题分解出子问题解可以合并为该问题解

动态规划算法解题步骤？

(1)刻画最优解的结构。
(2)递归定义最优解的值。
(3)自底向上(或自顶向下)方式计算最优解的值。
(4)根据计算的结果，构造问题最优解。

(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2) 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3) 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4) 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

渐进表示的定义

1. 如果存在三个正常数

2. 如果存在两个正常数c，n0，对于所有的 n≥n0，有0≤f(n)≤cg(n)，则记作f(n)≤O(g(n))。

考虑算法的好坏的因素

1、执行算法所耗费的时间。
2、执行算法所耗费的存储空间，其中主要考虑辅助存储空间。
3、算法应易于理解，易于编码，易于调试等。

最优子结构

如果问题的最优解包含子问题的最优解，则问题展示了最优子结构。

递归循环与迭代

递归是重复调用函数自身实现循环。 迭代是函数内某段代码实现循环。
迭代与普通循环的区别是：
循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。

算法分析的目的

1）对算法某些特定输入，估算该算法所需的内存空间和运行时间。
2）为了建立衡量算法优劣的标准，用比较同一类问题的不同算法。

典型的解空间树：子集树和排列树

（1）当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间。
（2）当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。

分支限界法的搜索策略

在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

二叉查找法算法基本思想

1、将n个元素分成大致相等的两部分。
2、取A(⌊n/2⌋)与v进行比较。
3、如果相等，则找到v，返回v所在位置，算法终止；
4、如果v<A(⌊n/2⌋)，则在数组的左半部分继续查找v；如果v>A(⌊n/2⌋)，则在数组的右半部分继续查找v。
5、当所查找的区间为0时，表示v不在数组中，返回查找不成功标志0。

归并排序

1）步骤：
①划分：将待排序n个元素的序列划分成两个规模为n/2的子序列。
②解决：用归并排序递归地对每一子序列排序。
③合并：归并两个有序序列，得到排序结果。
当划分的子序列规模为1时，递归结束。因为一个元素的序列被认为是有序的。
2）归并算法描述：归并排序的关键操作是归并两个已排序的子序列的过程。用过程MERGE(A,p,q,r)表示归并两个有序序列A[p…q]和A[q+1…r]。当过程MERGE(A,p,q,r)执行完成后A[p…r]中包含的元素有序。
3）归并排序算法描述：我们将利用MERGE作为排序算法的子过程，利用MERGE-SORT对子数组A[p…r]中的元素进行排序。

calculate question

1. 某商店有 n 个物品，第 i 个物品价值为 vi，重量(或称权值)为 wi， 其中 vi和 wi为非负数。设 c［i, w］表示背包容量为 w 时，i 个物品导致的最优解的总价值。写出 0-1 背包问题的递归方程。

2. 设 l［i, j］表示序列 Xi和 Yj的 LCS 的长度，写出最长公共子序列的递归方程。

3. 使用主方法求解递归方程 T(n)=4T(n/2)+n，需写出满足主定理的哪一种情形。

解：由递归方程可得，a=4，b=2 且 f(n)=n。因此，

4. 使用递归树方法求解递归方程 T(n)=2T(n/2)+n-1，需画出完整的递归树。
   
5. 写出矩阵链乘问题的递归方程。假设最优加括号方式将乘积 AiAi+1…Aj分裂为 AiAi+1…Ak和 Ak+1Ak+2…Aj，其中 i≤k<j，设 m[i, j] 表示计算 Ai…j所需的最少乘法次数。
   
6. 算法的定义
   
7. 欧几里得算法。

GCD（n，m）
If m=0
Return n
Return（ GCD m n mod m）

8. Strassen算法递归方程。

T(n)= O(1)… n=2
T(n)= 7T(n/2)+O(n2)…n>2

9. 设A=（5，7，12，25，34，37，43，46，58，80，92，105），推导出查找元素34的变量low，high和mid的运行轨迹。

10. 自然地导出递归的斐波那契过程 F(n)

F(n)
1 if n≤2
2 then return 1
3 return F(n-1)+F(n-2)

11. 分治法计算时间的递归方程:
    
12. 活动选择问题的递归方程

13. 矩阵链乘问题的最优解

14. 背包问题最优解

15. 活动选择问题的递归贪心算法

algorithm analysis

MergeSort

2. 

LCS

QuickSort

template<class Type>
void QuickSort (Type a[], int p, int r)
{
      if (p<r) {
        int q=Partition(a,p,r);
        QuickSort (a,p,q-1); //对左半段排序
        QuickSort (a,q+1,r); //对右半段排序
        }
}

BubbleSort

分析冒泡排序法BUBBLE－SORT(A)的最佳情况和最坏情况。

1. 当输入数组正好为升序时，出现最佳情况，第4行语句不执行。
2. 当输入数组为降序时，出现最差情况，第4行语句执行n（n－1）/2次。

N皇后问题

bool Queen::Place(int k)
{ //检查x[k]位置是否合法
  for (int j=1;j<k;j++)
    if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;
  return true;
} 

void Queen::Backtrack(int t)
{
  if (t>n) sum++;
  else    
  	for (int i=1;i<=n;i++) {
      x[t]=i;
      if (约束函数) Backtrack(t+1);
    }
}

最大团问题

void Clique::Backtrack(int i) // 计算最大团
{  
	if (i > n) { // 到达叶结点
      for (int j = 1; j <= n; j++) bestx[j] = x[j];
      bestn = cn;   return;}
 // 检查顶点 i 与当前团的连接
   int OK = 1; 
   for (int j = 1; j < i; j++)
      if (x[j] && a[i][j] == 0) {         // i与j不相连
         OK = 0;  break;}

   if (OK ) { // 进入左子树
      x[i] = 1;  cn++;
      Backtrack(i+1);
      x[i] = 0; cn--;  }
   
  if (cn + n - i > bestn) { // 进入右子树
      x[i] = 0;
      Backtrack(i+1);  }
}

design question

2. 写出用动态规划解矩阵链乘问题的递归定义和最优解值的伪代码程序。

3. 写出哈夫曼编码的过程

理论加实践缺一不可，二者决定你走的深度与高度。

加油！

淦!

算法设计与分析

前言

    通过学习掌握算法设计的主要方法，对算法的时、空复杂性有正确分析的能力，能够针对具体的应用问题选择合适的数据结构并设计结构清晰、正确有效的算法，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。

第一章 算法基础

1.1 算法概述

1.什么是算法？
    算法(algorithm):算法是对特定问题求解步骤的描述，是指令的有限序列。就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
2.算法的五个特征

• 输入：算法有零个或多个输入量；
• 输出：算法至少产生一个输出量；
• 确定性：算法的每一条指令都有确切的定义，没有二义性；
• 可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；
• 有穷性：算法必须执行有限步之后终止。

3.问题和问题求解
    问题求解：寻找一种方法来实现目标。
    问题求解过程：人们通过使用问题领域知识来理解和定义问题，并凭借自身的经验和知识求选择和使用适当的问题求解策略、技术和工具，将一个问题描述转换成问题解的过程。
    计算机求解问题的关键之一是寻找一种问题求解策略得到求解问题的算法，从而得到问题的解。
4.问题求解过程

• 理解问题
• 设计方案
• 实现方案
• 回顾复查

1.2 算法分析

1.算法问题求解过程

2.算法分类
    精确算法总能保证求得问题的解。
    启发式算法通过使用某种规则、简化或智能猜测来减少问题求解时间。
    对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法。
    如果在算法中需要做出某些随机选择，则称为随机算法。
3.算法设计

• 计算机的问题求解策略主要指算法设计策略。
• 如果所求问题符合某种算法设计策略处理问题的特性，就可使用该算法设计策略设计算法、求解问题。

4.算法表示

算法描述方法

• 自然语言
• 流程图
• 伪代码
• 程序设计语言
• 使用c/c++语言描述

5.算法确认

• 算法确认：确认一个算法是否正确的活动。
• 算法证明：使用数学方法证明算法的正确性。
• 程序测试：是指对程序模块或程序总体，输入事先准备好的样本数据（称为测试用例），检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求和活动。

6.算法分析

• 算法分析：对算法的执行时间和所需空间的估量。（时间复杂度和空间复杂度）
• 程序的性能测量：使用样本数据，实际测量一个程序所消耗的时间和空间。

1.3 算法复杂度

1.什么是好的算法

    一个好的算法应具备以下4个重要特性：

• 正确性：算法的执行结果应当满足预先规定的功能和性能要求。
• 简明性：算法要思路清晰、层次分明、容易理解、利于编码和调试。
• 高效性：算法要有效使用存储空间，并具有高的时间效率。
• 最优性：算法的执行时间已达到求解该类问题所需时间的下界。

    程序健壮性：是指当输入不合法数据时，程序可以做适当处理而不至于引起严重后果。 其含义是：当程序万一遇到意外时，能按某种预定方式作出适当处理。

    正确性和健壮性是相互补充的。

2.影响程序时间的因素

    影响程序运行时间的因素主要有：

• 程序所依赖的算法；

• 问题规模和输入数据；

• 计算机系统性能
  3.算法的时间复杂度

• 抽象机模型
      设抽象机提供由m个基本运算组成的运算集O={O1,O2,…,Om}，每个运算都是元运算，（运算亦称演算，数学的基本概念之一，指使的一些计算规则，算术中有加、减、乘、除、乘方、开方六种运算，其中加、减、乘、除是从两个已知数得出第三个数的运算，称为二元运算；乘方、开方是从一个已知数得出另一个数的运算，称为一元运算）。 它们的执行时间是有限常量。设执行第i个运算Oi所需的时间是αi，1≤i≤m。
  一个算法给定一个输入并在抽象机上执行一次，该执行过程表现为执行一个基本运算序列。

• 时间复杂度
      算法的时间复杂度是指算法运行所需的时间。
      设有一个在抽象机上运行的算法A，I是某次运行时的输入数据，其规模为n，则算法A的运行时间T是n和I的函数，记做T(n,I)。又设在该次运算中抽象机的第i个基本运算Oi的执行次数为βi，1≤i≤m。βi也是n和I的函数，记做βi(n,I)。那么算法A在输入为I时的运行时间是：
  

• 最好、最坏和平均时间复杂度：

• 最好时间复杂度
  

• 最坏时间复杂度
  

• 平均时间复杂度（与概率论中的数学期望概念类似，在概率论和统计学中，期望值（或数学期望、或均值，亦简称期望，物理学中称为期待值）是指在一个离散性随机变量试验中每次可能结果的概率乘以其结果的总和。换句话说，期望值是随机试验在同样的机会下重复多次的结果计算出的等同“期望”的平均值。 ）
  
  4.算法分析

• 事前分析：在算法实际运行前分析算法的效率。

• 事后测试：运行程序来测试一个程序在所输入数据下实际运行的时间。

• 程序步：在语法或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关。

• 实例
  
  5.算法的空间复杂度

• 算法的空间复杂度：算法运行所需的存储空间。

• 程序运行所需的存储空间包括以下两个部分：

• 固定空间需求：这部分空间与所处理数据的大小和个数无关，即与问题实例的特征无关。

• 可变空间需求：这部分空间大小与算法在某次执行中处理的特定数据的规模有关。

1.4 渐近表示法

1.大O记号
    定义：设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≤cg(n)，则记做f(n)=O(g(n))，称为大O记号。
    意义：该算法的运行时间 不会超过 g(n)的某个常数倍。 g(n)是该算法运行时间的上界。

• 渐进时间复杂度
      使用大O记号及下面定义的几种渐近表示法表示的算法时间复杂度，称为算法的渐近时间复杂度。
      只要适当选择关键操作，算法的渐近时间复杂度可以由关键操作的执行次数之和来计算。一般地，关键操作的执行次数与问题的规模有关，是n的函数。
  

2.Ω 记号
    定义：设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≥cg(n)，则记做f(n)=Ω (g(n))，称为Ω记号。
    意义：该算法至少需要g(n)的某个常数倍大小的时间量。g(n)是该算法运行时间的下界。
例题1：

例题2：

3.Θ记号
    定义：设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正常数c1,c2和n0，使得当n≥n0时，有c1g(n)≤f(n)≤c2g(n)，则记做f(n)=Θ(g(n))，称为Θ记号。
    意义：该算法实际运行时间大约为g(n)的某个常数倍大小的时间量。（有上界也有下界）
例题1：

4.小o记号
    定义：f(n)=o(g(n))当且仅当f(n)=O(g(n))且f(n)≠ Ω(g(n))
    意义：该算法的运行时间f(n)的阶比g(n)低。

5.算法按时间复杂度分类

• 算法按计算时间分类
      渐近时间复杂度有多项式时间限界的算法称做多项式时间算法。
      渐近时间复杂度为指数函数限界的算法称做指数时间算法。

• 最常见的多项式时间算法的渐近时间复杂度
      O(1)＜O(log n)＜O(n)＜O(nlog n)＜O(n2)＜O(n3)

• 最常见的指数时间算法的渐近时间复杂度
       O(2n)＜O(n!)＜O(nn)
  

第二章 分治法

算法设计与分析期末复习题（一）

✅作者简介：大家好我是编程ID
📃个人主页：编程ID的csdn博客
系列专栏：算法
💬推荐一款编程题刷题神器👉点击跳转进入网站

1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解
3、最大效益优先是（ A ）的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
4、最长公共子序列算法利用的算法是（ B ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
5. 回溯法解TSP问题时的解空间树是（ A ）。
A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树
6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
7、衡量一个算法好坏的标准是（C ）。
A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短
8、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题
9. 实现循环赛日程表利用的算法是（ A ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
10、实现最长公共子序列利用的算法是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
11．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。
A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解
14．广度优先是（ A ）的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
15．背包问题的贪心算法所需的计算时间为（ B ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
16．实现最大子段和利用的算法是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
17．实现棋盘覆盖算法利用的算法是（ A ）。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
18.下面是贪心算法的基本要素的是（ C ）。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解
19.回溯法的效率不依赖于下列哪些因素（ D ）
A.满足显约束的值的个数 B. 计算约束函数的时间
C. 计算限界函数的时间 D. 确定解空间的时间
20.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）
A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数
21、以深度优先方式系统搜索问题解的算法称为 ( D ) 。
A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法
22、贪心算法与动态规划算法的主要区别是（ B ）。
A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解
23. 采用最大效益优先搜索方式的算法是（ A ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
24. （ D ）是贪心算法与动态规划算法的共同点。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质
25. 矩阵连乘问题的算法可由（ B）设计实现。
A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法
26. 0-1背包问题的回溯算法所需的计算时间为（ A ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
27、背包问题的贪心算法所需的计算时间为（ B ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
29、使用分治法求解不需要满足的条件是（A ）。
A 子问题必须是一样的 B 子问题不能够重复C 子问题的解可以合并 D 原问题和子问题使用相同的方法解
30、下面问题（B ）不能使用贪心法解决。
A 单源最短路径问题 B N皇后问题 C 最小花费生成树问题 D 背包问题
31、下列算法中不能解决0/1背包问题的是（A ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
32、回溯法搜索状态空间树是按照（C ）的顺序。
A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历
33、采用广度优先策略搜索的算法是（ A ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
34．实现合并排序利用的算法是（ A ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
35．下列是动态规划算法基本要素的是（ D ）。
A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质
36．下列算法中通常以自底向下的方式求解最优解的是（ B ）。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
二、 填空题
1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。
2、程序是 算法 用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。
4.矩阵连乘问题的算法可由 动态规划 设计实现。
5、算法是指解决问题的 一种方法 或 一个过程 。
6、快速排序算法的性能取决于 划分的对称性 。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。
8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。
9、以深度优先方式系统搜索问题解的算法称为 回溯法 。
10、任何可用计算机求解的问题所需的时间都与其 规模 有关。
11、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。
12、回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数
14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。
15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。
17、回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。
18. 动态规划算法的两个基本要素是. 最优子结构性质和 重叠子问题 性质
19.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。
21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。
算法是由若干条指令组成的有穷序列，且要满足输入，输出 、确定性和 有限性 四条性质。
23、快速排序算法是基于 分治策略 的一种排序算法。
24、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。
三、算法设计题
1.背包问题的贪心算法， 分支限界算法
2.最大子段和: 动态规划算法
3.贪心算法求活动安排问题
5.快速排序
6. 多机调度问题-贪心算法

四、简答题
1分治法的基本思想
2. 分治法与动态规划法的相同点
3. 分治法与动态规划法的不同点
4. 分支限界法与回溯法的相同点
5．分治法所能解决的问题一般具有的几个特征是：
6. 用分支限界法设计算法的步骤
7. 回溯法中常见的两类典型的解空间树是子集
8. 请简述符号t(n)∈θ(g(n)), t(n)∈Ω(g(n)),t(n)∈Ο(g(n))的含义。
9. 分支限界法的搜索策略是：
算法设计与分析期末复习题（二）

蒈一、选择题（20分）

薆1．最长公共子序列算法利用的算法是（???B???）。

莆A、分支界限法 B、动态规划法 C、贪心法 D、回溯法

膄2．实现棋盘覆盖算法利用的算法是（???A???）。

蒁A、分治法 B、动态规划法 C、贪心法 D、回溯法

薆3.下面是贪心算法的基本要素的是（???C???）。

薃A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解

蚂4.回溯法的效率不依赖于下列哪些因素（D）

芀A.满足显约束的值的个数 B.计算约束函数的时间

蚆C.计算限界函数的时间 D.确定解空间的时间

羄5.下面哪种函数是回溯法中为避免无效搜索采取的策略（???B???）

莄A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数

罿6．采用最大效益优先搜索方式的算法是（???A???）。

聿A、分支界限法 B、动态规划法 C、贪心法 D、回溯法

莅7．贪心算法与动态规划算法的主要区别是（??B???）。

螂A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解

肂8.实现最大子段和利用的算法是（???B???）。

腿A、分治策略 B、动态规划法 C、贪心法 D、回溯法

螆9.优先队列式分支限界法选取扩展结点的原则是（???C???）。

薄A、先进先出 B、后进先出 C、结点的优先级 D、随机

螁10.下列算法中通常以广度优先方式系统搜索问题解的是（???A??）。

艿A、分支限界法 B、动态规划法 C、贪心法 D、回溯法

膇二、填空题（22分每空2分）

羂1.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。

薀2、大整数乘积算法是用分治法来设计的。

艿3、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。

芄4、舍伍德算法总能求得问题的一个解。

蚄5、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

荿6.快速排序

荿template

蚅voidQuickSort(Typea[],intp,intr)

膁{

莁if(p<r){

葿intq=Partition(a,p,r);

肅QuickSort(a,p,q-1);//对左半段排序

袃QuickSort(a,q+1,r);//对右半段排序

膀}

蕿}

蒆7.哈密顿环问题的算法可由回溯法设计实现。

芁8.贪心算法不一定产生最优解。

衿9.算法中通常以深度优先方式系统搜索问题解的是回溯法。

虿三、算法设计与分析（25分）

蚃1.用欧几里德迭代算法求两个数的最小公倍数（10分）

莃#include

羈usingnamespacestd;

聿intGcd(intm,intn)

莄{

螁 if(m==0)

肁 returnn;

腿 if(n==0)

螅 returnm;

薃 intt=m>n?n:m;

螀 while(m%t||n%t)

艿 t–;

膆 returnt;

羁}

蕿intmain()

芈{

薇 inta,b;

蚃 cout<<“Inputa&b(0<=a<b):”;

薂 cin>>a>>b;

莈 intm=a*b/Gcd(a,b);

蚄 cout<<“TheLeastCommonMultipleis:”<<m<<endl;

蒅 return0;

莁2、试用动态规划算法实现最大子矩阵和问题：求矩阵A的一个子矩阵，使其各元素之各为最大。（15分）

蒈解：解答如下：

肅intMaxSum2(intm,intn,int**a)

袃{

膀intsum=0;

薈int*b=newint[n+1];

蒆for(inti=1;i<=m;i++){

薄for(intk=1;k<=n;k++)b[k]=0;………………………………（5分）

罿for(intj=i;j<=m;j++){

羂for(intk=1;k<=n;k++)b[k]+=a[j][k];

膁intmax=MaxSum(n,b);

芆if(max>sum)sum=max;

芅}

羂}

芇returnsum;………………………………（10分）

肈}

羄intMaxSum(intn,int*a)

肂{

蚈intsum=0,b=0;

蒆for(inti=1;i<=n;i++){

螃if(b>0)b+=a[i];

膂elseb=a[i];

聿if(b>sum)sum=b;

膈}

螆Returnsum;………………………………（15分）

芁}

薀四、简答题（33分）

蚆1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题，使收益最大，请写出求解过程请写出求解过程。（10分）

薅物品
莁A
羁B
莈C
莄D
蒁E
肈F
袆G

肃重量
薁35
葿30
薈60
膆50
薁40
袀10
羅25

袄价值
蚁10
芀40
蚇30
蚃50
螁35
蚁40
膅30

蚆解：使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。

袁2.写出分治算法MaxMin算法对下列实例中找最大数和最小数的过程。（10分）

螈数组A=(48,12,61,3,5,19,32,7)

袇解：1、48,12,61,3,5,19,32,7表中元素多于二，对半分割

蒅2、48,1261,35,1932,7表中元素多于二，对半分割

羀3、48～61,12～319～32，5～7

腿求前半部分的最大最小和后半部分的最大最小，两个半部分的大者为最大，小者为最小

蕿4、61～323～5两个半部分的大者为最大，小者为最小

芄5、613寻找结束

肀3.写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。（13分）

薀

膀484

腿3

羆545
2
216

各边的代价如下：
C(1,2)=3，C(1,3)=5，C(1,4)=2
C(2,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4，C(4,5)=2，C(4,6)=1
C(5,8)=4，C(6,8)=5，C(7,8)=6
解：Cost(4,8)=0
Cost(3,7)=C(7,8)+0=6，
Cost(3,6)=C(6，8)+0=5,
Cost(3,5)=C(5，8)+0=4
Cost(2,4)=min{C(4，6)+Cost(3,6),C(4，5)+Cost(3,5)}
=min{1+5,2+4}=6
Cost(2,3)=min{C(3，6)+Cost(3,6)}
=min{4+5}=9
Cost(2,2)=min{C(2，6)+Cost(3,6),C(2，7)+Cost(3,7)}
=min{8+5,4+6}=10
Cost(1,1)=min{C(1,2)+Cost(2,2),C(1,3)+Cost(2,3),C(1,4)+Cost(2,4)}
=min{3+10,5+9,2+6}=8
按上所述，Cost(1,1)为所求最优值。
算法设计与分析期末复习题（三）
1
《算法设计与分析》历年期末试题整理(含答案) （1）用计算机求解问题的步骤：
1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、
程序调试 8、结果整理文档编制
（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理
过程
（3）算法的三要素
1、操作 2、控制结构 3、数据结构
算法具有以下 5 个属性：
有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出
口
可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有
限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
算法设计的质量指标：
正确性：算法应满足具体问题的需求；
可读性：算法应该好读，以有利于读者对程序的理解；
健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产
生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要
的最大存储空间。一般这两者与问题的规模有关。
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法
迭代法 也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方
法。
利用迭代算法解决问题，需要做好以下三个方面的工作：
一、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或
间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下
一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以
使用递推或倒推的方法来完成。
三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必
须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可
分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是
所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实
现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的
条件。
编写计算斐波那契（Fibonacci）数列的第 n 项函数 fib（n）。
斐波那契数列为：0、1、1、2、3、……，即：
2
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2) （当 n>1 时）。
写成递归函数有：
int fib(int n)
{ if (n0) return 0;
if (n1) return 1;
if (n>1) return fib(n-1)+fib(n-2);
}
一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，
每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到
第 12 个月时，该饲养场共有兔子多少只？
分析： 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为
u 1 ，第 2 个月时兔子的只数为 u 2 ，第 3 个月时兔子的只数为 u 3 ，……
根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有
u 1 ＝ 1 ， u 2 ＝ u 1 ＋ u 1 × 1 ＝ 2 ， u 3 ＝ u 2 ＋ u 2 × 1 ＝
4 ，……

根据这个规律，可以归纳出下面的递
推公式：
u n ＝ u n － 1 × 2 (n ≥ 2)
对应 u n 和 u n － 1 ，定义两
个迭代变量 y 和 x ，可将上面的递
推公式转换成如下迭代关系：
y=x2
x=y
让计算机对这个迭代关系重复执
行 11 次，就可以算出第 12 个月时
的兔子数。参考程序如下：
cls
x=1
for i=2 to 12
y=x2
x=y
next i
print y
end
分而治之法
1、分治法的基本思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模 N 有关。问题
的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于 n 个元素的
排序问题，当 n=1 时，不需任何计算；n=2 时，只要作一次比较即可排好序；n=3 时
只要作 3 次比较即可，…。而当 n 较大时，问题就不那么容易处理了。要想直接解决
一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的
相同问题，以便各个击破，分而治之。
分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
3
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结
构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共
的子子问题。
3、分治法的基本步骤
分治法在每一层递归上都有三个步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同
的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子
问题；
（3）合并：将各个子问题的解合并为原问题的解。
快速排序
在这种方法中， n 个元素被分成三段（组）：左段 l e f t，右段 r i g h t 和中段 m i d d l e。中
段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。
因此 l e f t 和 r i g h t 中的元素可以独立排序，并且不必对 l e f t 和 r i g h t 的排序结果进行合
并。m i d d l e 中的元素被称为支点( p i v o t )。图 1 4 - 9 中给出了快速排序的伪代码。
/ /使用快速排序方法对 a[ 0 :n- 1 ]排序
从 a[ 0 :n- 1 ]中选择一个元素作为 m i d d l e，该元素为支点
把余下的元素分割为两段 left 和 r i g h t，使得 l e f t 中的元素都小于等于支点，而 right
中的元素都大于等于支点
递归地使用快速排序方法对 left 进行排序
递归地使用快速排序方法对 right 进行排序
所得结果为 l e f t + m i d d l e + r i g h t
考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素 6 作为支点，则 6 位于 m i d d l e； 4，3，1，5，2 位于 l e f t；8，7 位于 r i g h t。当 left 排好序后，所得结果为 1，2，3，4， 5；当 r i g h t 排好序后，所得结果为 7，8。把 right 中的元素放在支点元素之后， l e f t 中
的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。
把元素序列划分为 l e f t、m i d d l e 和 r i g h t 可以就地进行（见程序 1 4 - 6）。在程序
1 4 - 6 中，支点总是取位置 1 中的元素。也可以采用其他选择方式来提高排序性能，本章稍
后部分将给出这样一种选择。
程序 14-6 快速排序

template
void QuickSort(T*a, int n)
{// 对 a[0:n-1] 进行快速排序
{// 要求 a[n] 必需有最大关键值
quickSort(a, 0, n-1);
template
void quickSort(T a[], int l, int r)
{// 排序 a [ l : r ]， a[r+1] 有大值
if (l >= r) return;
int i = l, // 从左至右的游标
j = r + 1; // 从右到左的游标
T pivot = a[l];
// 把左侧>= pivot 的元素与右侧<=
pivot 的元素进行交换
while (true) {
do {// 在左侧寻找>= pivot 的元素
i = i + 1;
} while (a < pivot);
do {// 在右侧寻找<= pivot 的元素
j = j - 1;
} while (a[j] > pivot);
if (i >= j) break; // 未发现交换对象
4
Swap(a, a[j]);
}
// 设置 p i v o t
a[l] = a[j];
a[j] = pivot;
quickSort(a, l, j-1); // 对左段排序
quickSort(a, j+1, r); // 对右段排序
}
贪婪法
它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一 定标准下看上
去最优的决策；决策一旦作出，就不可再更改。制定决策的依据称为贪婪准则。
贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到
满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当
前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。
【问题】 背包问题
问题描述：有不同价值、不同重量的物品 n 件，求从这 n 件物品中选取一部分物品的选择方案，使
选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

#include<stdio.h>
void main()
{
int
m,n,i,j,w[50],p[50],pl[50],b[50],s=0,max;
printf(“输入背包容量 m,物品种类 n :”);
scanf(“%d %d”,&m,&n);
for(i=1;i<=n;i=i+1)
{
printf(“输入物品的重量 W 和价值
P :”);
scanf(“%d %d”,&w[i],&p[i]);
pl[i]=p[i];
s=s+w[i];
}
if(s<=m)
{
printf(“whole choose\n”);
//return;
}
for(i=1;i<=n;i=i+1)
{
max=1;
for(j=2;j<=n;j=j+1)
if(pl[j]/w[j]>pl[max]/w[max])
max=j;
pl[max]=0;
b[i]=max;
}
for(i=1,s=0;s<m && i<=n;i=i+1)
s=s+w[b[i]];
if(s!=m)
w[b[i-1]]=m-w[b[i-1]];
for(j=1;j<=i-1;j=j+1)
printf(“choose weight %d\n”,w[b[j]]);
}动态规划的基本思想
前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转
移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出
来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分
并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更
小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可
以考虑用动态规划解决。
5
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、
相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的
子问题，并通过求解子问题产生一个全局最优解。
贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问
题。因此贪心法自顶向下，一步一步地作出贪心选择；
而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问
题的解后，便可自下而上地将子问题的解合并成问题的解。
不足之处：如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最
优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可
能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干
个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题
的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦
即各子问题可包含公共的子问题）也允许其通过自身子问题的解作出选择，该方法对每一个
子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现
大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求
解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
3、动态规划算法的基本步骤
设计一个标准的动态规划算法，通常可按以下几个步骤进行：
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段
一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。
当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有
着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果
我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻
两段的各状态之间的关系来确定决策。
（4）写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。
一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。动态规划的
主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本
方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：
标准动态规划的基本框架

1. 对fn+1(xn+1)初始化; {边界条件}
   for k:=n downto 1 do
   for 每一个xk∈Xk do
   for 每一个uk∈Uk(xk) do
   begin
   fk(xk):=一个极值; {∞或－∞} xk+1:=Tk(xk,uk); {状态转移方程}
   t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式}
   if t比fk(xk)更优 then fk(xk):=t; {计算fk(xk)的最优值}
   end;
   6
   t:=一个极值; {∞或－∞}
   for 每一个x1∈X1 do
   if f1(x1)比t更优 then t:=f1(x1); {按照 10 式求出最优指标}
   输出 t;
   但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：
   （1）分析最优解的性质，并刻划其结构特征。
   （2）递归地定义最优值。
   （3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
   （4）根据计算最优值时得到的信息，构造一个最优解。
   步骤（1）～（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可
   以省略，若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算
   最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速地构造
   出一个最优解。
   总结：动态规划实际上就是最优化的问题，是指将原问题的大实例等价于同一最优化问题的
   较小实例，自底向上的求解最小实例，并将所求解存放起来，存放的结果就是为了准备数据。
   与递归相比，递归是不断的调用子程序求解，是自顶向下的调用和求解。
   回溯法
   回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选
   解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘
   若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的
   规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问
   题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前
   候选解的规模，以继续试探的过程称为向前试探。
   1、回溯法的一般描述
   可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的
   一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个
   分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义
   域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P
   的一个解。
   解问题 P 的最朴素的方法就是枚举法，即对 E 中的所有 n 元组逐一地检测其是否满足 D 的
   全部约束，若满足，则为问题 P 的一个解。但显然，其计算量是相当大的。
   我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足
   D中仅涉及到x1，x2，…，xi的所有约束意味着j（j<i）元组（x1，x2，…，xj）一定也满足
   D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。换句话说，只要存在 0≤j≤n-1，
   使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，
   xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，
   xi的一个约束，n≥i>j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1， x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）
   为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去
   搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚
   举法效率更高的算法。
   回溯法首先将问题 P 的 n 元组的状态空间 E 表示成一棵高为 n 的带权有序树 T，把在 E 中
   求问题 P 的所有解转化为在 T 中搜索问题 P 的所有解。树 T 类似于检索树，它可以这样构
   7
   造：
   设Si中的元素可排成xi
   (1) ，xi
   (2) ，…，xi
   (mi-1) ，|Si| =mi，i=1，2，…，n。从根开始，
   让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次
   序，分别带权xi+1
   (1) ，xi+1
   (2) ，…，xi+1
   (mi) ，i=0，1，2，…，n-1。照这种构造方式，E中的
   一个n元组（x1，x2，…，xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上
   依次的n条边的权分别为x1，x2，…，xn，反之亦然。另外，对于任意的 0≤i≤n-1，E中n
   元组（x1，x2，…，xn）的一个前缀I元组（x1，x2，…，xi）对应于T中的一个非叶子结点，
   T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，…，xi，反之亦然。特别，
   E中的任意一个n元组的空前缀（），对应于T的根。
   因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶
   子结点的路径上依次的n条边相应带的n个权x1，x2，…，xn满足约束集D的全部约束。在T
   中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即
   依次搜索满足约束条件的前缀 1 元组（x1i）、前缀 2 元组（x1，x2）、…，前缀I元组（x1， x2，…，xi），…，直到i=n为止。
   在回溯法中，上述引入的树被称为问题 P 的状态空间树；树 T 上任意一个结点被称为问
   题 P 的状态结点；树 T 上的任意一个叶子结点被称为问题 P 的一个解状态结点；树 T 上满
   足约束集 D 的全部约束的任意一个叶子结点被称为问题 P 的一个回答状态结点，它对应于
   问题 P 的一个解。
   【问题】 n 皇后问题
   问题描述：求出在一个 n×n 的棋盘上，放置 n 个不能互相捕捉的国际象棋“皇后”
   的所有布局。

这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线 4 个方向相互捕捉。
如图所示，一个皇后放在棋盘的第 4 行第 3 列位置上，则棋盘上凡打“×”的位置上的皇后
就能与这个皇后相互捕捉。

1 2 3 4 5 6 7 8
× ×
× × ×
× × ×
× × Q × × × × ×
× × ×
× × ×
× ×
× ×
从图中可以得到以下启示：一个合适的解应是在每列、每行上只有一个皇后，且一条
斜线上也只有一个皇后。

求解过程从空配置开始。在第 1 列至第 m 列为合理配置的基础上，再配置第 m+1 列，
直至第 n 列配置也是合理时，就找到了一个解。接着改变第 n 列配置，希望获得下一个解。
另外，在任一列上，可能有 n 种配置。开始时配置在第 1 行，以后改变时，顺次选择第 2
行、第 3 行、…、直到第 n 行。当第 n 行配置也找不到一个合理的配置时，就要回溯，去改
变前一列的配置。得到求解皇后问题的算法如下：
8
{ 输入棋盘大小值 n；
m=0;
good=1;
do {
if (good)
if (m==n)
{ 输出解；
改变之，形成下一个候选解;
}
else 扩展当前候选接至下一列；
else 改变之，形成下一个候选解；
good=检查当前候选解的合理性；
} while (m!=0);
}

在编写程序之前，先确定边式棋盘的数据结构。比较直观的方法是采用一个二维数组，
但仔细观察就会发现，这种表示方法给调整候选解及检查其合理性带来困难。更好的方法乃
是尽可能直接表示那些常用的信息。对于本题来说，“常用信息”并不是皇后的具体位置，
而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因在某一列上恰好放一个皇
后，引入一个一维数组（col[
]），值 col[i]表示在棋盘第 i 列、col[i]行有一个皇后。例如：col[3]=4，就表示在棋盘
的第 3 列、第 4 行上有一个皇后。另外，为了使程序在找完了全部解后回溯到最初位置，设
定 col[0]的初值为 0 当回溯到第 0 列时，说明程序已求得全部解，结束程序运行。
为使程序在检查皇后配置的合理性方面简易方便，引入以下三个工作数组：
（1） 数组 a[ ]，a[k]表示第 k 行上还没有皇后；
（2） 数组 b[ ]，b[k]表示第 k 列右高左低斜线上没有皇后；
（3） 数组 c[ ]，c[k]表示第 k 列左高右低斜线上没有皇后；
棋盘中同一右高左低斜线上的方格，他们的行号与列号之和相同；同一左高右低斜线
上的方格，他们的行号与列号之差均相同。

初始时，所有行和斜线上均没有皇后，从第 1 列的第 1 行配置第一个皇后开始，在第
m 列 col[m]行放置了一个合理的皇后后，准备考察第 m+1 列时，在数组 a[
]、b[ ]和 c[ ]中为第 m 列，col[m]行的位置设定有皇后标志；当从第 m 列回溯到第
m-1 列，并准备调整第 m-1 列的皇后配置时，清除在数组 a[
]、b[ ]和 c[ ]中设置的关于第 m-1 列，col[m-1]行有皇后的标志。一个皇后在 m 列，
col[m]行方格内配置是合理的，由数组 a[ ]、b[ ]和 c[ ]对应位置的值都为 1 来确定。细节见
以下程序：
【程序】

include

include

define MAXN 20

int n,m,good;
9
int col[MAXN+1],a[MAXN+1],b[2MAXN+1],c[2MAXN+1];
void main()
{ int j;
char awn;
printf(“Enter n: “); scanf(“%d”,&n);
for (j=0;j<=n;j++) a[j]=1;
for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
m=1; col[1]=1; good=1; col[0]=0;
do {
if (good)
if (mn)
{ printf(“列\t 行”);
for (j=1;j<=n;j++)
printf(“%3d\t%d\n”,j,col[j]);
printf(“Enter a character (Q/q for exit)!\n”);
scanf(“%c”,&awn);
if (awn’Q’||awn==’q’) exit(0);
while (col[m]==n)
{ m–;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
else
{ a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
col[++m]=1;
}
else
{ while (col[m]==n)
{ m–;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
} while (m!=0);
}

试探法找解算法也常常被编写成递归函数，下面两程序中的函数 queen_all()和函数
queen_one()能分别用来解皇后问题的全部解和一个解。
【程序】

include

include

10

define MAXN 20

int n;
int col[MAXN+1],a[MAXN+1],b[2MAXN+1],c[2MAXN+1];
void main()
{ int j;
printf(“Enter n: “); scanf(“%d”,&n);
for (j=0;j<=n;j++) a[j]=1;
for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
queen_all(1,n);
}
void queen_all(int k,int n)
{ int i,j;
char awn;
for (i=1;i<=n;i++)
if (a[i]&&b[k+i]&&c[n+k-i])
{ col[k]=i;
a[i]=b[k+i]=c[n+k-i]=0;
if (kn)
{ printf(“列\t 行”);
for (j=1;j<=n;j++)
printf(“%3d\t%d\n”,j,col[j]);
printf(“Enter a character (Q/q for exit)!\n”);
scanf(“%c”,&awn);
if (awn’Q’||awn==’q’) exit(0);
}
queen_all(k+1,n);
a[i]=b[k+i]=c[n+k-i];
}
}

采用递归方法找一个解与找全部解稍有不同，在找一个解的算法中，递归算法要对当
前候选解最终是否能成为解要有回答。当它成为最终解时，递归函数就不再递归试探，立即
返回；若不能成为解，就得继续试探。设函数 queen_one()返回 1 表示找到解，返回 0 表示
当前候选解不能成为解。细节见以下函数。
【程序】

define MAXN 20

int n;
int col[MAXN+1],a[MAXN+1],b[2MAXN+1],c[2MAXN+1];
int queen_one(int k,int n)
{ int i,found;
i=found=0;
While (!found&&i { i++;
11
if (a[i]&&b[k+i]&&c[n+k-i])
{ col[k]=i;
a[i]=b[k+i]=c[n+k-i]=0;
if (k==n) return 1;
else
found=queen_one(k+1,n);
a[i]=b[k+i]=c[n+k-i]=1;
}
}
return found;
}
分支定界法：
分支限界法：
这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法，分枝定界法在搜索
解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度
优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此，可
以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得
多，因此当内存容量有限时，回溯法成功的可能性更大。
算法思想：分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法
的主要区别在于对 E-节点的扩充方式。每个活节点有且仅有一次机会变成 E-节点。当一个
节点变为 E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，
抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个
节点作为下一个 E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动
表为空，扩充过程才结束。
有两种常用的方法可用来选择下一个 E-节点（虽然也可能存在其他的方法）：

1. 先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活
   节点表的性质与队列相同。

2. 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找
   一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个 E-节点就是具有最小耗费
   的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个
   E-节点是具有最大收益的活节点
   装载问题
   用一个队列 Q 来存放活结点表，Q 中 weight
   表示每个活结点所相应的当前载重量。当
   weight＝－1 时，表示队列已达到解空间树
   同一层结点的尾部。
   算法首先检测当前扩展结点的左儿子结
   点是否为可行结点。如果是则将其加入到活
   结点队列中。然后将其右儿子结点加入到活
   结点队列中(右儿子结点一定是可行结点)。2
   个儿子结点都产生后，当前扩展结点被舍
   弃。
   活结点队列中的队首元素被取出作为
   当前扩展结点，由于队列中每一层结点之后
   都有一个尾部标记-1，故在取队首元素时，
   活结点队列一定不空。当取出的元素是-1
   时，再判断当前队列是否为空。如果队列非
   空，则将尾部标记-1 加入活结点队列，算法
   开始处理下一层的活结点。
   /该版本只算出最优解/
   #include<stdio.h>
   #include<malloc.h>
   struct Queue{
   int weight ;
   12
   struct Queue* next ;
   };
   int bestw = 0 ; // 目前的最优值
   Queue* Q; // 活结点队列
   Queue* lq = NULL ;
   Queue* fq = NULL ;
   int Add(int w)
   {
   Queue* q ;
   q = (Queue*)malloc(sizeof(Queue)) ;
   if(q NULL)
   {
   printf(“没有足够的空间分配\n”) ;
   return 1 ;
   }q->next = NULL ;
   q->weight = w ;
   if(Q->next == NULL)
   { Q->next = q ;
   fq = lq = Q->next ; //一定要使元素放到链
   中}
   else
   {
   lq->next = q ;
   lq = q ;
   // lq = q->next ;
   }
   return 0 ;
   }
   int IsEmpty()
   {
   if(Q->nextNULL)
   return 1 ;
   return 0 ;
   }
   int Delete(int&w)
   {
   Queue* tmp = NULL ;
   // fq = Q->next ;
   tmp = fq ;
   w = fq->weight ;
   Q->next = fq->next ; /一定不能丢了链表头
   /
   fq = fq->next ;
   free(tmp) ;
   return 0 ;
   }
   void EnQueue(int wt,
   int& bestw, int i, int n) //该函数负责加入
   活结点
   { // 如果不是叶结点，则将结点权值 wt 加
   入队列 Q
   if (i == n)
   { // 叶子
   if (wt>bestw)
   bestw = wt;
   }
   else
   Add(wt); // 不是叶子
   }
   int MaxLoading(int w[], int c, int n)
   { // 返回最优装载值
   // 为层次 1 初始化
   int err ; //返回值
   int i = 1; // 当前扩展结点的层
   int Ew = 0; // 当前扩展结点的权值
   bestw = 0; // 目前的最优值
   Q = (Queue)malloc(sizeof(Queue)) ;
   Q->next = NULL ;
   Q->weight = -1 ;
   err = Add(-1) ; //标记本层的尾部
   if(err)
   {
   return 0 ;
   }
   while (true)
   {
   // 检查左孩子结点
   if (Ew + w[i] <= c) // x[i] = 1
   EnQueue(Ew + w[i], bestw , i, n);
   // 右孩子总是可行的
   EnQueue(Ew, bestw, i, n); // x[i] = 0
   Delete(Ew); // 取下一个扩展结点
   if (Ew == -1)
   { // 到达层的尾部
   13
   if (IsEmpty())
   return bestw;
   if(i<n)
   Add(-1); // 同层结点的尾部
   Delete(Ew); // 取下一扩展结点
   i++; // 进入下一层
   }
   }}
   int main()
   {
   int n =0 ;
   int c = 0 ;
   int i = 0 ;
   int w ;
   FILE in , out ;
   in = fopen(“input.txt” , “r”) ;
   out = fopen(“output.txt” , “w”) ;
   if(inNULL||outNULL){
   printf(“没有输入输出文件\n”) ;
   return 1 ;
   }
   fscanf(in , “%d” , &n) ;
   fscanf(in , “%d” , &c) ;
   w = (int)malloc(sizeof(int)(n+1)) ;
   for(i =1 ; i<=n ; i++)
   fscanf(in , “%d” , &w[i]) ;
   MaxLoading(w , c , n) ;
   fprintf(out , “%d\n” , bestw) ;
   return 0 ;
   }
   算法设计与分析期末复习题（四）答案在下面
   一．填空题（每空2分，共30分）
   1．算法的时间复杂性指算法中 的执行次数。
   2．在忽略常数因子的情况下，O、和三个符号中， 提供了算法运行时间的一个上界。
   3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)= 。
   4．分治算法的时间复杂性常常满足如下形式的递归方程：

   其中，g(n)表示 。

5. 分治算法的基本步骤包括 。
   6．回溯算法的基本思想是 。
   7．动态规划和分治法在分解子问题方面的不同点是 。
   8．贪心算法中每次做出的贪心选择都是 最优选择。
   9．PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级越 。
   10．选择排序、插入排序和归并排序算法中， 算法是分治算法。
   11．随机算法的一个基本特征是对于同一组输入， 不同的运行可能得到 的结果。
   12.对于下面的确定性快速排序算法，只要在步骤3前加入随机化步骤 ，就可得到一个随机化快速排序算法，该随机化步骤的功能是 。
   算法 QUICKSORT
   输入：n个元素的数组A[1…n]。
   输出：按非降序排列的数组A中的元素。
6. quicksort(1, n)
   end QUICKSORT
   过程 quicksort(A, low, high)
   // 对A[low…high]中的元素按非降序排序。
7. if low<high then
8. w=SPLIT(A, low, high)
   //算法SPLIT以A[low]为主元将A[low…high]划分成两部 //分，返回主元的新位置。
9. quicksort (A, low, w-1)
10. quicksort (A, w+1, high)
    6． end if
    end quicksort
    13．下面算法的基本运算是 运算，该算法的时间复杂性阶为( )。
    算法 SPLIT
    输入：正整数n，数组A[1…n]。
    输出：…。
    i=1
    x=A[1]
    for j=2 to n
    if A[j]<=x then
    i=i+1
    if ij then A[i]A[j]
    end if
    end for
    A[i]A[1]
    w =i
    return w, A
    end SPLIT
    二．计算题和简答题（每小题7分，共21分）
    1．用O、、表示函数f与g之间阶的关系，并分别指出下列函数中阶最低和最高的函数：
    (1)　f (n)=100 g(n)=
    (2) f(n)=6n+n g(n)=3n
    (3) f(n)= n/logn-1 g(n)=
    (4) f(n)= g(n)=
    (5) f(n)= g(n)=
    2．下面是一个递归算法，其中，过程pro1和pro2的运算时间分别是1和。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用表示）。
    算法 EX1
    输入：正整数n，n=2k。
    输出：…
    ex1(n)
    end EX1
    过程 ex1(n)
    if n=1 then
    pro1(n)
    else
    pro2(n)
    ex1(n/2)
    end if
    return
    end ex1
    3．用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dk[i, j]表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。
    三．算法填空题（共34分）
    1．（10分）设n个不同的整数按升序存于数组A[1…n]中，求使得A[i]=i的下标i 。下面是求解该问题的分治算法。
    算法 SEARCH
    输入：正整数n，存储n个按升序排列的不同整数的数组A[1…n]。
    输出：A[1…n]中使得A[i]=i的一个下标i，若不存在，则输出 no solution。
    i=find ( (1) )
    if i>0 then output i
    else output “no solution”
    end SEARCH
    过程 find (low, high)
    // 求A[low…high] 中使得A[i]=i的一个下标并返回，若不存在，//则返回0。
    if (2) then return 0
    else
    mid=
    if (3) then return mid
    else
    if A[mid]<mid then
    return find( (4) )
    else
    return (5)
    end if
    end if
    end if
    end find
    2．(10分) 下面是求解矩阵链乘问题的动态规划算法。
    矩阵链乘问题：给出n个矩阵M1, M2, …, Mn , Mi 为riri+1阶矩阵，i=1, 2, …, n，求计算M1M2…Mn所需的最少数量乘法次数。
    记 Mi, j=MiMi+1…Mj , i<=j。设C[i, j], 1<=i<=j<=n, 表示计算Mi, j的所需的最少数量乘法次数，则

算法 MATCHAIN
输入：矩阵链长度n, n个矩阵的阶r[1…n+1], 其中r[1…n]为n个矩阵的行数，r[n+1]为第n个矩阵的列数。
输出：n个矩阵链乘所需的数量乘法的最少次数。
for i=1 to n C[i, i]= （1）
　for d=1 to n-1
for i=1 to n-d
　　　j= (2)
C[i, j]= ∞
for k=i+1 to j
x= (3)
if x<C[i, j] then
(4) =x
end if
end for
end for
end for
return (5)
end MATCHAIN
3．(14分) 下面是用回溯法求解马的周游问题的算法。
马的周游问题：给出一个nxn棋盘，已知一个中国象棋马在棋盘上的某个起点位置（x0, y0），求一条访问每个棋盘格点恰好一次，最后回到起点的周游路线。（设马走日字。）
算法 HORSETRAVEL
输入：正整数n，马的起点位置(x0, y0)，1<=x0, y0<=n 。
输出：一条从起点始访问nxn棋盘每个格点恰好一次，最后回到起点的周游路线；若问题无解，则输出no solution。
tag[1…n, 1…n]=0
dx[1…8]={2, 1, -1, -2, -2, -1, 1, 2}
dy[1…8]={1, 2, 2, 1, -1, -2, -2, -1}
flag=false
x=x0; y=y0 ; tag[x, y]=1
m=n*n
i=1; k[i]=0
while (1) and not flag
while k[i]<8 and not flag
k[i]= (2)
x1= x+dx[k[i]]; y1= y+dy[k[i]]
if ((x1,y1)无越界and tag[x1, y1]=0) or ((x1,y1)=(x0,y0) and i=m) then
x=x1; y=y1
tag[x, y]= (3)
if i=m then flag=true
else
i= (4)
(5)
end if
end if
end while
i=i-1
(6)
　 (7)
end while
if flag then outputroute(k) //输出路径
else output “no solution”　
end HORSETRAVEL
四．算法设计题（15分）
10. 一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为公里，0=，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。
《算法设计与分析》期考试卷(A)标准答案

一.填空题：

1. 元运算
2. O
4. 将规模为n的问题分解为子问题以及组合相应的子问题的解所需的时间
5. 分解，递归，组合
6. 在问题的状态空间树上作带剪枝的DFS搜索（或：DFS+剪枝）
7. 前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的
8. 局部
9. 高
10. 归并排序算法
11. 不同
12. v=random (low, high); 交换A[low]和A[v]的值
    随机选主元
13. 比较
    n

二.计算题和简答题：

1. 阶的关系：
   (1) f(n)= O(g(n))
   (2) f(n)=(g(n))
   (3) f(n)=(g(n))
   (4) f(n)= O(g(n))
   (5) f(n)=(g(n))
   阶最低的函数是：100
   阶最高的函数是：
2. 该递归算法的时间复杂性T(n)满足下列递归方程：

将n=, a=1, c=2, g(n)=, d=1代入该类递归方程解的一般形式得：
T(n)=1+=1+k-
=1+ k-=++1
所以，T(n)= ++1=。
3.

三.算法填空题：
1.(1) 1, n (2) low>high (3) A[mid]=mid
(4) mid+1, high (5) find(low, mid-1)
2. (1) 0 (2) i+d (3) C[i, k-1]+C[k, j]+r[i]*r[k]*r[j+1]
(4) C[i, j] (5) C[1, n]
3. (1) i>=1 (2)k[i]+1 (3) 1
(4) i+1 (5) k[i]=0 (6) tag[x, y]=0
(7) x=x-dx[k[i]]; y=y-dy[k[i]]

四.算法设计题：

1. 贪心选择策略：从起点的加油站起每次加满油后不加油行驶尽可能远，直至油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加满油。
   算法 MINSTOPS
   输入：A、B两地间的距离s，A、B两地间的加油站数n，车加满油后可行驶的公里数m，存储各加油站离起点A的距离的数组d[1…n]。
   输出：从A地到B地的最少加油次数k以及最优解x[1…k]（x[i]表示第i次加油的加油站序号），若问题无解，则输出no solution。
   d[n+1]=s; //设置虚拟加油站第n+1站。
   for i=1 to n
   if d[i+1]-d[i]>m then
   output “no solution”; return //无解，返回
   end if
   end for
   k=1; x[k]=1 //在第1站加满油。
   s1=m //s1为用汽车的当前油量可行驶至的地点与A点的距离
   i=2
   while s1<s
   if d[i+1]>s1 then //以汽车的当前油量无法到达第i+1站。
   k=k+1; x[k]=i //在第i站加满油。
   s1=d[i]+m //刷新s1的值
   end if
   i=i+1
   end while
   output k, x[1…k]
   MINSTOPS

最坏情况下的时间复杂性：Θ(n)
算法设计与分析期末复习题（五）
一、选择题
1．一个.java文件中可以有（ ）个public类。
A．一个 B．两个 C．多个 D．零个
2．一个算法应该是（ ）
A．程序 B．问题求解步骤的描述
C．要满足五个基本特性 D．A和C
3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（ ）
A．唯一性 B．有穷性 C．有0个或多个输入 D．有输出
4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（ ）

A．3，15，130，20，98，67 B．3，15，20，130，98，67
C．3，15，20，67，130，98 D．3，15，20，67，98，130
5．下列关于算法的描述，正确的是（ ）
A．一个算法的执行步骤可以是无限的 B．一个完整的算法必须有输出
C．算法只能用流程图表示 D．一个完整的算法至少有一个输入
6．Java Application源程序的主类是指包含有（ ）方法的类。
A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法
7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（ ）
A．分治法 B．减治法 C．蛮力法 D．变治法
8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。
A、import java.awt.* ; B、import java.applet.Applet ;
C、import java.io.* ; D、import java.awt.Graphics ;
9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。

图中空白处理框①和②处应填入的是（ ）
A．① sum ← sum + d B．① sum ← sum + c
② c ← c + 1 ② c ← c + 1
C．① sum ← sum + d D．① sum ← sum + c
② d ← d + 1 ② d ← d + 1
10．报名参加冬季越野赛跑的某班5位学生的学号是：5，8，11，33，45。利用折半查找，查找学号为33号学生的过程中，依次被访问到的学号是（ ）
A．5，11，33 B．8，33 C．11，45，33 D．11，33
11．表达式（short）8/9.2*5的值的类型为
A．short B． int C．double D．float
12． 设x为int型变量，则执行一下语句段后，x的值为
x=10;
x+=x-=x-x;
A．10 B．20 C．40 D．30
13．下列代码的执行结果是
public class StringTest{
public static void main(String args[]){
int a=4,b=6,c=8;
String s=”abc”;
System.out.println(a+b+s+c);
System.out.printin(); }
}
A．ababcc B．464688 C．46abc8 D．10abc8
14． 下列程序段执行后t3的结果是
int t1 = 2, t2 = 3, t3;
t3=t1<t2? t1:t2+t1
A．2 B．4 C．5 D．6
15．要计算当0〈x〈10时，y=x，应当使用的语句是
A．if(0<x<10)y=x; B．if(0<x|x<10)y=x; C．if(0<x&x<10)y=x; D．if(0<x^x<10)y=x;
16．对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下，
第一趟：2，12，16，88，5，10
第二趟：2，5，16，88，12，10
第三趟：2，5，10，88，12，16
则采用的排序方法是（ ）
A．冒泡排序 B．合并排序 C．快速排序 D．选择排序
17．类与对象的关系是（ ）
A． 建筑图纸和建筑物的关系 B． 汽车与发动机的关系
C． 人与黑人的关系 D． 没有关系
18．JAVA语言二维数组定义中，第二维的长度 ( )
A．可以不相等 B．必须相等
C．高维数组长度与低维数组长度相同 D．固定长度
19．算法必须具备（ ）这三个特性。
A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性
C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性
20．如下图所示，该流程图所表示的算法违背了算法的有穷性特征，下列修改方法中，可以改正该错误的是（ ）

A．将①处改为 i ← 0 B．将②处改为 s ≥ 0 ?
C．将③处改为 i ← i-2 D．将④处改为 s ← s-i

二、填空题
1．一个显而易见的事实是：大部分算法的执行时间随着 输入量的增加 而增大。
2．算法是 求解某一问题所使用的一系列清晰的指令 。
3．算法分析时间效率模型的基本数学公式是： T(n) ≈ CopC(n) 。
4．算法设计技术是 用算法解题的一般性方法 ，用于解决不同计算领域的多种问题。
5．三个渐进符号： O 、 Ω 和 Ө 。
6．效率分析框架主要关心一个算法的 基本操作次数的增长次数 ，并把它作为算法效率的主要指标。
7．Java源程序的文件名和程序中定义的 主类名 应保持一致，包括字母大小写的匹配。
8．算法中常见的问题类型包括： 排序 、 查找 、字符串处理和组合问题等。
9．类中的 构造 方法是一个特殊的方法，其名称与类名相同。
10．面向对象程序设计语言中的3个重要特性分别是 封装 、 继承 和 多态 。
11．Java源程序文件的扩展名为 java ，编译生成的字节码文件的扩展名为 class 。
12．大多数算法的效率可以分为常数、 对数 、线性、平方、 立方 和指数等。

三、简答题
1．什么是算法？算法的五个重要特征是什么？
答：算法是求解某一问题所使用的一系列清晰的指令。
答：
（1）输入：有零个或多个由外部提供的量作为算法的输入.
（2）输出：算法产生至少一个量作为输出.
（3）确定性：组成算法的每条指令是清晰的,无歧义的.
（4）有限性：在执行了有穷步骤后运算终止.
（5）可行性：运算都是基本运算，原理上能在有限时间内完成.

2．请简述蛮力算法的优点？
答：
蛮力算法是一种简单直接地解决问题的方法。蛮力法具有如下优点：(1)应用范围广；(2)不受实例规模的限制；(3)当要解决的问题实例不多,设计更高效算法的代价太大时可选用；(4)对解决一些小规模的问题实例仍然有效；(5)可作为衡量其他算法的参照物。

3．算法设计与分析过程的典型步骤都包括哪些？
答：
（1）了解问题的内容
（2）了解计算设备的性能
（3）在精确解法和近似解法之间选择
（4）确定适当的数据结构
（5）算法设计技术
（6）详细表述算法的方法
（7）证明算法的正确性
（8）分析算法
（9）为算法写代码

4．请简述分治法的基本思路？
答：
将规模为N的问题分解为k个规模较小的子问题，使这些子问题相互独立可分别求解，再将k个子问题的解合并成原问题的解。如子问题的规模仍很大，则反复分解直到问题小到可直接求解为止。
在分治法中,子问题的解法通常与原问题相同,自然导致递归过程。

5．请简述减治法的基本思路？
答：
减治技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系。一旦建立了这种关系，既可以从顶至底（递归地），也可以从底至顶（非递归地）来运用该关系。
减治法有三种主要的变种：
减常数(如1)：:每此迭代规模减小n→n-1
减因子(如1/2)：每此迭代规模减半n→ n/2
减可变规模：每此迭代减小的规模不同

6．请简述递归算法设计的基本思路？
答：
递归的执行过程由分解过程和求值过程两部分构成。
实际上, 递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决(此时分解到递归出口)。
但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。

7．请简述变治法的基本思路？
答：
变治法的技术基于变换思想。变治法分为两个阶段的工作：首先在“变”的阶段，出于这样或那样的原因，将问题的实例变得更容易求解；然后是“治”的阶段，对问题的实例进行求解。
根据对问题实例的变换方式不同，变治法有三种主要的类型：
（1）实例化简——变换为同样问题的一个更简单或者更方便的实例；
（2）改变表现——变换为同样实力的不同表现；
（3）问题化简——变换为另一个问题的实例，这种问题的算法是已知的。
8．请简述时空权衡法的基本思路？
答：
时空权衡法的基本思路是对问题的部分或全部输入做预处理，然后对得到的额外信息使用额外的存储空间来存储。通过实现更快或更方便的数据存取，以加速后面问题的求解来提高算法的效率。

四、算法实现题
1．对于任意非负整数n，计算阶乘函数F(n) = n！的值。因为当n ≥ 1时，n！= 1×2×3×……×（n-1）×n = (n-1)！×n。并且根据定义，0！= 1，所以可以使用下面的递归算法计算n！：F(n) = F(n-1) × n。
请编写Java应用程序，由键盘输入n的值，在屏幕上输出计算的n！的结果。
import java.io.*;
public class FN
{
static long f(int n)
{
long r = 1;
if(n != 0)
r = n * f(n-1);
return r;
}
public static void main(String args[]) throws IOException
{
//输入N的值
byte[] buf = new byte[10];
System.out.println(“请输入一个整数：”);
System.in.read(buf);
String str=new String(buf);
int n=Integer.parseInt(str.trim());
//计算N！的值
long result = f(n);
//输出结果
System.out.println(n + “!=” + result);
}
}

2．斐波那契数列：0，1，1，2，3，5，8，13，21，34，……
这个数列可以用一个简单的递推式和两个初始条件来定义：
当n > 1时，F(n) = F(n-1) + F(n-2)
F(0) = 0，F(1) = 1

请编写Java应用程序，由键盘输入n的值代表要生成斐波那契数列的项数，在屏幕上输出n项斐波那契数列。
import java.io.*;
public class Fb{
/斐波那契数列算法/
int f(int n){
int r;
if(n <= 1)
r = n;
else
r = f(n-1) + f(n-2);
return r;
}
public static void main(String args[]) throws IOException{
System.out.println(“请输入所求斐波那契数列的项数：”);
byte buf[] = new byte[20];
System.in.read(buf);
String t1 = new String(buf);
int n = Integer.parseInt(t1.trim());
Fb f1 = new Fb();
int b;
System.out.println(“输出包含” + n + “项的斐波那契数列：”);
for(int i = 0; i <= n; i++)
{
b = f1.f(i);
System.out.print(b + " ");
}
System.out.println();
}
}

3．编写基于Java语言的选择排序算法。
/***

• 功能：该算法用选择排序对给定的数组排序
• 输入：一个乱序的整数数组a[ ]
• 输出：升序排列的整数数组a[ ]
  ***/
  public void selectionSort (int a[ ])
  {
  int temp,min;
  for(int i=0;i<a.length-1;i++)
  {
  min = i;
  for(int j=i+1;j<a.length;j++)
  if(a[min] > a[j])
  min = j;
  temp = a[i];
  a[i] = a[min];
  a[min] = temp;
  }
  }

4．编写基于Java语言的冒泡排序算法。
/***

• 功能：该算法用冒泡排序对给定的数组排序
• 输入：一个乱序的整数数组a[ ]
• 输出：升序排列的整数数组a[ ]
  ***/
  public void bubbleSort(int a[ ])
  {
  int temp;
  for(int i=0;i<a.length-1;i++)
  for(int j=0;j<a.length-1-i;j++)
  if(a[j]>a[j+1])
  {
  temp = a[j+1];
  a[j+1] = a[j];
  a[j] = temp;
  }
  }

5．编写基于Java语言的顺序查找算法。
/***

• 功能：该算法实现顺序查找功能

• 输入：一个整数数组a[ ]和一个要查找的键值k

• 输出：如果在数组中找到k，则返回对应数组元素的下标；如果在数组中找不到k，则返回-1
  ***/
  public int seqSearch(int a[ ],int k)
  {
  int i = 0;
  while((i < a.length ) && ( a[i] != k ))
  i = i + 1;
  if( i < a.length)

    	return i;
    else
  
    	return -1;
  

}

6．编写基于Java语言的折半查找算法。
/***

• 功能：该算法实现折半查找功能
• 输入：一个已经按照升序排列好的整数数组a[ ]和一个要查找的键值k
• 输出：如果在数组中找到k，则返回对应数组元素的下标；如果在数组中找不到k，则返回-1
  ***/
  public int binarySearch(int a[ ], int k)
  {
  int low = 0;
  int upper = a.length - 1;
  while(low <= upper)
  {
  int mid = (low+upper) / 2;
  if(k == a[mid])
  return mid;
  else
  if(des < a[mid])
  upper = mid - 1;
  else
  low = mid + 1;
  }
  return -1;
  }

7．编写基于Java语言的字符串匹配算法。
/***

• 功能：该算法实现字符串匹配功能

• 输入：一个n个字符的字符串str代表一段文本
  一个m个字符的字符串key代表一个模式

• 输出：如果查找成功的话，返回文本的第一个匹配字符串中第一个字符的位置，
  否则返回-1
  ***/
  public int stringMatch(String str,String key)
  {
  int j;
  int n = str.length();
  int m = key.length();

    for(int i = 0; i <= (n - m); i++)
    {
    	j = 0;
    	while((j < m) && (key.charAt(j) == str.charAt(i+j)))
    	{
    		j = j + 1;
    		System.out.println(i + "," + j);
    		if(j == m)
    			return i;
    	}
    }
    return -1;
  

}

8．编写基于Java语言的直接插入排序算法。
/***

• 功能：该算法用直接插入排序对给定的数组排序
• 输入：一个乱序的整数数组a[ ]
• 输出：升序排列的整数数组a[ ]
  ***/
  public void insertSort (int a[ ])
  {
  int temp,i,j;
  for(i=1;i<a.length;i++)
  {
  temp=a[i];
  j=i-1;
  while(j>=0 && a[j]>=temp)
  {
  a[j+1]=a[j];
  j–;
  }
  a[j+1]=temp;
  }
  }
  算法设计与分析期末复习题（六）
  1、用计算机求解问题的步骤：
  1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制
  2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程
  3、算法的三要素
  1、操作2、控制结构3、数据结构
  算法具有以下5个属性：
  　有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
  　确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
  　可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
  　输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
  　输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
  算法设计的质量指标：
  　　正确性：算法应满足具体问题的需求；
  　　可读性：算法应该好读，以有利于读者对程序的理解；
  　　健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
  　　效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。

经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法

迭代法
基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。
2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量
3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。
　
　　写成递归函数有：
　　int fib(int n)
　　{ if (n0) return 0;
　　if (n1) return 1;
　　if (n>1) return fib(n-1)+fib(n-2);
　　}

一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第 12 个月时，该饲养场共有兔子多少只？
Main()
{int I,a=1,b=1;
Print(a,b);
For(i=1;i<=10;i++)
{
C=a+b;
Print©;
A=b;
B=c;
}
}

分而治之法
1、基本思想
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
3、分治法的基本步骤
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
（3）合并：将各个子问题的解合并为原问题的解。

贪婪法
基本思想：以逐步的局部最优，达到最终的全局最优。无后效性

【问题】 背包问题
问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

#include<stdio.h>
void main()
{
int m,n,i,j,w[50],p[50],pl[50],b[50],s=0,max;
printf(“输入背包容量m,物品种类n :”);
scanf(“%d %d”,&m,&n);
for(i=1;i<=n;i=i+1)
{
printf(“输入物品的重量W和价值P :”);
scanf(“%d %d”,&w[i],&p[i]);
pl[i]=p[i];
s=s+w[i];
}
if(s<=m)
{
printf(“whole choose\n”);
//return;
}
for(i=1;i<=n;i=i+1)
{
max=1;
for(j=2;j<=n;j=j+1)
if(pl[j]/w[j]>pl[max]/w[max])
max=j;
pl[max]=0;
b[i]=max;
}
for(i=1,s=0;s<m && i<=n;i=i+1)
s=s+w[b[i]];
if(s!=m)
w[b[i-1]]=m-w[b[i-1]];
for(j=1;j<=i-1;j=j+1)
printf(“choose weight %d\n”,w[b[j]]);

}
动态规划
基本思想：把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。前一个子问题的解为后一个子问题的求解提供了有用的信息。在求解任何一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是问题的解。
基本步骤
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
回溯法
基本思想：按照深度优先策略，从根结点出发搜索解空间。算法搜索至解空间的任一结点时总是先判断该结点是否问题的约束条件。如果满足进入该子树，继续按深度优先的策略搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法
基本步骤：
1、确定问题的解空间：应用回溯法时，首先应明确定义问题的解的空间。问题的解空间应至少包含问题的一个解。
2、确定结点的扩展规则
3、搜索解空间：从开始结点出发，以深度优先的方式搜索整个解空间。
【问题】 n皇后问题
分支限界法
基本思想： 分支限界法是由“分支”和“限界”两部分组成。“分支”策略体现在对问题空间是按广度优先的策略进行搜索“限界”策略是为了加速搜索速度面采用启发信息剪枝策略。
可能会让画出“子集树斩图”235页例题及图好好看一下。
整理不易喜欢的点个赞呗！