华中科技大学：《计算机算法基础》 第一章 习题

第一章 Procedure F(A, n) ←n; count0;m←0; while j20 do if a[]=1 then count+count 1 else if count mod 2#o then m←m+1; endif count←-0; endif 1; repeat if m>0 then return(false) else return(true) endif Endf

第一章 Procedure F(A,n) i←n; count←0;m←0; while i≥0 do if A[i] =1 then count←count + 1; else if count mod 2 ≠ 0 then m←m+1; endif count←0; endif i←i-1; repeat if m＞0 then return(false) else return(true) endif End F

int judge(int al l, int n) int I, flag =0 for(=1;-sn;i++){ Whe(A[]==1&&≤n) flag =(flag +A[i++]%2 if(flag) return(false) return(true);∥如果没有任何连续为1的序列?

int judge(int A[ ],int n) { int I, flag = 0; for(i=1;i≤n;i++) { while(A[i]== 1 && i≤n) flag =(flag + A[i++])%2; if(flag) return(false); } return(true); //如果没有任何连续为1的序列？ }

int check(int al ], int n int i=0, k=0, flag =1 while(isnt k=0 Whle(A[==0)计++;∥&i<n Whle(A[==1)k++;∥/i++&&i<n if(k/ i flag=0 break return(fag);∥如果没有任何连续为1的序列?

int check(int a[ ],int n) { int i=0, k=0, flag = 1; while(i＜n) { k=0; while(A[i]== 0) i++; //&&i<n while(A[i]== 1) k++; // i++ && i<n if(k%2) { flag = 0; break; } return(flag); //如果没有任何连续为1的序列？ }

第二章 2.化简递推关系式 ∴g(n)=0(1) ∴可令g(n)=c1(或简单令g(n)=1) 同理 f(n)=0(n) ∴可令f(n)=c2n(或简单令f(n)=n,或f(n)=c2n+b), 可设c1=C2=C 化简 T(n)=2T(n/2)+f(n) 2T(n/2)+cn =4T(n/4)+2(cn/2)+cn=4T(n/4)+2cn 2kT(n/2k)+kcn 若n=2,则k=logn .T(n)=cn+cnlogn=o(nlogn) 当n∈[2k,2k+1),T(n)=cn+ cologne=e( nlogn)

第二章 2. 化简递推关系式 ∵g(n)=O(1) ∴可令 g(n)=c1(或简单令g(n)=1) 同理， ∵f(n)=O(n) ∴可令 f(n)=c2n(或简单令f(n)=n，或f(n)=c2n＋b), 可设c1=c2=c 化简 T(n)=2T(n/2)+f(n) =2T(n/2)+cn =4T(n/4)+2(cn/2)+cn=4T(n/4)+2cn =… =2kT(n/2k)+kcn 若n=2k ,则k=logn ∴T(n)=cn+cnlogn=O(nlogn) 当n∈[2k,2k+1), T(n)=cn+cnlogn=Θ(nlogn)

g(n)=0(1 可令g(n)=c1(或简单令g(n)=1) 同理 f(n)=0(1) 可令f(n)=c2(或简单令f(n)=1), 可设C1=C2=C 化简 T(n)=2T(n/2)+f(n) =2T(n/2)+c =4T(n/4)+2c+c =8T(n/8)+22c+2c+c=… 2T(n/2k)+(1+2+22+…+2k-1) C-cn+(2k- C . cn-c=o(n)

∵g(n)=O(1) ∴可令 g(n)=c1(或简单令g(n)=1) 同理， ∵f(n)=O(1) ∴可令 f(n)=c2(或简单令f(n)=1), 可设c1=c2=c 化简 T(n)=2T(n/2)+f(n) =2T(n/2)+c =4T(n/4)+2c+c =8T(n/8)+22c+2c+c=… =2kT(n/2k)+(1+2+22+…+2k-1)c=cn+(2k-1)c =2cn-c=O(n)

典型错误 令g(n)=a,f(mn)=bn+c(a,b,c为常数) 则T(n)=2T(n/2)+bn+c =4T(n/4)+2bn+2c+bn+c =2T(n/2)+bn(1+2+…+2k-1) +c(1+2+…+2k-1) 2T(n/2k)+(bn+c)(2k-1) 故得,T(n)=(n2)

典型错误 令g(n)=a,f(n)=bn+c(a,b,c为常数） 则T(n)=2T(n/2)+bn+c =4T(n/4)+2bn+2c+bn+c =… =2kT(n/2k)+bn(1+2+…+2k-1) +c(1+2+…+2k-1) =2kT(n/2k)+(bn+c)(2k-1) 故得，T(n)=Θ(n2)

5.三分法 low mid2 high mid1=low L (high-low)/3] mil=(high+lon)/3」 mid2=high- LChigh-low)/3 2=2(high+low)/3

5.三分法 low mid1 mid2 high mid1=low + mid2=high - (high −low)/ 3 (high −low)/ 3   2  2( )/ 3 1 ( )/ 3 mid high low mid high low = + = +

E=2|+3n 二元比较树=>三元比较树?

E=2I+3n 二元比较树＝>三元比较树？

第三章 ①若k个作业可以按照题目中给出的方法安排执行时间又不 违反任何作业的期限要求,显然J可行。 ②若J可行,则对J应该存在一个题目中所说的处理序列。设 这一序列是8=i1i2…ik 序列的特点是:若作业i在]时刻执行,i不违反期限 要求,且其后的k一j个作业也不违反各自的期限。i是按照 从后往前找其执行时间j:后边的k-j个执行单元或者不满足 其期限要求,或已经为先前考虑的其它作业占用,而这些作 业是不能被推迟执行的

第三章 9. ①若k个作业可以按照题目中给出的方法安排执行时间又不 违反任何作业的期限要求，显然J可行。 ②若J可行，则对J应该存在一个题目中所说的处理序列。设 这一序列是δ=i1i2…ik 序列的特点是：若作业ij在j时刻执行， ij不违反期限 要求，且其后的k-j个作业也不违反各自的期限。ij是按照 从后往前找其执行时间j：后边的k-j个执行单元或者不满足 其期限要求，或已经为先前考虑的其它作业占用，而这些作 业是不能被推迟执行的

证1 若J是可行解,则必存在调度序列δ r1r·r1 使得 d;≥j,1≤j≤k 现设按题目要求调整序列δ’。 在8’的调度序列中任取1个作业r;(1≤i≤k) ●若i=dn,则r;的位置不变 ●若i<d1且dx1=j,则将r调整到j处,原r1+1,r+2,…,r向前移 位,可保持调整后的d-≥j(1≤j≤k) 每做一次调整后,调整的元素固定下来。若调整过程中,r;要调的 地方的作业r;已被固定,则继续往前寻找,直到找到没有被固定的作业 处 每次在δ’中选取1个没有固定下位置的作业做上述调整,k次后作 业顺序定下来,且能保持作业的执行时间不不违反作业期限,故J可行时, 用题中给出的方法可以解决作业排序。 存在的问题:调整后得到的调度序列可能不等于题目中给出的调度 序列

证1： 若J是可行解，则必存在调度序列δ’=r1r2…rk，使得 drj≥j,1≤j≤k 现设按题目要求调整序列δ’。 在δ’的调度序列中任取1个作业ri(1≤i≤k) ●若i=dri，则ri的位置不变 ●若i＜dri且dri=j，则将ri调整到j处，原ri+1,ri+2,…,rj向前移一 位，可保持调整后的drj≥j（1≤j≤k） 每做一次调整后，调整的元素固定下来。若调整过程中，ri要调的 地方的作业rj已被固定，则继续往前寻找，直到找到没有被固定的作业 处。 每次在δ’中选取1个没有固定下位置的作业做上述调整，k次后作 业顺序定下来，且能保持作业的执行时间不不违反作业期限，故J可行时， 用题中给出的方法可以解决作业排序。 存在的问题：调整后得到的调度序列可能不等于题目中给出的调度 序列