下载文档原格式
第5章数据结构与算法习题与答案第五章习题（1）复习题1、试述数据和数据结构的概念及其区别。
数据是对客观事物的符号表⽰，是信息的载体；数据结构则是指互相之间存在着⼀种或多种关系的数据元素的集合。
（P113）2、列出算法的五个重要特征并对其进⾏说明。
算法具有以下五个重要的特征：有穷性：⼀个算法必须保证执⾏有限步之后结束。
确切性：算法的每⼀步骤必须有确切的定义。
输⼊：⼀个算法有0个或多个输⼊，以刻画运算对象的初始情况，所谓0个输⼊是指算法本⾝定除了初始条件。
输出：⼀个算法有⼀个或多个输出，以反映对输⼊数据加⼯后的结果。
没有输出的算法没有实际意义。
可⾏性：算法原则上能够精确地运⾏，⽽且⼈们⽤笔和纸做有限次运算后即可完成。
（P115）3、算法的优劣⽤什么来衡量？试述如何设计出优秀的算法。
时间复杂度空间复杂度（P117）4、线性和⾮线性结构各包含哪些种类的数据结构？线性结构和⾮线性结构各有什么特点？线性结构⽤于描述⼀对⼀的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。
所谓⾮线性结构是指，在该结构中⾄少存在⼀个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。
树型和图型结构就是其中⼗分重要的⾮线性结构，可以⽤来描述客观世界中⼴泛存在的层次结构和⽹状结构的关系。
（P118 P122）5、简述树与⼆叉树的区别；简述树与图的区别。
树⽤来描述层次结构，是⼀对多或多对⼀的关系；⼆叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由⼀个称为根(root)的元素及两个不相交的、被分别称为左⼦树和右⼦树的⼆叉树组成。
⼆叉树是有序的，即若将其左、右⼦树颠倒，就成为另⼀棵不同的⼆叉树。
图也称做⽹，是⼀种⽐树形结构更复杂的⾮线性结构。
在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表⽰的多对多的关系。
（P121-P124）6、请举出遍历算法在实际中使⽤的例⼦。
《算法及其分析》课后选择题答案及详解第1 章——概论1.下列关于算法的说法中正确的有（）。
Ⅰ.求解某一类问题的算法是唯一的Ⅱ.算法必须在有限步操作之后停止Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果A.1个B.2个C.3个D.4个2.T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（）。
A.T(n)=T(n-1)+1，T(1)=1B.T(n)=2nC.T(n)= T(n/2)+1，T(1)=1D.T(n)=3nlog2n答案解析：1.答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一类问题的算法不一定是唯一的。
答案为C。
2.答：选项A的时间复杂度为O(n)。
选项B的时间复杂度为O(n)。
选项C 的时间复杂度为O(log2n)。
选项D的时间复杂度为O(nlog2n)。
答案为C。
第3 章─分治法1.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。
这要求原问题和子问题（）。
A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同2.在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。
A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行。
但不同方法，算法复杂度上界可能不同3.对于下列二分查找算法，以下正确的是（）。
A.intbinarySearch(inta[],intn,int x){intlow=0,high=n-1;while(low<=high){intmid=(low+high)/2;if(x==a[mid])returnmid;if(x>a[mid])low=mid;elsehigh=mid;}return –1;}B.intbinarySearch(inta[],intn,int x) { intlow=0,high=n-1;while(low+1!=high){intmid=(low+high)/2;if(x>=a[mid])low=mid;elsehigh=mid;}if(x==a[low])returnlow;elsereturn –1;}C.intbinarySearch(inta[],intn,intx) { intlow=0,high=n-1;while(low<high-1){intmid=(low+high)/2;if(x<a[mid])high=mid;elselow=mid;}if(x==a[low])returnlow;elsereturn –1;}D.intbinarySearch(inta[],intn,int x) {if(n>0&&x>=a[0]){intlow= 0,high=n-1;while(low<high){intmid=(low+high+1)/2;if(x<a[mid])high=mid-1;elselow=mid;}if(x==a[low])returnlow;}return –1;}答案解析：1.答：C。
page: 1The Home of jetmambo - 第 5 章树和二叉树第 5 章树和二叉树(1970-01-01) -第 5 章树和二叉树课后习题讲解1. 填空题⑴树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m （m＞0）个（）的集合，每个集合都是根结点的子树。
【解答】有且仅有一个，互不相交⑵树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。
【解答】度，孩子，双亲⑶一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。
【解答】2i-1，(n+1)/2，(n-1)/2【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。
⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。
【解答】2h -1，2h-1【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。
⑸深度为k的二叉树中，所含叶子的个数最多为（）。
【解答】2k-1【分析】在满二叉树中叶子结点的个数达到最多。
⑹具有100个结点的完全二叉树的叶子结点数为（）。
【解答】50【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。
⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。
则该树中有（）个叶子结点。
【解答】12【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。
⑻某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。
1．最大子段和问题：给定整数序列 n a a a ,,,21 ，求该序列形如∑=jik k a 的子段和的最大值： ⎭⎬⎫⎩⎨⎧∑=≤≤≤ji k k n j i a 1max ,0max1) 已知一个简单算法如下：int Maxsum(int n,int a,int& best i,int& bestj){ int sum = 0;for (int i=1;i<=n;i++){ int suma = 0;for (int j=i;j<=n;j++){ suma + = a[j]; if (suma > sum){ sum = suma; besti = i; bestj = j; } }}return sum;}试分析该算法的时间复杂性。
2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。
3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。
分析算法的时间复杂度。
（提示：令1()max,1,2,,jk i j nk ib j a j n ≤≤≤===∑）解：1）分析按照第一章，列出步数统计表，计算可得)(2n O2）分治算法：将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种可能： ①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； ②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同； ③a[1:n]的最大子段和为两部分的字段和组成，即j n jil n i ja a a a a+++++=+⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢∑ 122；intMaxSubSum ( int *a, int left , int right){int sum =0;if( left==right)sum = a[left] > 0? a[ left]:0 ;else{int center = ( left + right) /2;int leftsum =MaxSubSum ( a, left , center) ;int rightsum =MaxSubSum ( a, center +1, right) ;int s_1 =0;int left_sum =0;for ( int i = center ; i >= left; i--){left_sum + = a [ i ];if( left_sum > s1)s1 = left_sum;}int s2 =0;int right_sum =0;for ( int i = center +1; i <= right ; i++){right_sum + = a[ i];if( right_sum > s2)s2 = right_sum;}sum = s1 + s2;if ( sum < leftsum)sum = leftsum;if ( sum < rightsum)sum = rightsum;}return sum;}int MaxSum2 (int n){int a；returnMaxSubSum ( a, 1, n) ;} 该算法所需的计算时间T(n)满足典型的分治算法递归分式T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)3）设}{max )(1∑=≤≤=j ik k ji a j b ,则最大子段和为).(max max max max max 11111j b a a nj jik k ji n j j ik k nj n i ≤≤=≤≤≤≤=≤≤≤≤==∑∑},,,,max {)(11211j j j j j j j a a a a a a a a a j b +++++=---最大子段和实际就是)}(,),2(),1(max{n b b b .要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。
算法第五次作业答案第1题：答：TURE法一：我们已知用Kruskal算法能够生成G的一棵最小生成树，而在此算法运行时最小费用边e*将被首先添加进来，从而可知最后生成的最小生成树肯定包含边e*法二：假设边e*(代价最少的边)的两个顶点为v1和v2,图G中共有N 个点，为v1、v2、…v N。
现在假设已经找出了除v1外的点全部被纳入的最优生成树，现在只要将v1以最小代价连入即可，由于e*是v1连接的代价最少的边（v1连接的其余边要付出的代价都比e*大），所以一定会选择e*连入以生成最小生成树。
第2题：答：1) 算法如下：While 图G中还有环用BFS算法遍历图G，找到一个环后删除环中费用最大的边；返回删除了一条边后的图G；Endwhile消除了所有的环后最后剩下的图G即为最小生成树2) 算法正确性证明：使用BFS广度搜索遍历整个图，找到环后删除环中代价最大的边，之后重新遍历，每遍历一次消除一个环，最后留下的图中没有环，并且剩下的边都是相对代价小的，因此生成的是最小生成树。
3) 复杂度：因为最多不超过n+8个边，所以环至多只有9个，所以整个BFS 遍历最多不超过9次，而BFS 算法复杂度为O(V+E)=O(n),故总的复杂度是O(n).第3题：(1)算法描述如下：①初始化一个具有n 个顶点0条边的图G②对给定的度数序列0L 进行排序得11212{,,,}d n n L d d d d d =≥≥≥……且…… ③1L 中前n d 个数均减1并舍去最后一个数得21211L {1,1,,1,,,}n n d d n d d d d d +-=---…………④在进行第③步处理的同时对图G 中的顶点进行连线并用2L 替换0L ； ⑤重复步骤②—④直到0L 为空，此时得到的图G 即为所求(2)算法正确性证明：①如果图G 具有n-1个顶点且度数序列为2L ，在图G 中添加一个顶点n v ，使得n v 与顶点12,,,nd v v v ……相连，得到图'G 且其度数序列为1L 。
第五章作业答案1、伪代码：假设查找范围是有序的，a<b1. low=1；high=n；//设置初始查找区间2. 测试查找区间［low，high］是否存在，若不存在，则查找失败；否则3. 取中间点mid=(low+high)/2; 比较a，b与r[mid]，有以下三种情况：3.1 若a>r[mid]，则high=mid-1；查找在左半区进行，转2；3.2 若b<r[mid]，则low=mid+1；查找在右半区进行，转2；3.3 若a<r[mid]并且b>r[mid]，则在左半区对a用折半查找找到对应的r[i]>=a&&r[i-1]<a，在右半区对b用折半查找r[j]<=b&&r[j+1]>b；4. r[i]到r[j]之间的元素即为问题的解参考代码：#include<iostream.h>int i=0;int j=0;//存储a-b的所有元素的起始下标和终止下标int finda(int s[],int begin,int end,int a)//查找边界为a的元素{if(begin==end)return begin;else{int m=(begin+end)/2;if(s[m]==a)return m;else if(s[m]>a)return finda(s,begin,m,a);else return finda(s,m+1,end,a);}}int findb(int s[],int begin,int end,int b)//查找边界为b的元素{if(begin==end){if(s[begin]>b) return begin-1;else return begin;}else{int m=(begin+end)/2;if(s[m]==b)return m;else if(s[m]<b)return findb(s,m+1,end,b);else return findb(s,begin,m,b);}}void find(int s[],int begin,int end,int a,int b)//缩小a-b的查找范围{if(begin==end){if(s[begin]>=a)i=begin;else if(s[begin]<=b)j=begin;}else{int m=(begin+end)/2;if(s[m]<a) find(s,m+1,end,a,b);else if(s[m]>b)find(s,begin,m,a,b);else {i=finda(s,begin,m,a);j=findb(s,m+1,end,b);}}}void main(){int s[]={1,2,5,8,11,24,31,40};int a=2;int b=30;find(s,0,7,a,b);cout<<i<<ends<<j<<endl;}4、参考代码：根据程序运行结果显示使用两种方法生成的堆序列不一定一样#include<iostream.h>const int N=8;void SiftHeap(int r[],int k,int n){int i=k,j=2*i;int temp;while(j<=n){if(j<n&&r[j]<r[j+1])j++;if(r[i]>r[j])break;else{temp=r[i];r[i]=r[j];r[j]=temp;i=j;j=2*i;}}}void InsertHeap(int r[],int k) {int i=k,j;int temp;while(i!=1){j=i/2;if(r[i]<r[j])break;else{temp=r[i];r[i]=r[j];r[j]=temp;i=j;}}}void main(){int s[N+1],s1[N+1];//输入s和s1for(int i=1;i<=N;i++){cin>>s[i];s1[i]=s[i];} //利用筛选法生成堆for(i=N;i>=1;i--)SiftHeap(s,i,N);//利用插入法生成堆for(i=1;i<=N;i++)InsertHeap(s1,i);//输出s和s1for(i=1;i<=N;i++)cout<<s[i]<<ends<<s1[i]<<endl;}。
习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。
故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理"该算法在处理这种输入的过程中,上述情况最多会发生几次"Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法"(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法"(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗"c.该算法在位吗"解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序)hints:a. Replace the ith element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element(e.g., 0 for an array of positive numbers ) to mark the ith position is empty. (“lazy deletion”)习题2.11欧几里得算法的时间复杂度欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式gcd(a, b) = gcd(b, a mod b)其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b的余数. 算法如下:输入: 两个整数a, b输出: a和b的最大公约数function gcd(a, b:integer):integer;if b=0 return a;else return gcd(b, a mod b);end function欧几里得算法是最古老而经典的算法, 理解和掌握这一算法并不难, 但要分析它的时间复杂度却并不容易. 我们先不考虑模运算本身的时间复杂度(算术运算的时间复杂度在Knuth的TAOCP中有详细的讨论), 我们只考虑这样的问题: 欧几里得算法在最坏情况下所需的模运算次数和输入的a 和b 的大小有怎样的关系"我们不妨设a>b>=1(若a<b 我们只需多做一次模运算, 若b=0或a=b 模运算的次数分别为0和1), 构造数列{un}: u0=a, u1=b, uk=uk-2 mod uk-1(k>=2), 显然, 若算法需要n 次模运算, 则有un=gcd(a, b), un+1=0. 我们比较数列{un}和菲波那契数列{Fn}, F0=1<=un, F1=1<=un-1, 又因为由uk mod uk+1=uk+2, 可得uk>=uk+1+uk+2, 由数学归纳法容易得到uk>=Fn-k, 于是得到a=u0>=Fn, b=u0>=Fn-1. 也就是说如果欧几里得算法需要做n 次模运算, 则b 必定不小于Fn-1. 换句话说, 若 b<Fn-1, 则算法所需模运算的次数必定小于n. 根据菲波那契数列的性质, 有Fn-1>(1.618)n/sqrt(5), 即b>(1.618)n/sqrt(5), 所以模运算的次数为O(lgb)---以b 为底数 = O(lg(2)b)---以2为底数，输入规模也可以看作是b 的bit 位数。
第五章人工免疫算法习题与答案1. 填空题（1）人工免疫算法的缩写是，它是对的一种模拟。
判别优劣的适应度函数这里称为。
（2）利用生物免疫系统的某一方面原理就可以设计新算法，因此人工免疫算法是多个算法的统称，其中最具代表性的算法有、和。
解释：本题考查人工免疫算法的基础知识。
具体内容请参考课堂视频“第5章人工免疫算法”及其课件。
答案：（1）AIA，生物免疫机理，亲和度（2）否定选择算法、免疫规划算法、克隆选择算法2.给出人工免疫算法的定义，并指出其特征。
解释：本题考查人工免疫算法的定义和特点。
具体内容请参考课堂视频“第5章人工免疫算法”及其课件。
答案：人工免疫算法是基于免疫学理论和生物免疫系统机制而提出的计算智能算法，是对生物免疫机理的一种模拟，并受到遗传算法的启发，因此免疫算法与遗传算法有许多相似之处。
AIS算法具有以下特征：（1）具有全局搜索能力。
（2）具有多样性保持机制。
（3）鲁棒性强。
（4）具有并行分布式搜索机制。
3.关于人工免疫算法，下面说法错误的是（）。
A）人工免疫算法是一种全局搜索优化方法。
B）抗原对应着优化问题的可行解。
C）免疫操作可以用于产生新的解。
D）优化问题的寻优过程实际上是免疫系统识别抗原并实现抗体进化的过程。
解释：本题考查人工免疫算法的特点。
具体内容请参考课堂视频“第5章人工免疫算法”及其课件。
答案：B（1）生物免疫系统运用多种免疫调节机制产生多样性抗体以识别、匹配并最终消灭外界抗原，免疫应答中的抗体更新过程是一个全局搜索的进化过程，A 选项正确。
（2）抗原对应着问题，抗体对应着优化问题的可行解，B选项错误。
（3）免疫操作中克隆变异、抗体补充等可以产生新的抗体，对应着新解产生的过程，C选项正确。
（4）优化问题的寻优过程对应着免疫系统识别抗原并实现抗体进化的过程，D选项正确。
4.试写出克隆选择算法的基本流程。
解释：本题考查克隆选择算法CSA的步骤。
具体内容请参考课堂视频“第5章人工免疫算法”及其课件。
第五章 聚类分析5.1 判别分析和聚类分析有何区别？答：即根据一定的判别准则，判定一个样本归属于哪一类。
具体而言，设有n 个样本，对每个样本测得p 项指标（变量）的数据，已知每个样本属于k 个类别（或总体）中的某一类，通过找出一个最优的划分，使得不同类别的样本尽可能地区别开，并判别该样本属于哪个总体。
聚类分析是分析如何对样品（或变量）进行量化分类的问题。
在聚类之前，我们并不知道总体，而是通过一次次的聚类，使相近的样品（或变量）聚合形成总体。
通俗来讲，判别分析是在已知有多少类及是什么类的情况下进行分类，而聚类分析是在不知道类的情况下进行分类。
5.2 试述系统聚类的基本思想。
答：系统聚类的基本思想是：距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中。
5.3 对样品和变量进行聚类分析时， 所构造的统计量分别是什么？简要说明为什么这样构造？答：对样品进行聚类分析时，用距离来测定样品之间的相似程度。
因为我们把n 个样本看作p 维空间的n 个点。
点之间的距离即可代表样品间的相似度。
常用的距离为 （一）闵可夫斯基距离：1/1()()pq qij ik jk k d q X X ==-∑q 取不同值，分为 （1）绝对距离（1q =）1(1)pij ik jk k d X X ==-∑（2）欧氏距离（2q =）21/21(2)()pij ik jk k d X X ==-∑（3）切比雪夫距离（q =∞）1()max ij ik jkk pd X X ≤≤∞=-（二）马氏距离（三）兰氏距离对变量的相似性，我们更多地要了解变量的变化趋势或变化方向，因此用相关性进行衡量。
21()()()ij i j i j d M -'=--X X ΣX X 11()p ik jkij k ik jk X X d L p X X =-=+∑将变量看作p 维空间的向量，一般用（一）夹角余弦（二）相关系数5.4 在进行系统聚类时，不同类间距离计算方法有何区别？选择距离公式应遵循哪些原则？答： 设d ij 表示样品X i 与X j 之间距离，用D ij 表示类G i 与G j 之间的距离。
5-1凸多边形最优三角剖分问题//3d5 凸多边形最优三角剖分#include "stdafx.h"#include <iostream> using namespace std；const int N = 7;//凸多边形边数+1int weight[][N] = {{0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1},{4,3,4,2,1,0}};//凸多边形权int MinWeightTriangulation(int n,int **t,int **s);void Traceback(int i,int j,int **s);//构造最优解int Weight(int a,int b,int c);//权函数int main(){int **s = new int *[N]；int **t = new int *[N]；for(int i=0;i<N;i++) {s[i] = new int[N]；t[i] = new int[N]；}cout<<"此多边形最优三角剖分值为："<<MinWeightTriangulation(N-1,t,s)<<endl；cout<<"最优三角剖分构造为："<<endl；Traceback(1,5,s)；//s[i][j]记录了Vi-1和Vj构成三角形第3个顶点位置return 0;}int MinWeightTriangulation(int n,int **t,int **s){for(int i=1；i<=n；i++){t[i][i] = 0;}for(int r=2；r<=n；r++) //r为当前计算链长（子问题规模）{for(int i=1；i<=n-r+1；i++)//n-r+1为最后一种r链前边界{int j = i+r-1;//计算前边界为r，链长为r链后边界t[i][j] = t[i+1][j] + Weight(i-1,i,j);//将链ij划分为A(i) * ( A[i+1:j] )这里事实上就是k=i s[i][j] = i;for(int k=i+1；k<j；k++){//将链ij划分为( A[i:k] )* (A[k+1:j])int u = t[i][k] + t[k+1][j] + Weight(i-1,k,j);if(u<t[i][j]){t[i][j] = u;s[i][j] = k;}}}}return t[1][N-2];}void Traceback(int i,int j,int **s){if(i==j) return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout<<"三角剖分顶点：V"<<i-1<<",V"<<j<<",V"<<s[i][j]<<endl; }int Weight(int a,int b,int c){return weight[a][b] + weight[b][c] + weight[a][c];}5-4 数字三角形最短途径5-2 游艇租赁问题#include <iostream>using namespace std;#define N 210int cost[N][N];int m[N];int main(){int n,i,j;while(cin>>n){for(i=1;i<n;i++)for(j=i+1;j<=n;j++)cin>>cost[i][j];m[1]=0;int min;for(i=2;i<=n;i++){min=cost[1][i];for(j=1;j<=i-1;j++){if(cost[j][i]!=0 && m[j]+cost[j][i]<min)min=m[j]+cost[j][i];}m[i]=min;}cout<<m[n]<<endl;}return 0;}5-6 合唱队形问题#include <iostream>ing namespace std;2.3.//用于保存子问题最优解备忘录4.typedef struct5.{6.int maxlen; //当前子问题最优解7.int prev; //构造该子问题所用到下一级子问题序号(用于跟踪输出最优队列)8.}Memo;9.10.//用于递归输出Memo B中解11.void Display(int* A, Memo* M, int i)12.{13.if (M[i].prev == -1)14. {15. cout<<A[i]<<" ";16.return;17. }18. Display(A, M, M[i].prev);19. cout<<A[i]<<" ";20.}21.22.//算法重要某些23.void GetBestQuence(int* A, int n)24.{25.//定义备忘录并作必要初始化26. Memo *B = new Memo[n]; //B[i]代表从A[0]到A[i]满足升序剔除某些元素后能得到最多元素个数27. Memo *C = new Memo[n]; //C[i]代表从A[i]到A[n-1]满足降序剔除某些元素后能得到最多元素个数28. B[0].maxlen = 1; //由于B[i]由前向后构造初始化最前面子问题 (元素自身就是一种满足升序降序序列)29. C[n-1].maxlen = 1; //同样C[i]由后向前构造30.for (int i=0; i<n; i++) //为前一种最优子问题序号给定一种特殊标记-131.//用于在跟踪途径时终结递归或迭代(由于咱们并不懂得最后队列从哪里开始)32. {33. B[i].prev = -1;34. C[i].prev = -1;35. }36.37.for (i=1; i<n; i++) //构造B[n]38. {39.int max=1;40.for (int j=i-1; j>=0; j--) //查看前面子问题找出满足条件最优解并且记录41. {42.if (A[j]<A[i] && B[j].maxlen+1>max)43. {44. max = B[j].maxlen+1; //跟踪当前最优解45. B[i].prev = j; //跟踪构造途径46. }47. }48. B[i].maxlen = max; //构造最优解49. }50.51.for (i=n-1; i>0; i--)52. {53.int max=1;54.for (int j=i; j<n; j++) //从后往前构造这是为了背面在统筹最后解时可以直接用B[i]+C[i]-155.//否则咱们得到最优解始终为B[n-1]+C[n-1]56. {57.if (A[j]<A[i] && C[j].maxlen+1>max) //比当前长度更长记录并构造58. {59. max = C[j].maxlen+1;60. C[i].prev = j;61. }62. }63. C[i].maxlen = max;64. }65.66.//遍历i 得到最大B[i]+C[i]-1(-1是由于咱们在B[i]和C[i]中均加上了A[i]这个数因而需要减去重复)67.int maxQuence = 0; //记录当前最优解68.int MostTall; //记录i 用于跟踪构造途径69.for (i=0; i<n; i++)70. {71.if (B[i].maxlen+C[i].maxlen-1 > maxQuence)72. {73. maxQuence = B[i].maxlen+C[i].maxlen-1;74. MostTall = i;75. }76. }77.78. cout<<"最大合唱队形长度: "<<maxQuence<<endl;79.80.//B由前向后构造因而prev指向前面元素需要递归输出81. Display( A, B, MostTall);82.//Cprev指向背面元素直接迭代输出83.while (C[MostTall].prev != -1)84. {85. MostTall = C[MostTall].prev;86. cout<<A[MostTall]<<" ";87. }88. cout<<endl;89.90.delete []B;91.delete []C;92.}93.int main()94.{95.//测试96.int *A;97.int n;98. cout<<"请输入合唱队员个数: "<<endl;99. cin>>n;100.101. A = new int[n];102. cout<<"输入队员身高 :"<<endl;103.for (int i=0; i<n; i++)104. {105. cin>>A[i];106. }107. GetBestQuence(A, n);108.delete []A;109.return 0;110.}5-7买票问题状态转移方程是f[i] := min(f[i - 1] + t[i]，f[i - 2] + r[i - 1])；{i = 2 ~ n} 初值f[0] := 0；f[1] := t[1];constmaxn = 1000;var i，j，n ：longint;f，t，r ：array[0..maxn] of longint;function min(a，b ：longint) ：longint;begin if a < b then exit(a)；exit(b)；end;beginreadln(n);for i := 1 to n do read(t[i]);for i := 1 to n - 1 do read(r[i]);f[0] := 0；f[1] := t[1];for i := 2 to n dof[i] := min(f[i - 1] + t[i]，f[i - 2] + r[i - 1]);writeln(f[n]);end.伪代码BuyTicks(T，R)1n ← length[T]2 f[0] ← 03 f[1] ← T[1]4for i ← 2 to n do5f[i] ← f[i-2]+R[i-1]6if f[i] > f[i-1]+T[i] then 7f[i] ← f[i-1]+T[i]8return f5-8最大子段和问题#include <stdio.h>#include <malloc.h>int max_sum(int n,int *a,int *besti,int *bestj){ int *b = (int *)malloc(n * sizeof(int));int sum = 0;int i = -1;int temp = 0;for (i=0;i<=n-1;i++) {if (temp > 0)temp += a[i];elsetemp = a[i];b[i] = temp;}sum = b[0];for (i=1;i<=n-1;i++) {if (sum < b[i]) {sum = b[i];*bestj = i;}}for (i = *bestj;i >= 0;i--) {if (b[i] == a[i]) {*besti = i;break;}}free(b);return sum；}int main(void){int a[] = {-2,1,-4,13,-5,-2,-10,20,100};int length = sizeof(a)/sizeof(int);int sum = -1;int besti = -1;int bestj = -1;sum = max_sum(length,a,&besti,&bestj);printf("besti = %d,bestj = %d,max_sum=%d\n",besti,bestj,sum);return 0;}5-9 装箱问题发现就是0-1背包问题每个物品体积就是耗费同步也是价值，也就是说这题可以转化为在总体积为w下，可以得到最大价值最后用总体积减去最大价值就是剩余至少空间状态转移方程d[j] = max(d[j]，d[j - a[i]] + a[i]);#include <stdio.h>#include <string.h>using namespace std;int n;int d[5];int a[35];int main(){int w;scanf("%d%d"，&w，&n);int i，j;for(i = 0；i < n；i++){scanf("%d"，&a[i]);}memset(d，0，sizeof(d));for(i = 0；i < n；i++){for(j = w；j >= a[i]；j--)d[j] = max(d[j]，d[j - a[i]] + a[i]);}printf("%d\n"，w - d[w]);return0;}</algorithm></string.h></stdio.h> 6-10 表格乘法#include "stdio.h"#define num 50void chengji_1(int (*a)[num][3],int n,char b[]); int _tmain( ){int a[num][num][3];char b[num];int i,j,k,n;char c;printf("intput the num of array:");scanf("%d",&n);getchar();for(i=0;i<n;i++)for(j=0;j<n;j++)for(k=0;k<3;k++)a[i][j][k]=0;i=0;while((c=getchar())!='/n'){b[i]=c；i++;}chengji_1(a,n,b);printf("reslut is:%d",a[0][n-1][0]);getchar();}void chengji_1(int (*a)[num][3],int n,char b[]){int i,j,k,t;for(i=0;i<n;i++)*(*(*(a+i)+i)+(b[i]-'a'))=1;for(k=1;k<n;k++)for(i=0;i<n;i++){j=i+k;for(t=i;t<j;t++){*(*(*(a+i)+j)+0)+=((*(*(*(a+i)+t)+0))*(*(*(*(a+t+1)+j)+2))+(*(*(*(a+i)+t)+1))*(*(*(*(a+t+1)+j )+2))+(*(*(*(a+i)+t)+2))*(*(*(*(a+t+1)+j)+0)));*(*(*(a+i)+j)+1)+=((*(*(*(a+i)+t)+0))*(*(*(*(a+t+1)+j)+0))+(*(*(*(a+i)+t)+0))*(*(*(*(a+t+1)+j )+1))+(*(*(*(a+i)+t)+1))*(*(*(*(a+t+1)+j)+1)));*(*(*(a+i)+j)+2)+=((*(*(*(a+i)+t)+1))*(*(*(*(a+t+1)+j)+0))+(*(*(*(a+i)+t)+2))*(*(*(*(a+t+1)+j )+1))+(*(*(*(a+i)+t)+2))*(*(*(*(a+t+1)+j)+2)));} }}11 最长滑雪道问题#include <iostream>using namespace std;int data[102][102],longetr[102][102];int m,n;int cal(int i,int j){int max = 0;if (longetr[i][j] > 0)//如果该点已经计算过直接返回途径长度，保存已有计算成果这是动态规划优越之处return longetr[i][j];if(j-1 >= 0 && data[i][j] > data[i][j-1] && max < cal(i,j-1))max = cal(i,j-1);//向左走if(j+1 < n && data[i][j] > data[i][j+1] && max < cal(i,j+1))max = cal(i,j+1);//向右走if(i-1 >= 0 && data[i][j] > data[i-1][j] && max < cal(i-1,j))max = cal(i-1,j);//向上走if(i+1 < m && data[i][j] > data[i+1][j] && max < cal(i+1,j))max = cal(i+1,j);//向下走return longetr[i][j] = max + 1;//最长途径就是相邻四个节点最长途径加1所得四条途径中最长那条}int main(){int i,j;cin>>m>>n;int maxway = 0;for ( i=0;i<m;i++)for( j=0;j<n;j++){cin>>data[i][j];longetr[i][j] = 0;}for ( i=0;i<m;i++)for( j=0;j<n;j++){longetr[i][j] = cal(i,j);}for ( i=0;i<m;i++)for( j=0;j<n;j++){if(maxway < longetr[i][j])maxway = longetr[i][j];}cout<<maxway<<endl;return 0;}办法2 #include<iostream#include<cmath>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;struct dot//创立一种构造体存储每个点信息{int x;int y;int h;};dot line[0]; //将每个点存入该构造体数组int height[120][120]; //用于存储inputint len[120][120]; //dp数组，存储每个点最优解int cmp( const void *a ,const void *b) //迅速排序参照函数{if((*(dot *)a).h>(*(dot *)b).h)return 1;else return -1;}int main (){int m,n;cin>>m>>n;int i,j;int flag=-1;int max=0;for(i=1;i<=m;i++){for(j=1;j<=n;j++){flag++;scanf("%d",&height[i][j]);line[flag].x=i;line[flag].y=j;line[flag].h=height[i][j];}} //这个双层循环用来完毕数据收集工作qsort(line,m*n,sizeof(line[0]),cmp); //对构造体h参数进行排序for(i=0;i<m*n;i++){if(height[line[i].x][line[i].y]<height[line[i].x][line[i].y+1]&&len[line[i].x][line [i].y]>=len[line[i].x][line[i].y+1]){len[line[i].x][line[i].y+1]=len[line[i].x][line[i].y]+1;}if(height[line[i].x][line[i].y]<height[line[i].x+1][line[i].y]&&len[line[i].x][line [i].y]>=len[line[i].x+1][line[i].y]){len[line[i].x+1][line[i].y]=len[line[i].x][line[i].y]+1;}if(height[line[i].x][line[i].y]<height[line[i].x][line[i].y-1]&&len[line[i].x][line[ i].y]>=len[line[i].x][line[i].y-1]){len[line[i].x][line[i].y-1]=len[line[i].x][line[i].y]+1;}if (height[line[i].x][line[i].y]<height[line[i].x-1][line[i].y]&&len[line[i].x][li ne[i].y]>=len[line[i].x-1][line[i].y]){len[line[i].x-1][line[i].y]=len[line[i].x][line[i].y]+1;}} //动态规划过程for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(len[i][j]>max)max=len[i][j];}} //遍历len数组，求出最大值cout<<max+1<<endl;// 由于初始值是0,因此最后要加一return 0;最大矩形和b[j]=max{b[j-1]+a[j],a[j]},1 #include <iostream>2 using namespace std;34 int ** a;5 int **sum;6 int max_array(int *a,int n)7 {8 int *c = new int [n];9 int i =0;10 c[0] = a[0];11 for(i=1;i<n;i++)12 {13 if(c[i-1]<0)14 c[i] = a[i];15 else16 c[i] = c[i-1]+a[i];17 }18 int max_sum = -65536;19 for(i=0;i<n;i++)20 if(c[i]>max_sum)21 max_sum = c[i];22 delete []c;23 return max_sum;2425 }26 int max_matrix(int n)27 {28 int i =0;30 int max_sum = -65535;31 int * b = new int [n];3233 for(i=0;i<n;i++)34 {35 for(j=0;j<n;j++)36 b[j]= 0;37 for(j=i;j<n;j++)//把数组从第i行到第j行相加起来保存在b中，在加时，自底向上，一方面计算行间隔(j-i)等于1状况，然后计算j-i等于2状况，一次类推,在小间隔基本上一次累加，避免重复计算38 {39 for(int k =0;k<=n;k++)40 b[k] += a[j][k];41 int sum = max_array(b,n);42 if(sum > max_sum)43 max_sum = sum;44 }45 }46 delete []b;47 return max_sum;48 }49 int main()50 {51 int n;5354 a = new int *[n];55 sum = new int *[n];56 int i =0;57 int j =0;58 for(i=0;i<n;i++)59 {60 sum[i] = new int[n];61 a[i] = new int[n];62 for(j=0;j<n;j++)63 {64 cin>>a[i][j];65 sum[i][j] =0 ;//sum[r][k]表达起始和结尾横坐标分别为r,k时最大子矩阵66 //sum[r][k] = max{sum (a[i][j]):r<=i<=k}:0<=k<=n-167 }68 }69 /*70 int b[10]={31,-41,59,26,-53,58,97,-93,-23,84};71 cout << max_array(b,10) << endl;72 */73 cout << max_matrix(n);74 }。
第五章习题5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。
已知A的基地址为1000，计算：数组A共占用多少字节；数组A的最后一个元素的地址；按行存储时元素A36的地址；按列存储时元素A36的地址；5.2 设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变换公式。
5.3假设稀疏矩阵A和B均以三元组表作为存储结构。
试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。
5.5写一个在十字链表中删除非零元素aij的算法。
5.6画出下面广义表的两种存储结构图示：((((a), b)), ((( ), d), (e, f)))5.7求下列广义表运算的结果：（1）HEAD[((a,b),(c,d))];（2）TAIL[((a,b),(c,d))];（3）TAIL[HEAD[((a,b),(c,d))]];（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];实习题若矩阵Am×n 中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。
假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。
第五章答案5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。
【解答】（1）k=2(i-1)+j(2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余）5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。
1．最大子段和问题：给定整数序列 n a a a ,,,21 ，求该序列形如∑=ji k k a 的子段和的最大值： ⎭⎬⎫⎩⎨⎧∑=≤≤≤j i k k n j i a 1max ,0max 1) 已知一个简单算法如下：int Maxsum(int n,int a,int& besti,int& bestj){int sum = 0;for (int i=1;i<=n;i++){int suma = 0;for (int j=i;j<=n;j++){suma + = a[j];if (suma > sum){sum = suma;besti = i;bestj = j;}}}return sum;}试分析该算法的时间复杂性。
2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。
3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。
分析算法的时间复杂度。
（提示：令1()max ,1,2,,j ki j n k i b j a j n ≤≤≤===∑）解：1）分析按照第一章，列出步数统计表，计算可得)(2n O2）分治算法：将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种可能：①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同；②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；③a[1:n]的最大子段和为两部分的字段和组成，即j n j i l n i j a a a a a+++++=+⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢∑ 122；intMaxSubSum ( int *a, int left , int right){int sum =0;if( left==right)sum = a[left] > 0? a[ left]:0 ;else{int center = ( left + right) /2;int leftsum =MaxSubSum ( a, left , center) ;int rightsum =MaxSubSum ( a, center +1, right) ;int s_1 =0;int left_sum =0;for ( int i = center ; i >= left; i--){left_sum + = a [ i ];if( left_sum > s1)s1 = left_sum;}int s2 =0;int right_sum =0;for ( int i = center +1; i <= right ; i++){right_sum + = a[ i];if( right_sum > s2)s2 = right_sum;}sum = s1 + s2;if ( sum < leftsum)sum = leftsum;if ( sum < rightsum)sum = rightsum;}return sum;}int MaxSum2 (int n){int a；returnMaxSubSum ( a, 1, n) ;}该算法所需的计算时间T(n)满足典型的分治算法递归分式T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)3）设}{max )(1∑=≤≤=j i k k j i a j b ,则最大子段和为).(max max max max max 11111j b a a n j j i k k j i n j j i k k n j n i ≤≤=≤≤≤≤=≤≤≤≤==∑∑ 最大子段和实际就是)}(,),2(),1(max{n b b b .要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。
},)1(max {},}{max max {},}{max {}{max )(1111111j j j j j i k k j i j j i j j i k k j i k k j i a a j b a a a a a a a j b +-=+=+==∑∑∑-=-≤≤-≤≤-==≤≤若0)1(>-j b , j a j b j b +-=)1()(；若0)1(≤-j b ，j a j b =)(。
因此，计算)(j b 的动态规划的公式为：.1},,)1(max {)(n j a a j b j b j j ≤≤+-=intMaxSum (int* a ，int n ){int sum = 0, b = 0，j=0;for( int i=1;i<=n;i++){if( b >0)b = b + a [i];else b = a [i];end{if}if( b > sum) sum = b;j=i ；end{if}}return sum;}自行推导，答案：时间复杂度为O （n ）。
2.动态规划算法的时间复杂度为O （n ）（双机调度问题）用两台处理机A 和B 处理n 个作业。
设第i 个作业交给机器A 处理时所需要的时间是i a ，若由机器B 来处理，则所需要的时间是i b 。
现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。
设计一个动态规划算法，使得这两台机器处理完这n 个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。
以下面的例子说明你的算法：解：（思路一）删除（思路二）在完成前k 个作业时，设机器A 工作了x 时间，则机器B 最小的工作时间是x 的一个函数。
设F[k][x]表示完成前k 个作业时，机器B 最小的工作时间，则其中k b x k F +-)](1[对应第k 个作业由机器B 来处理（完成k-1个作业时机器A 工作时间仍是x ，则B 在k-1阶段用时为)](1[x k F -）；而)](1[k a x k F --对应第k 个作业由机器A 处理（完成k-1个作业，机器A 工作时间是x-a[k]，而B 完成k 阶段与完成k-1阶段用时相同为)](1[k a x k F --）。
则完成前k 个作业所需的时间为)}]([,max{x k F x1）当处理第一个作业时，a[1]=2,b[1]=3;机器A 所花费时间的所有可能值范围：0 ≤x ≤a[0].x<0时，设F[0][x]= ∞，则max(x, ∞)= ∞；0≤x<2时，F[1][x]=3，则Max(0,3)=3，x ≥2时，F[1][x]=0，则Max(2,0)=2；2）处理第二个作业时：x 的取值范围是：0 <= x <= (a[0] + a[1])，当x<0时，记F[2][x] = ∞；以此类推下去（思路三）假定n 个作业的集合为{}n S n ,,2,1 =。
设J 为n S 的子集，若安排J 中的作业在机器A 上处理，其余作业在机器B 上处理，此时所用时间为⎪⎪⎭⎫ ⎝⎛=∑∑∈∈J S j j Jj j b a J T \,max )(，则双机处理作业问题相当于确定n S 的子集J ，使得安排是最省时的。
即转化为求J 使得)}({min J T nS J ⊆。
若记{}1,,2,11-=-n S n ，则有如下递推关系： ⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛+=⎪⎪⎭⎫ ⎝⎛∑∑∑∑∑∑∈∈⊆∈∈⊆∈∈⊆J S j j n J j j S J J S j j J j j n S J I S j j I j j S I b b a b a a b a n n n \\\,max min ,,max min min ,max min 11－－（思路四）此问题等价于求（x1,……x n），使得它是下面的问题最优解。
min max{x1a1+……x n a n，(1-x1)b1+……+(1-x n)b n} x i=0或1，i=1~n基于动态规划算法的思想，对每个任务i，依次计算集合S(i)。
其中每个集合中元素都是一个3元组（F1,F2,x）。
这个3元组的每个分量定义为F1:处理机A的完成时间F2：处理机B的完成时间x：任务分配变量。
当x i=1时表示将任务i分配给处理机A，当x i=0时表示分配给处理机B。
初始时，S(0)={(0,0,0)}令F=按处理时间少的原则来分配任务的方案所需的完成时间。
例如，当（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)时，按处理时间少的原则分配任务的方案为（x1,x2,x3,x4,x5,x6）=（1,1,0,1,0,1）因此，F=max{2+5+10+2,7+5}=19。
然后，依次考虑任务i，i=1~n。
在分配任务i时，只有2种情形，x i=1或x i=0。
此时，令S(i)={S(i-1)+(a i,0,2i)}U{S(i-1)+(0,b i,0)}在做上述集合并集的计算时，遵循下面的原则：①当（a,b,c）,(d,e,f)ЄS(i)且a=d,b<=e时，仅保留（a,b,c）；②仅当max{a,b}<=F时，(a,b,c)ЄS(i)最后在S(n)中找出使max{F1,F2}达到最小的元素，相应的x即为所求的最优解，其最优值为max{F1,F2}。
当（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)时,按处理时间少的原则分配任务的方案为（x1,x2,x3,x4,x5,x6）=（1,1,0,1,0,1）因此，F=max{2+5+10+2,7+5}=19。
S(0)={(0,0,0)};S(1)={(2,0,2),(0,3,0)}S(2)={(7,0,6),(5,3,4),(2,8,2),(0,11,0)}S(3)={(14,0,14),(12,3,12),(9,8,10), (7,4,6),(5,7,4),(2,12,2),(0,15,0)}S(4)={(19,8,26), (17,4,22),(15,7,20),(12,12,18),(14,11,14),(9,19,10),(7,15,6),(5,18,4)}S(5)={(19,11,46), (12,15,38),(19,11,26), (17,7,22),(15,10,20),(12,15,18),(14,14,14),(7,18,6)}S(6)={(14,15,102),(19,7,86),(17,10,84),(14,15,82), (9,18,70),(12,19,38),(15,14,20),(12,19,18)} max(F1,F2)最小的元组为(14,15,102),(14,15,82),(15,14,20)所以，完成所有作业最短时间是15，安排有三种：（1,1,0,0,1,1），（1,0,0,1,0,1）,(0,1,0,1,0,0)（思路五）C++ 源代码如下:#include<iostream>usingnamespace std;constint MAXS = 70;constint MAXN = 10;bool p[MAXS][MAXS][MAXS];int a[MAXS],b[MAXS];int schduleDyn(int * a,int * b,int n,int mn){ int i,j,k;//===========数组初始化===================for(i = 0; i <= mn; i++)for(j = 0; j <= mn; j++){ p[i][j][0] = true;for(k = 1 ; k <= n; k++)p[i][j][k] = false;}//===========动态递归=============for(k = 1; k <= n; k ++)for(i = 0; i <= mn; i++)for(j = 0; j <= mn; j++){ if( (i - a[k-1]) >= 0)p[i][j][k] = p[i - a[k-1]][j][k-1];if( (j - b[k-1]) >= 0)p[i][j][k] = (p[i][j][k] | p[i][j-b[k-1]][k-1]);}//================求结果=====================int rs = mn;int temp = 0;for(i = 0; i <= mn; i++)for(j = 0; j <= mn ; j++){if(p[i][j][n]){ temp = i > j ? i : j;if(temp < rs)rs = temp;}}return rs;}void main(){int i,n,m = 0,mn = 0;//=============初始化========================cin >> n;for(i = 0; i < n; i++){ cin >> a[i];if(a[i] > m)m = a[i];}for(i = 0; i < n; i++){cin >> b[i];if(b[i] > m)m = b[i];}mn = m * n;//=========动态规划求解=================cout << schduleDyn(a,b,n,mn) << endl; system("pause");}对于例子: n = 6 ;(a1,….,a6) = (2 5 7 10 5 2),(b,1…,b6) = (3 8 4 11 3 4); 由于求解过程比较繁锁,这里只说个大概算法执行过程,首先,用p[i][j][k],记录下对于第k 个作业,能否在对于a 机器是i 时间以内,对于b 机器是j 时间以内完成,如果能,则把p[i][j][k]设为true.经过了设置后,求对于n 个作业的所有可能的值为p[i][j][n],对min(max(i,j)),结果为15.即为所得到的结果.3．考虑下面特殊的整数线性规划问题试设计一个解此问题的动态规划算法，并分析算法的时间复杂度。
