试证明：10n的平方-2n=Θ（n的平方）

2.为什么用分治法设计的算法一般有递归调用?

答：子问题的规模很大时，必须继续使用分治法，反复分治，必然要用到递归。

3.衡量一个算法优劣的主要性能标准有哪些？能否用程序的运行时间作为算法的时间复杂度？为什么？

答：衡量一个算法优劣的主要性能指标有算法的时间复杂度和空间复杂度。因为程序的运行实现除了与算法有关，还与问题规模、特定的输入和计算机软硬件环境有关（编译程序，编程语言，CPU运算速度的快慢，内存空间的大小，等等）有关。

4.分治法的适用一条件是什么？

答：问题能够按照某种方式分解成若干个规模较小的子问题，相互独立且与原问题类型相同的子问题；第二，子问题足够小时，可以直接求解；第三，能将子问题的解组合成原问题的解。

5.程序与算法的联系和区别是什么？

答：联系：用某种程序设计语言来描述算法，得到的就是程序。区别：算法必须终止，程序可以不终止。

6.什么是递归算法，递归模型由那两个部分组成？

答：递归算法是指直接或者间接调用自身的算法。递归模型由递归出口和递归体两个部分组成。

7.简答题：
三分搜索算法的做法是：它先将待查元素x与n/3处的元素比较，然后将x与2n/3处的元素进行比较。比较的结果或者找到x，或者将搜索范围缩小到原来的n/3.

(1)编写c++程序实现算法；

（2）分析算法的时间复杂度

答：

int Search3(int a[],int left,int right,int x)   /*递归算法*/{int l,u;if(left<=right){l=left+(right-left+1)/3;u=left+(right-left+1)*2/3;if(x==a[u])return u;else if(x==a[l])return l;else if(x>a[u])return Search3(a, u+1, right, x);else if(x>a[l])return Search3(a, l+1, u-1,x);else       return Search3(a, left, l-1,x);}return -1;}void main(){int n,*a;int x,i;cout<<"Please input n:";cin>>n;a=new int[n];                             //动态数组int location=-1;for(i=0;i<n;i++){a[i]=i+1;}cout<<"Please input the search x:";cin>>x;cout<<endl<<Search3(a, 0, n-1,x)<<endl;}void main()                                       /*非递归算法*/{int a[15];int x,i;int location=-1;for(i=0;i<15;i++){a[i]=i+1;}cin>>x;i=0;int j=14,l,u;while(i<=j){l=i+(j-i)/3;u=i+(j-i)*2/3;if(x==a[u]){location=u;break;}else if(x==a[l]){location=l;break;}else if(x>a[u])i=u+1;else if(x<a[l])j=l-1;else     {i=l+1;j=u-1;}}cout<<location<<endl; //x的位置}

8.什么是算法的有穷性，能行性？

什么是程序的健壮性？

答：算法的有穷性指令有限个，且每条指令的执行时间也是有限的；

算法的能行性是指算法的每条指令都是可以执行的且算法执行之后可以得到预期的结果。

程序的健壮性是指当输入不合法数据时，程序应该能做适当的处理而不至于引起严重的后果。

9.贪心法和动态规划法有何异同？

答：他们都有最优子结构性质，可以多步决策。

不一样的地方：贪心法：自顶向下，最优量度标准，原问题的解不依赖于子问题的解，并且每一步的选择依赖于局部和以前的选择。

动态规划法是自底向上的，而且子问题具有重叠性，原问题的解依赖于子问题的解，每一步的选择依赖于子问题的解。

10：简述动态规划法与贪心法、贪心法的异同？

正确答案：
动态规划法与分治法异同比较

同:

将较大问题分解为较小的同类子问题

原问题的解依赖于子问题的解

异:

分治法:子问题相互独立

动态规划法:子问题重叠

动态规划法与贪心法异同比较

同:

具有最优子结构特性

多步决策

异:

贪心法:

自顶向下

最优量度标准

原问题的解不依赖于子问题的解.

每一步的选择依赖于局部和以前的选择

动态规划法:

自底向上

子问题的重叠性

原问题的解依赖于子问题的解

每一步的选择依赖于子问题的解

二、填空题：

广度优先生成节点，并使用剪枝函数的方法称为：分支限界法

13.深度优先生成节点，并使用剪枝函数的方法称为回溯法。

14问题求解的过程分为如下四步：

理解问题，设计方案、实现方案、回顾检查。

15.NP类问题是指目前还没有找到多项式时间算法的问题的集合。

16.回溯法的效率分析的常用方法是：蒙特卡洛法

17.算法是特定问题求解步骤的描述；对特定问题求解步骤的一种描述。
是指令的有限序列，用来将输入数据转换为输出结果。

18.在最优化问题中，使目标函数取极值的解称为问题的最优解。

19.一般地，一个递归模型是由递归出口和递归体两部分组成的，前者确定递归何时结束，后者确定递归求解时的递推关系。

20.深度优先生成状态空间树中的结点，并使用剪枝函数的方法成为回溯法。

21.通常，剪枝函数有两类，用于剪去不含最优答案结点的子树的是限界函数。

22. (填空题)
    运用回溯法解题的关键要素有以下三点：

(1) 针对给定的问题，定义问题的解空间；

(2) 确定易于搜索的解空间结构；

(3) 以深度优先方式搜索解空间，并且在搜索过程中用_剪枝_____函数避免无效搜索。

24.在使用动态规划法求解最长公共子序列问题时，需定义一个二维数组来保存最长公共子序列长度，设c[i][j] 保存Xi(x1,x2,…xi) 和 Yj = (y1,y2…yj)的最长公共子序列的长度，那么i=0或者j=0，c[i][j] = 0 若xi=yi(i,j>0) 则c[i][j] = c[i-1][j-1]+1 xi ≠yj(i,j>0),则c[i][j]=_ max(c[i-1][j],c[i][j-1])_________ 。

25.在使用动态规划法求解矩阵连乘问题的时，需定义一个二维数组来保存矩阵连乘时所需的最少运算量， 设m[i][j] 保存Ai*Ai+1…Aj所需的最少数乘次数…那么,当i=j时,m[i][j]= 0 ; 若i<j,则m[i][j]= min{m[i][k]+m[k+1][j]+pi×pk×pj}

26. 回溯法中，用于规定每个xi 的取值的约束条件称为 显式约束，对给定的一个问题实例，显式约束规定了问题所有候选解集，该候选解集被称为该问题实例的解空间。

27. 设有背包问题实例，n=7，(w0,w1,w2,w3,w4,w5,w6)=(2,3,5,7,1,4,1)，(p0,p1,p2,p3,p4,p5,p6)=(
    10,5,15,7,6,18,3)，M=15。求这一实例的最优解及最大收益.

答： 明白了，您想用贪心算法来解决背包问题，基于物品的利润/重量比。我们来按照这种方法重新计算您的答案。

问题分析

给定背包容量 (M = 15)，物品按利润/重量比排序为：

• 物品 4: 重量 (w_4 = 1)，利润 (p_4 = 6)，利润/重量比为 ( \frac{p_4}{w_4} = 6 )
• 物品 0: 重量 (w_0 = 2)，利润 (p_0 = 10)，利润/重量比为 ( \frac{p_0}{w_0} = 5 )
• 物品 5: 重量 (w_5 = 4)，利润 (p_5 = 18)，利润/重量比为 ( \frac{p_5}{w_5} = 4.5 )
• 物品 2: 重量 (w_2 = 5)，利润 (p_2 = 15)，利润/重量比为 ( \frac{p_2}{w_2} = 3 )
• 物品 6: 重量 (w_6 = 1)，利润 (p_6 = 3)，利润/重量比为 ( \frac{p_6}{w_6} = 3 )
• 物品 1: 重量 (w_1 = 3)，利润 (p_1 = 5)，利润/重量比为 ( \frac{p_1}{w_1} = 1.67 )
• 物品 3: 重量 (w_3 = 7)，利润 (p_3 = 7)，利润/重量比为 ( \frac{p_3}{w_3} = 1 )

按利润/重量比降序排列，物品顺序是：4, 0, 5, 2, 6, 1, 3。

贪心算法的实现

我们使用贪心算法，逐步选择物品，直到背包满为止。如果背包无法容纳一个物品的全部重量，我们将取物品的部分（分数物品），直到背包满。

物品 4：

• 重量 = 1，利润 = 6，剩余容量 = 15
• 放入物品 4，背包剩余容量 (15 - 1 = 14)，总利润 = 6

物品 0：

• 重量 = 2，利润 = 10，剩余容量 = 14
• 放入物品 0，背包剩余容量 (14 - 2 = 12)，总利润 = 6 + 10 = 16

物品 5：

• 重量 = 4，利润 = 18，剩余容量 = 12
• 放入物品 5，背包剩余容量 (12 - 4 = 8)，总利润 = 16 + 18 = 34

物品 2：

• 重量 = 5，利润 = 15，剩余容量 = 8
• 放入物品 2，背包剩余容量 (8 - 5 = 3)，总利润 = 34 + 15 = 49

物品 6：

• 重量 = 1，利润 = 3，剩余容量 = 3
• 放入物品 6，背包剩余容量 (3 - 1 = 2)，总利润 = 49 + 3 = 52

物品 1：

• 重量 = 3，利润 = 5，剩余容量 = 2
• 背包剩余容量不足以容纳整个物品 1，但可以部分放入：
  • 物品 1 的部分放入，占用剩余的 2 单位容量，利润为：( \frac{2}{3} \times 5 = 3.33 )
• 总利润 = 52 + 3.33 = 55.33

物品 3：

• 重量 = 7，利润 = 7，剩余容量 = 0
• 背包已满，无法放入物品 3。

最终解

• 最终总利润 = 55.33
• 物品放入顺序为：物品 4、物品 0、物品 5、物品 2、物品 6，以及物品 1 的一部分。

结论

按照利润/重量比排序后的贪心算法最大利润为 55.33。 .

28.请用动态规划法求解：给定字符串A=“xzyzzyx”和B=“zxyyzxz”，求A和B的最长公共子序列长度，并给出一个最长公共子序列。（10分）

（要求：从上到下，从左往右计算C矩阵，依据C矩阵，求得最长公共子序列）

以下是使用动态规划法求解给定字符串 A = "xzyzzyx" 和 B = "zxyyzxz" 的最长公共子序列长度以及找出一个最长公共子序列的详细步骤：

1. 构建动态规划矩阵 C

设 A 的长度为 m，B 的长度为 n。这里 m = 7，n = 7。创建一个 (m + 1)×(n + 1) 大小的二维数组 C，用于保存中间结果，其中 C[i][j] 表示 A 的前 i 个字符组成的子串与 B 的前 j 个字符组成的子串的最长公共子序列长度。

初始化边界条件：

• 当 i = 0 或者 j = 0 时（即有一个子串为空串），C[i][j] = 0。

然后按照从上到下、从左到右的顺序来填充矩阵 C，对于 i > 0 且 j > 0 的情况，根据以下规则来计算 C[i][j]：

• 如果 A[i - 1] == B[j - 1]（注意这里索引要减 1，因为字符串索引从 0 开始，而矩阵 C 的行列是从 1 开始计数用于表示空串等边界情况），那么 C[i][j] = C[i - 1][j - 1] + 1。
• 如果 A[i - 1]!= B[j - 1]，则 C[i][j] = max(C[i - 1][j], C[i][j - 1])。

以下是具体计算 C 矩阵的过程：

	“”	“z”	“x”	“y”	“y”	“z”	“x”
“”	0	0	0	0	0	0	0
“x”	0	0	1	1	1	1	1
“z”	0	1	1	1	1	2	2
“y”	0	1	1	2	2	2	2
“z”	0	1	1	2	2	3	3
“z”	0	1	1	2	2	3	3
“y”	0	1	1	2	3	3	3
“x”	0	1	1	2	3	3	4

例如，计算 C[3][3]（对应 A 的前 3 个字符 "xzy" 和 B 的前 3 个字符 "zxy"）：

• 因为 A[2]（即 y）不等于 B[2]（即 y），所以 C[3][3] = max(C[2][3], C[3][2]) = max(1, 1) = 1。

再比如，计算 C[7][7]（对应整个 A 和 B 字符串）：

• 因为 A[6]（即 x）等于 B[6]（即 x），所以 C[7][7] = C[6][6] + 1 = 3 + 1 = 4。

2. 最长公共子序列长度

通过上述计算，C[m][n]（这里 m = 7，n = 7）的值就是字符串 A 和 B 的最长公共子序列长度，即 4。

3. 求一个最长公共子序列（通过回溯 C 矩阵来获取）

从矩阵 C 的右下角 C[m][n] 开始回溯，根据以下规则来构建最长公共子序列：

• 如果 C[i][j] = C[i - 1][j - 1] + 1 且 A[i - 1] == B[j - 1]，那么说明当前字符是最长公共子序列中的一部分，将其加入结果序列，然后向左上移动，即 i--，j--。
• 如果 C[i][j] = C[i - 1][j]，则向上移动，即 i--。
• 如果 C[i][j] = C[i][j - 1]，则向左移动，即 j--。

以下是回溯过程：

• 从 C[7][7] = 4 开始，因为 C[7][7] = C[6][6] + 1 且 A[6] = B[6] = "x"，所以最长公共子序列的一个字符是 "x"，然后移动到 C[6][6]。
• 对于 C[6][6]，因为 C[6][6] = C[5][5] + 1 且 A[5] = B[5] = "z"，所以最长公共子序列再加入字符 "z"，接着移动到 C[5][5]。
• 对于 C[5][5]，因为 C[5][5] = C[4][4] + 1 且 A[4] = B[4] = "y"，所以最长公共子序列再加入字符 "y"，接着移动到 C[4][4]。
• 对于 C[4][4]，因为 C[4][4] = C[3][3] + 1 且 A[3] = B[3] = "z"，所以最长公共子序列再加入字符 "z"，此时到达左上角，回溯结束。

得到的一个最长公共子序列为 "zyzx"。

综上，字符串 A 和 B 的最长公共子序列长度为 4，一个最长公共子序列是 "zyzx"。

29.请用动态规划法求解：设有4 个矩阵连乘积A0A1A2A3：A0: 53, A1: 34, A2: 42, A3: 25, ,请求出它们的最少数乘计算量和最优计算次序。

要求：计算出m和矩阵和s矩阵

我们可以通过 矩阵链乘法（Matrix Chain Multiplication）问题的动态规划方法来求解这个问题。给定四个矩阵连乘 ( A_0, A_1, A_2, A_3 )，矩阵的维度分别为：

• ( A_0 ): ( 5 \times 3 )
• ( A_1 ): ( 3 \times 4 )
• ( A_2 ): ( 4 \times 2 )
• ( A_3 ): ( 2 \times 5 )

步骤 1: 定义状态和矩阵

我们用两个矩阵来存储动态规划的结果：

1. m 矩阵：( m[i][j] ) 表示从矩阵 ( A_i ) 到矩阵 ( A_j ) 之间的最小标量乘积数。
2. s 矩阵：( s[i][j] ) 表示计算最优的矩阵链乘积时，矩阵分割的位置。这个矩阵用于恢复最优的矩阵计算顺序。

步骤 2: 维度数组

首先我们需要构建一个维度数组 ( p ) 来表示矩阵的维度。由于矩阵的维度是 ( A_0: 5 \times 3 ), ( A_1: 3 \times 4 ), ( A_2: 4 \times 2 ), ( A_3: 2 \times 5 )，我们可以得到维度数组：

[
p = [5, 3, 4, 2, 5]
]

其中：

• ( p_0 = 5 ) 表示 ( A_0 ) 的行数
• ( p_1 = 3 ) 表示 ( A_0 ) 的列数（同时是 ( A_1 ) 的行数）
• ( p_2 = 4 ) 表示 ( A_1 ) 的列数（同时是 ( A_2 ) 的行数）
• ( p_3 = 2 ) 表示 ( A_2 ) 的列数（同时是 ( A_3 ) 的行数）
• ( p_4 = 5 ) 表示 ( A_3 ) 的列数

步骤 3: 初始化矩阵

矩阵 ( m ) 和 ( s ) 都是 ( 4 \times 4 ) 的矩阵，因为我们有 4 个矩阵，索引从 1 到 4。首先初始化 ( m ) 和 ( s )：

• 对于 ( m[i][i] = 0 )（即矩阵链只有一个矩阵时，不需要乘法）
• 对于 ( s[i][i] = 0 )（初始时没有分割）

步骤 4: 填充动态规划表

动态规划的递推关系是：
对于任意 ( i ) 和 ( j )，我们选择一个 ( k ) 来分割矩阵链，使得 ( i \leq k < j )，并计算其最小值：

[
m[i][j] = \min { m[i][k] + m[k+1][j] + p[i-1] \times p[k] \times p[j] }
]

步骤 5: 计算结果

我们开始计算最小标量乘积数，并在过程中更新矩阵 ( m ) 和 ( s )。

初始化

( m ) 和 ( s ) 初始化为：

m =    s =
[ [ 0, ∞, ∞, ∞ ],  [ [ 0,  0,  0,  0 ],[ ∞,  0, ∞, ∞ ],    [ 0,  0,  0,  0 ],[ ∞, ∞,  0, ∞ ],    [ 0,  0,  0,  0 ],[ ∞, ∞, ∞,  0 ] ]  [ 0,  0,  0,  0 ]]

填充 ( m ) 和 ( s )（从矩阵链长度 2 到 4）

1. 链长 = 2：我们计算长度为 2 的子问题，即计算 ( m[i][i+1] )。

   • i = 1, j = 2: ( m[1][2] = p_0 \times p_1 \times p_2 = 5 \times 3 \times 4 = 60 )
     • 所以 ( m[1][2] = 60 )，并且 ( s[1][2] = 1 )。
   • i = 2, j = 3: ( m[2][3] = p_1 \times p_2 \times p_3 = 3 \times 4 \times 2 = 24 )
     • 所以 ( m[2][3] = 24 )，并且 ( s[2][3] = 2 ).
   • i = 3, j = 4: ( m[3][4] = p_2 \times p_3 \times p_4 = 4 \times 2 \times 5 = 40 )
     • 所以 ( m[3][4] = 40 )，并且 ( s[3][4] = 3 ).

2. 链长 = 3：我们计算长度为 3 的子问题，即计算 ( m[i][i+2] )。

   • i = 1, j = 3: 我们需要考虑分割位置 ( k = 1 ) 和 ( k = 2 )。

     • 如果 ( k = 1 )，那么 ( m[1][3] = m[1][1] + m[2][3] + p_0 \times p_1 \times p_3 = 0 + 24 + 5 \times 3 \times 2 = 54 )。
     • 如果 ( k = 2 )，那么 ( m[1][3] = m[1][2] + m[3][3] + p_0 \times p_2 \times p_3 = 60 + 0 + 5 \times 4 \times 2 = 140 )。
     • 所以 ( m[1][3] = 54 )，并且 ( s[1][3] = 1 )。

   • i = 2, j = 4: 我们需要考虑分割位置 ( k = 2 ) 和 ( k = 3 )。

     • 如果 ( k = 2 )，那么 ( m[2][4] = m[2][2] + m[3][4] + p_1 \times p_2 \times p_4 = 0 + 40 + 3 \times 4 \times 5 = 80 )。
     • 如果 ( k = 3 )，那么 ( m[2][4] = m[2][3] + m[4][4] + p_1 \times p_3 \times p_4 = 24 + 0 + 3 \times 2 \times 5 = 54 )。
     • 所以 ( m[2][4] = 54 )，并且 ( s[2][4] = 3 ).

3. 链长 = 4：我们计算整个矩阵链 ( m[1][4] )。

   • i = 1, j = 4: 我们需要考虑分割位置 ( k = 1, 2, 3 )。
     • 如果 ( k = 1 )，那么 ( m[1][4] = m[1][1] + m[2][4] + p_0 \times p_1 \times p_4 = 0 + 54 + 5 \times 3 \times 5 = 90 )。
     • 如果 ( k = 2 )，那么 ( m[1][4] = m[1][2] + m[3][4] + p_0 \times p_2 \times p_4 = 60 + 40 + 5 \times 4 \times 5 = 140 )。
     • 如果 ( k = 3 )，那么 ( m[1][4] = m[1][3] + m[4][4] + p_0 \times p_3 \times p_4 = 54 + 0 + 5 \times 2 \times 5 = 64 )。
     • 所以 ( m[1][4] = 64 )，并且 ( s[1][4] = 3 )。

步骤 6: 最终结果

• 最小标量乘积数：( m[1][4] = 64 )