1、平时作业1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。a) int BinarySearch(Type a, const Typeif (x = am) return m;if (x = l) int m = (l+r)/2;if (x = am) return m;if (x l) int m = (l+r)/2;if (x = am) return m;if (x l) 要考虑到 数组只有一个元素的情况 所以应该是 r=l ;2、O(1)空间子数组环卫算法：设 a0:n-1是一个 n 维数组，k（1 k n-1）是一个非负整数。试设计一个算法将子数组 a0 : k-
2、1与 ak+1 : n-1换位。要求算法在最坏情况下耗时O(n)，且只用 O(1)的辅助空间。答：最简单的方法就是循环(n-k-1)次，将 a 数组的末尾数字插入到 a0之前。具体做法： (1) 首先开辟一个额外空间 temp 用于存放每一次 a 数组的末尾数据。 (2) temp #includeint main()int n;int i,j,s;int buf106;char *in=“input.txt“,*out=“output.txt“;FILE *ip,*op;if(ip=fopen(in,“r“)=NULL)return 1;if(op=fopen(out,“w“)=NULL)r
3、eturn 2;fscanf(ip,“%d“,fclose(ip);buf1=1;buf2=2;buf3=2;for(i=4;i*2 #define m 10 /快速排序 void QuickSort(int R,int s,int t) int i=s,j=t; int tmp; if(si Ri=Rj; while(i=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int i,int j,int *x,int bmm) if(id; coutxi; yi=xi; int cmm=0,bmm=0; QuickSort(x,0
4、,d-1); LCSLength(x,y,d,c,b); cout using namespace std;#define M 50/最大活动数struct Active int b;/开始时间 int f;/结束时间int no;/预安排会场号 aM; /两元素交换位置 void swap(Active a=b; b=t; void main() int k, i,j; coutk; coutaj.b) swap(ai,aj);if(ai.b=aj.b)if(ai.faj.f) swap(ai,aj);int int sum=1;/使用的会场数初始化 int n; a1.no=sum; fo
5、r(i=2;i ak) k+; ak = ak - 1 + 1; n -= ak; if (n = ak) ak+; n-; for (int i = 0; i int n,c; int a100; int current100; /存放当前选择的情况 int best100; /存放最后选择的子集合，besti=1，表示包含，反之即不包含。 int d=1; /判断有无满足的情况 int d2=0; /是否已经选出子集和 void Back(int m,int count); int main() int i,j; scanf(“%d %d“, for(i=0;in)return; if(c
6、ount=c) d=0; /有满足的子集和 if(d2) return 0; for(k=0;k 0 xi = yi 时 , cij = ci-1j-1 + 1 当 i , j 0 xi != yi 时 , cij = max cij-1 , ci-1j public class LSC private int c,b; private int m,n; private char A,B; public LSC(char A,char B) this.A=A; this.B=B; m=A.length; n=B.length; c=new intm+1n+1; b=new intm+1n+1;
7、 for(int i=0;i=cij-1) cij=ci-1j; bij=1; /* * 情况 */ else cij=cij-1; bij=2; return cmn; public void print(int i,int j) if(ia2?a1:a2; public static void main(String args) char A=g,f,d,a,s,d,a,c; char B=g,c,f,a,t,0,c,c; LSC lsc=new LSC(A,B); System.out.println(lsc.LSCLength2(7,7); 9、记矩阵连乘积 。 确定计算 A1:n的最
8、优计算次序，使得所1,.,ijAiji需数乘的次数最少。1、说明矩阵连乘计算次序问题的最优解包含着其子问题的最优解，即最优子结构性质。2、该问题具备子问题的重叠性质。3、说明采用动态规划方法可以解决该问题。4、设计该算法，分析算法的复杂性。答：计算 Ai:j的最优次序所包含的计算矩阵子链 Ai:k和 Ak+1:j的次序也是最优的。设计算 Ai:j，1ijn，所需要的最少数乘次数 mi,j，则原问 题的最优值为 m1,n 当 i=j 时，Ai:j=Ai，无需计算，因此，mi,j=0，i=1,2,n 当 i #define total 10 float ptotal,wtotal,ttotal; void greedy_knaPsack(int x,int c) int note,i; float max; while(1) note=0; max=0; for(i=0;ix;i+) if(maxpi/wi) note=i; if(wnotec) tnote=1; c-=wnote; else tnote=c/wnote; break; int main() int i=0,n=0; float cu; printf(“请输入物品总数（不大于%d）与背包的容量：“,total); while(1)
