下载文档原格式
计算机算法设计和分析习题及答案解析This manuscript was revised on November 28, 2020《计算机算法设计与分析》习题及答案一．选择题1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（A ）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4. 回溯法解旅行售货员问题时的解空间树是（ A ）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树5．下列算法中通常以自底向上的方式求解最优解的是（B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法6、衡量一个算法好坏的标准是（ C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短7、以下不可以使用分治法求解的是（ D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题8. 实现循环赛日程表利用的算法是（A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法9．下面不是分支界限法搜索方式的是（D ）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法11.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法D、回溯法12．哈夫曼编码的贪心算法所需的计算时间为（B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。
A、最小堆B、最大堆C、栈D、数组14．最长公共子序列算法利用的算法是（B）。
A、分支界限法B、动态规划法C、贪心法D、回溯法15．实现棋盘覆盖算法利用的算法是（A ）。
A、分治法B、动态规划法C、贪心法D、回溯法16.下面是贪心算法的基本要素的是（C ）。
算法分析作业 IMB standardization office【IMB 5AB- IMBK 08- IMB 2C】算法分析练习题（一）一、选择题1、二分搜索算法是利用（A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（A ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3．下列算法中通常以自底向上的方式求解最优解的是（B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法4、衡量一个算法好坏的标准是（C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短5、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题6. 实现循环赛日程表利用的算法是（A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法7.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法D、回溯法8．最长公共子序列算法利用的算法是（B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法9．实现棋盘覆盖算法利用的算法是（A ）。
A、分治法B、动态规划法C、贪心法D、回溯法10. 矩阵连乘问题的算法可由（B）设计实现。
A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法11、Strassen矩阵乘法是利用（A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法12、使用分治法求解不需要满足的条件是（A ）。
A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解13、下列算法中不能解决0/1背包问题的是（A ）A 贪心法B 动态规划C 回溯法D 分支限界法14．实现合并排序利用的算法是（A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法15．下列是动态规划算法基本要素的是（D ）。
A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质16．下列算法中通常以自底向下的方式求解最优解的是（B ）。
第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。
若f=Ο(g)，则必然存在常数c1>0和n0，使得∀n≥n0，有f≤c1*g(n)。
由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。
必要性。
同理，若g=Ω(f)，则必然存在c2>0和n0，使得∀n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。
2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得∀n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。
由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。
3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。
证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得∀n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。
4）log(n!)= Θ(nlogn)证明：∙由于log(n!)=∑=n i i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。
∙由于对所有的偶数n 有，log(n!)= ∑=n i i 1log ≥∑=n n i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。
当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得∀n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。
1、硬币面值组合描述使用1角、2角、5角硬币组成n 角钱。
设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。
输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。
输入一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。
输出输出有若干行，每行的形式为：i a b c第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。
样例输入样例输出源代码：#include<stdio.h>#include<stdlib.h>int main(){int t=1;int i,j,k;int n;scanf("%d",&n);int A=n,B=n/2,C=n/5;for(i=0;i<=C;i++){for(j=0;j<=B;j++){for(k=0;k<=A;k++){if(i*5+j*2+k*1==n){printf("%03d%12d%12d%12d\n",t,k,j,i);t++;}}}}getchar();return 0;}2、比赛排名描述5名运动员参加100米赛跑，各自对比赛结果进行了预测：A说：E是第1名。
B说：我是第2名。
C说：A肯定垫底。
D说：C肯定拿不了第1名。
E说：D应该是第1名。
比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。
请编程判断5位选手各是第几名。
输入无输出输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。
样例输入样例输出源代码：#include<stdio.h>int main(){printf("5\n");printf("2\n");printf("1\n");printf("3\n");printf("4\n");return 0;}3、鸡兔同笼描述一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。
算法练习题一、基础算法1. 编写一个程序，实现一个冒泡排序算法。
2. 实现一个选择排序算法。
3. 实现一个插入排序算法。
4. 编写一个函数，计算一个整数数组中的最大值和最小值。
5. 编写一个函数，实现二分查找算法。
6. 编写一个函数，实现快速排序算法。
7. 编写一个函数，判断一个整数是否为素数。
8. 编写一个函数，实现反转一个整数数组。
9. 编写一个函数，计算两个整数数组的交集。
10. 编写一个函数，判断一个字符串是否为回文。
二、数据结构11. 实现一个单链表的基本操作，包括插入、删除、查找。
12. 实现一个双向链表的基本操作，包括插入、删除、查找。
13. 实现一个栈的基本操作，包括压栈、出栈、查看栈顶元素。
14. 实现一个队列的基本操作，包括入队、出队、查看队首元素。
15. 实现一个二叉树的基本操作，包括插入、删除、查找。
16. 实现一个二叉搜索树的基本操作，包括插入、删除、查找。
17. 实现一个哈希表的基本操作，包括插入、删除、查找。
三、搜索与图论18. 编写一个程序，实现深度优先搜索（DFS）算法。
19. 编写一个程序，实现广度优先搜索（BFS）算法。
20. 编写一个程序，求解迷宫问题。
21. 编写一个程序，计算一个有向图的拓扑排序。
22. 编写一个程序，计算一个无向图的欧拉回路。
23. 编写一个程序，计算一个加权无向图的最小树（Prim算法）。
24. 编写一个程序，计算一个加权有向图的最短路径（Dijkstra算法）。
25. 编写一个程序，计算一个加权有向图的所有顶点对的最短路径（Floyd算法）。
四、动态规划26. 编写一个程序，实现背包问题。
27. 编写一个程序，计算最长公共子序列（LCS）。
28. 编写一个程序，计算最长递增子序列（LIS）。
29. 编写一个程序，实现编辑距离（Levenshtein距离）。
30. 编写一个程序，实现硬币找零问题。
31. 编写一个程序，实现矩阵链乘问题。
算法分析练习题一一、选择题1、二分搜索算法是利用A 实现的算法;A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是A ;A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3．下列算法中通常以自底向上的方式求解最优解的是B ;A、备忘录法B、动态规划法C、贪心法D、回溯法4、衡量一个算法好坏的标准是C ;A 运行速度快B 占用空间少C 时间复杂度低D 代码短5、以下不可以使用分治法求解的是D ;A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题6. 实现循环赛日程表利用的算法是A ;A、分治策略B、动态规划法C、贪心法D、回溯法7.备忘录方法是那种算法的变形; BA、分治法B、动态规划法C、贪心法D、回溯法8．最长公共子序列算法利用的算法是B ;A、分支界限法B、动态规划法C、贪心法D、回溯法9．实现棋盘覆盖算法利用的算法是A ;A、分治法B、动态规划法C、贪心法D、回溯法10. 矩阵连乘问题的算法可由B设计实现;A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法11、Strassen矩阵乘法是利用A 实现的算法;A、分治策略B、动态规划法C、贪心法D、回溯法12、使用分治法求解不需要满足的条件是A ;A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解13、下列算法中不能解决0/1背包问题的是AA 贪心法B 动态规划C 回溯法D 分支限界法14．实现合并排序利用的算法是A ;A、分治策略B、动态规划法C、贪心法D、回溯法15．下列是动态规划算法基本要素的是D ;A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质16．下列算法中通常以自底向下的方式求解最优解的是B ;A、分治法B、动态规划法C、贪心法D、回溯法17、合并排序算法是利用A 实现的算法;A、分治策略B、动态规划法C、贪心法D、回溯法18．实现大整数的乘法是利用的算法C ;A、贪心法B、动态规划法C、分治策略D、回溯法19. 实现最大子段和利用的算法是B ;A、分治策略B、动态规划法C、贪心法D、回溯法20. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的B ;A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解21. 实现最长公共子序列利用的算法是B ;A、分治策略B、动态规划法C、贪心法D、回溯法二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分;2、程序是算法用某种程序设计语言的具体实现;3、算法的“确定性”指的是组成算法的每条指令是清晰的,无歧义的;4.矩阵连乘问题的算法可由动态规划设计实现;5、算法是指解决问题的一种方法或一个过程 ;6、从分治法的一般设计模式可以看出,用它设计出的程序一般是递归算法 ;7、矩阵连乘问题的算法可由动态规划设计实现;8. 动态规划算法的基本思想是将待求解问题分解成若干子问题 ,先求解子问题 ,然后从这些子问题的解得到原问题的解;9.算法是由若干条指令组成的有穷序列,且要满足输入、输出、确定性和有限性四条性质;10、大整数乘积算法是用分治法来设计的;11.快速排序算法是基于分治策略的一种排序算法;12.动态规划算法的两个基本要素是. 性质和性质 ;13.任何可用计算机求解的问题所需的时间都与其规模有关;14.快速排序算法的性能取决于划分的对称性 ;15、出自于“平衡子问题”的思想,通常分治法在分割原问题,形成若干子问题时,这些子问题的规模都大致相同 ;16、使用二分搜索算法在n个有序元素表中搜索一个特定元素,在最佳情况下,搜索的时间复杂性为O,在最坏情况下,搜索的时间复杂性为O logn ;17、已知一个分治算法耗费的计算时间Tn,Tn满足如下递归方程：解得此递归方可得Tn= O nlogn ;18、动态规划算法有一个变形方法备忘录方法 ;这种方法不同于动态规划算法“自底向上”的填充方向,而是“自顶向下”的递归方向,为每个解过的子问题建立了备忘录以备需要时查看,同样也可避免相同子问题的重复求解;19、递归的二分查找算法在divide阶段所花的时间是 O1 ,conquer阶段所花的时间是 Tn/2 ,算法的时间复杂度是 Ologn ;20、用动态规划算法计算矩阵连乘问题的最优值所花的时间是 On3 , 子问题空间大小是 On2 ;21、一个算法的优劣可以用时间复杂度与空间复杂度与来衡量;22、直接或间接地调用自身的算法称为递归算法;23、记号在算法复杂性的表示法中表示渐进确界或紧致界;24、在分治法中,使子问题规模大致相等的做法是出自一种平衡子问题的思想;25、动态规划算法适用于解具有某种最优性质问题;26、最优子结构性质的含义是问题的最优解包含其子问题的最优解;27、按照符号O的定义Of+Og等于Omax{fn,gn};28、二分搜索技术是运用分治策略的典型例子;29、动态规划算法中,通常不同子问题的个数随问题规模呈多项式级增长;30、最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素;三、算法填空1.最大子段和: 动态规划算法int MaxSumint n, int a{int sum=0, b=0； 速排序template<class Type>void QuickSort Type a, int p, int r{if p<r {int q=Partitiona,p,r;QuickSorta,p,q-1 ; 最长上升子序列问题—— 提示：此题可采用动态规划算法实现对于给定的一个序列12(,,,)N a a a ,11000N ≤≤;我们可以得到一些递增上升的子序列12(,,,)i i iK a a a ,这里121K i i i N ≤<<<≤;比如,对于序列1, 7, 3, 5, 9, 4, 8,有它的一些上升子序列,如1, 7, 3, 4, 8等等;这些子序列中最长的长度是4,比如子序列1, 3, 5, 8;你的任务：就是对于给定的序列,求出最长上升子序列的长度;要求写出你设计的算法思想及递推函数的公式表达;.2.Gray码构造问题——提示：此题可采用分治递归算法实现问题描述：“格雷码”是一个长度为n2的序列,满足：a每个元素都是长度为n比特的串b序列中无相同元素c连续的两个元素恰好只有1个比特不同例如：n=2时,格雷码为{00,01,11,10};Gray码是一种编码,这种编码可以避免在读取时,因各数据位时序上的差异造成的误读;格雷码在工程上有广泛应用;但格雷码不便于运算,请你设计一种构造方法,输入长度序列n,输出格雷码你只要做出一种构造方案即可,格雷码并不唯一;3.现在有8位运动员要进行网球循环赛,要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他选手各赛一次；（2）每个选手一天只能赛一次；（3）循环赛一共进行n – 1天;请利用分治法的思想,给这8位运动员设计一个合理的比赛日程;4.对于矩阵连乘所需最少数乘次数问题,其递归关系式为：其中mi,j为计算矩阵连乘Ai…Aj所需的最少数乘次数,pi-1为矩阵Ai的行,ip为矩阵Ai的列;现有四个矩阵,其中各矩阵维数分别为：请根据以上的递归关系,计算出矩阵连乘积A1A2A3A4所需要的最少数乘次数;5.有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高;n=6,c=20,P=4,8,15,1,6,3,W=5,3,2,10,4,8;其中n为物品个数,c为背包载重量,P表示物品的价值,W表示物品的重量;请问对于此0-1背包问题,应如何选择放进去的物品,才能使到放进背包的物品总价值最大,能获得的最大总价值多少6.归并排序算法对下列实例排序,写出算法执行过程;A=48,12,61,3,5,19,32,77.规则证明： Ofn+Ogn = Omax{fn,gn}8. 给定已按升序排好序的n个元素a0:n-1,现要在这n个元素中找出一特定元素x,返回其在数组中的位置,如果未找到返回-1;写出二分搜索的算法,并分析其时间复杂度;9. 利用分治算法写出合并排序的算法,并分析其时间复杂度。
1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是( B )。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是( A ）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（ B ）。
A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（ 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、下列随机算法中运行时有时候成功有时候失败的是（C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（ D )。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先(回溯法）12．下列算法中通常以深度优先方式系统搜索问题解的是( D ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。
( B ）A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B )。
A、O（n2n)B、O（nlogn）C、O(2n）D、O(n）15．分支限界法解最大团问题时，活结点表的组织形式是( B ）。
A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）.A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A )。
1、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或))(()(ngnf或))(()(ngnf，并简述理由。（12分） (1) ;5log)(;log)(2nngnnf (2) ;100)(;2)(2nngnfn (3) ;3)(;2)(nnngnf 2、试用分治法实现有重复元素的排列问题：设),...,,{21nrrrR是要进行排列的n个元素，其中元素nrrr,...,,21可能相同，试计算R的所有不同排列。（13分） 3、试用分治法对一个有序表实现二分搜索算法。（12分） 4、试用动态规划算法实现0-1闭包问题。（15分） 5、试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。（15分） 6、试用动态规划算法实现最大子矩阵和问题：求nm矩阵A的一个子矩阵，使其各元素之各为最大。（15分） 7、试用回溯法解决下列整数变换问题：关于整数i的变换f和g定义如下：2/)(;3)(iigiif。对于给定的两个整数n和m，要求用最少的变换f和g变换次数将n变为m。（18分）
1、(1) 证明：O(f)+O(g)=O(f+g) （7分） (2) 求下列函数的渐近表达式：（6分） 3n2+10n; 21+1/n; 2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或))(()(ngnf或))(()(ngnf，并简述理由。（15分） (1) ;5log)(;log)(2nngnnf (2) ;)(;log)(2nngnnf (3) ;log)(;)(2nngnnf 3、试用分治法对数组A[n]实现快速排序。（13分） 4、试用动态规划算法实现最长公共子序列问题。（15分） 5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。。（12分） 6、试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括： (1) 删除一个字符。 (2) 插入一个字符。 (3) 将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d(A,B)。 （16分）
7、试用回溯法解决下列整数变换问题：关于整数i的变换f和g定义如下：2/)(;3)(iigiif。
对于给定的两个整数n和m，要求用最少的变换f和g变换次数将n变为m。（16分）
1、 解：简答如下： （1）)5(loglog2nn，（2）)100(22nn，（3）)3(2nn 2、 解：解答如下： Template void Perm(Type list[],int k,int m) { if(k= =m){ for(int i=0;i<=m;i++) cout
3、 解：解答如下： Template int BinarySearch(Type a[],const Type& x,int n)
{//假定数组a[]已按非递减有序排列，本算法找到x后返回其在数组a[]中的位置，//否则返回-1 int left=0,right=n-1; while(left<=right){ int middle=(left+right)/2; ……………………………..（4分） if(x= =a[middle]) return middle+1; if(x>a[middle]) left=middle+1; ……………………………..（8分） else right=middle-1; } return -1; }……………………………..（12分）
4、 解：解答如下： Template void Knapsack(Type v,int w,int c,int n,Type **m) { Int jMax=min(w[n]-1,c); for(int j=0;j<=jMax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; ……………………………..（5分） for(int i=n-1;i>1;i--){ jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); …………..（8分） }; m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); …………..（10分） } Template Void Traceback(Type **m,int w,int c,int n,int x) { for(int i=1;iif(m[i][c]= =m[i+1][c]) x[i]=0; …………..（12分） else { x[i]=1,c-=w[i];}; x[n]=(m[n][c])?1:0; }……………………………..（15分）
5、 解：解答如下： void dicomp(int n,int a[]) { k=1; if(n<3){ a[1]=0;return;}; if(n<5){ a[k]=1;a[++k]=n-1;return;}; ……………………………..（5分） a[1]=2;n-=2;
while(n>a[k]){
k++; a[k]=a[k-1]+1; n-=a[k]; };……………………………..（10分） if(n= =a[k]){ a[k]++;n--;}; for(int i=0;i}……………………………..（15分） 6、 解：解答如下： int MaxSum2(int m,int n,int **a) { int sum=0; int *b=new int[n+1]; for(int i=1;i<=m;i++){ for(int k=1;k<=n;k++) b[k]=0; ……………………………..（5分） for(int j=i;j<=m;j++){ for(int k=1;k<=n;k++) b[k]+=a[j][k]; int max=MaxSum(n,b); if(max>sum) sum=max; } } return sum; ……………………………..（10分） }
int MaxSum(int n,int *a) { int sum=0,b=0; for(int i=1;i<=n;i++){ if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; } Return sum; ……………………………..（15分） } 7、 解：解答如下： void compute() { k=1; while(!search(1,n)){ k++; if(k>maxdep) break; init(); };……………………………..（6分） if(found) output();
else cout<<”No Solution!”<
}……………………………..（9分）
bool search(int dep,int n) { If(dep>k) return false; for(int i=0;i<2;i++){ int n1=f(n,i);t[dep]=i; ……………………………..（12分） if(n1= =m||search(dep+1,n1)){ Found=true; Out(); return true; } return false; ……………………………..（18分） }
