1.计算题。
2.使用分治算法找一组数的最大最小数。采用如下设计思想：
1）将数据集 s 均分为 s1 和 s2；（2）求解 s1 和 s2 中的最大和最小值；（3）最终的最大和最小值可以计算得到：min( s1, s2 ),max( s1, s2 )；4）采用同样的处理方法递归处理 s1 和 s2。
函数 a(n，m) 有 2 个独立的整型变量 m >=0 和 n >=0
a( 3，2 ) 2 ^ 3 = 8
4.证明题：
5.利用动态规划法设计如下的矩阵连乘最小次数问题，写出动态规划法求解过程。
a1：40×25 a2：25×25 a3：25×15
m[0][0]=m[1][1] =m[2][2] =m[3][3]=0
r=2 i=1 j=2
m[1][2]=40*25*10=10000
i=2 j=3
m[2][3]= 25*10*15=3750
r=3 i=1 j=3
m[1][3]= m[1][1]+ m[2][3]+ 40*25*15=18750
k=2t= m[1][2]+ m[3][3]+ 40*10*15=16000
m[1][3]=t=16000
6.有一个箱子容量为 v（正整数），同时有 n 个物品，每个物品有一个体积（正整数）。要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
编写程序实现，自定义输入和输出。
提示】使用二维数组 f[ i ][j ],表示前 i 个物品装入容量为 j 的箱子能获得的最大体积，则状态转移方程：
f[ i ][j ] max( f[ i - 1 ][j ],f[ i -1 ][j - a[ i ] a[ i ]
7.证明下述问题具有“贪心选择性质”和“最优子结构性质。
8.设 7 个独立作业 由 3 台相同的机器 m1，m2，m3 加工处理。各作业所需的处理时间分别为。贪心算法产生作业调度。
作业数 n = 7 机器数 m = 3
所需的加工时间为 17
9.回溯法搜索排列树的算法。
void backtrack ( int t )
if ( t > n ) output( x );
10.给定 0/1 背包问题，参数为：n = 3, w = 16, 15, 15 ],p = 45, 25, 25 ],c = 30。用队列式分支限界法求解此问题。
处理法则：价值大者优先。{}
11.给定无向图 g 如下所示，试给出图 g 的一个最大团。
1，2，5 }、和 是 g 的最大团。
“算法设计与分析”复习整理参考
算法设计与分析 课程基本概念复习参考。1 什么是算法？算法有哪些基本特征？请指出算法同程序的相同点与不同点。答 算法是指解决问题的方法和过程。算法的基本特征。1 输入 有零个输入或者 多个外部量作为算法的输入 2 输出 算法产生出一个量作为输出 3 确定性 组成算法的每条指令是清晰地，无歧义的 4 ...
算法基础笔记整理
算法重点总结。一 引言 算法基本概念。1.什么是算法 有限指令序列，对某个问题能够得出正确答案的规则集合。2.算法的特点 确定性，可终止性，可行性，输入，输出。3.算法规模 问题实例的大小，输入的大小。4.基本运算 主要的 关键的 耗时的最小操作。5.算法正确性及复杂度证明方法 反证法 数学归纳法 ...
2019算法复习
1 有0 1背包问题如下 n 3，c 30，p 45，25，25 w 16，15，15 用队列式 优先队列式分支限界法求最优解。画解空间树并详细描述求解过程 解 队列式分支限界法 a b,c b,c b,c d,e e c,e f,g f,g e,f,g j,k k 45 1,0,0 f,g l,m...