算法复习资料整理.docVIP

1.计算题 2.使用分治算法找一组数的最大最小数。采用如下设计思想： （1）将数据集 S 均分为 S1 和 S2；（2）求解 S1 和 S2 中的最大和最小值；（3）最终的最大和最小值可以计算得到：min( S1, S2 ), max( S1, S2 )；（4）采用同样的处理方法递归处理 S1 和 S2。 Ackerman 函数 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=2 t= 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 个独立作业 { 1，2，3，4，5，6，7 }由 3 台相同的机器 M1，M2，M3 加工处理。各作业所需的处理时间分别为{ 2，14，4，16，6，5，3 }。贪心算法产生作业调度 作业数 n = 7 机器数 m = 3 所需的加工时间为 17 9.回溯法有哪些信誉好的足球投注网站排列树的算法 void Backtrack ( int t ) { if ( t n ) output( x ); { else for ( int i = t; i = n; i++ ) { swap( x[ t ], x[ i ] ); if ( Constraint( t ) Bound( t ) ) Backtrack( t + 1 ); swap( x[ t ], x[ i ] ); } } } 10.给定 0/1 背包问题，参数为：n = 3, w = [ 16, 15, 15 ], p = [ 45, 25, 25 ], c = 30。用队列式分支限界法求解此问题 处理法则:价值大者优先。{}—{A}—{B,C}—{C，D，E}—{C，E}—{C，J，K}—{C}—{F，G}—{G，L，M}—{G，M}—{G}—{N，O}—{O}—{}