习题答案第四章算法设计与分析吕国英

1、算法设计与分析(第二版)主编：吕国英习题答案第四章1.#i ncludeint main( void)int buf1OO;int n;int i,j,k;sca nf(%d,&n);for(i=0;i n;i+)bufi=2;for(i=0;i n-1;i+)for(j=0;j n _i_1;j+)bufj+=2;for(j=0;j=10)bufj+1+=bufj/10;bufj=bufj%10;for(i=n-1;i=0;i-)prin tf(%d,bufi);pri ntf(n);return 0;2.#i ncludeint main( void)int n=2;int i;for(i

2、=1;i=9;i+)n=( n+2)*2;prin tf(%dn, n);return 0;3.#i ncludeint main( void)int a=54;int n;int m;printf(计算机先拿3张牌n);a=a-3;while(a=0)printf(还剩 d张牌 n,a);prin tf(你拿几张？请输入：);sca nf(%d,&n);if(n 4| na)printf(错误！重新拿牌n);con ti nue;a=a-n;printf(还剩 d张牌 n,a);if(a=0)break;m=5-n;printf(计算机拿 %dn,m);a=a-m;return 0;4.#i

3、 ncludeint d;int a1,a2;int fun (i nt n);int main( void)int n;prin tf( n=?,d=?,a 仁？,a2=?);sea nf(%d%d%d%dn,&n,& d, &a1, &a2); prin tf(%dn,fu n(n);return 0;int fun (i nt n)if(n=1)return a1;if(n=2)return a2;return fun(n-2)-(fu n(n-1)-d)*2;5.#i ncludechar chess 88;int is_safe(i nt row,i nt col);int quee

4、 n(i nt row,i nt col,i nt n);int main( void)int i,j;for(i=0;i8;i+)for(j=0;j8;j+) chessij=X： quee n(O,O,O);for(i=0;i8;i+)for(j=0;j8;j+)prin tf(%c ,chessij);pri ntf(n);return 0;int is_safe(i nt row,i nt col)int i,j;for(i=0;i8;i+)if(chessrowi=Q)return 0;if(chessicol=Q)return 0;i=row;j=col;while(i!=-1 &

5、j!=-1)if(chessi-j-=Q)return 0;i=row;j=col;while(i!=-1 &j!=8)if(chessi-j+=Q) return 0;i=row;j=col;while(i!=8&j!=-1)if(chessi+j-=Q) return 0;i=row;j=col;while(i!=8&j!=8)if(chessi+j+=Q) return 0;return 1;int quee n(i nt row,i nt col,i nt n)int i,j;int result=0;if(n=8)return 1;elseif(is_safe(row,col)che

6、ssrowcol=Q;for(i=0;i8;i+)for(j=0;j:-refurn q#inc-udecssphvinf main(void)宀in二for7r17-10000_.+)宀if(i&2HH1QOQOi&3HH2QOQOi&5HH4QOQOi&6HH5QOQOi&7HH0) prin=t(=&2rrurefurn q8.#i ncludeint main( void)int i;int sum;int a1,a2,a3,a4;for(i=1000;i=9999;i+)a1=i%10;a2=i/10%10;if(a1!=a2)a3=i/100%10;if(a1!=a3&a2!=a3

7、)a4=i/1000;if(a1!=a4&a2!=a4&a3!=a4)sum=(a1+a2+a3+a4)*(a1+a2+a3+a4);if(i%sum=0)prin tf(%dn,i);return 0;9.#i nclude#defi ne N 10void max_min (i nt *a,i nt m,i nt n ,i nt *min 1,i nt *min 2,i nt *max1,i nt *max2);int main( void)int aN=2,3,4,5,34,7,9,6,43,21;int min 1,mi n2;int max1,max2;max_mi n(a,0,N-

8、1,&mi n1,&mi n2,&max1,&max2);pr in tf(mi n1=%dnmi n2=%dnmax1=%dnmax2=%dn,mi n1,mi n2,max1,max2); return 0;void max_min (i nt *a,i nt m,i nt n ,i nt *min 1,i nt *min 2,i nt *max1,i nt *max2)int lmi n1,lmi n2,lmax1,lmax2;int rmi n1,rmi n2,rmax1,rmax2;int mid;if(m=n)*min 1=*m in 2=*max1=*max2=am;elseif

9、(m=n-1)if(ama n)*min 1=am;*min 2=a n;*max1=a n;*max2=am;else*min 1=a n;*min 2=am;*max1=am;*max2=a n;elsemid=(m+n)/2;max_mi n( a,m,mid，&l mi n1,&l mi n2,&l maxi,&lm ax2); max_mi n( a,mid+1, n,&rmi n1,&rmi n2,&rmax1,&rmax2); if(lmi nivrmi n1)if(lmi n2rmi n1)*mi n1=lmi n1;*mi n2=lmi n2;else*mi n1=lmi n

10、1;*mi n2=rmi n1;elseif(rmi n2rmax1)if(lmax2rmax1)*max1=lmax1;*max2=lmax2;else*max1=lmax1;*max2=rmax1;elseif(rmax2lmax1)*max1=rmax1;*max2=rmax2;else*max1=rmax1;*max2=lmax1;10.#i ncludeint add(i nt *a,i nt flag,i nt right);int main( void)int a10=1,2,3,4,5,6,7,8,9,10;int sum=add(a,0,9);prin tf(%dn,sum)

11、;return 0;int add(i nt *a,i nt flag,i nt right)int mid;if(flag=right)retur n aflag;elseif(flag=right-1)retur n aflag+aright;elsemid=(flag+right)/2;retur n add(a,flag,mid)+add(a,mid+1,right); 11.#i ncludeint main( void)int a53=-50,17,-42,-47,-19,-3,36,-34,-43,-30,-43,34,-23,-8,-45;int i,j;int max ,n;

12、int sum=0;for(i=0;i5;i+)max=ai0;n=0;for(j=1;jmax)max=aij;n=j;sum+=max;pri ntf(a%d%d=%dn,i, n,max);prin tf(%dn,sum);return 0;12./* File: n ewmai n.c* Author: nirn ava* Created on 2010 年 4 月 22 日,下午 5:21*/#i nclude#in clude#defi ne N 4void matrix_mul( int *mul1,i nt *mul2,i nt *mul3,i nt len gth); voi

13、d matrix_add_sub(i nt * A,i nt * B,i nt * C,i nt m,char ch);void update_half_value(i nt * A,i nt * B,i nt m);void get_half_value(int * A,int * B,int m);int main( void)int i,j;int mul1N*N=1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6;int mul2N*N=7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2;int mul3N*N;matrix_mul(mul1,mul2,m

14、ul3,N);for(i=0;iN*N;i+)prin tf(%5d,mul3i);if(i+1)%N=0)pri ntf(n);return 0;void matrix_add_sub(i nt * A,i nt * B,i nt * C,i nt m,char ch)int i;for(i=0;im*m;i+)if(ch=+)Ci=Ai+Bi;elseCi=Ai-Bi;void update_half_value(i nt * A,i nt * B,i nt m)int i,j;for(i=0;im/2;i+)for(j=0;jm/2;j+)Bi *m+j=A i *m/2+j;void

15、get_half_value(int * A,int * B,int m)int i,j；for(i=0;im/2;i+)for(j=0;jm/2;j+)Ai *m/2+j=B i *m+j;void matrix_mul(int *A,int *B,int *C,int m)if(m=2)in t D,E,F,G,H,I,J;D=A0*(B1-B3);E=A3*(B2-B0);F=(A2+A3)*B0;G=(A0+A1)*B3;H=(A2-A0)*(B0+B1);I=(A1-A3)*(B2+B3);J=(A0+A3)*(B0+B3);C0=E+I+J-G;C1=D+G;C2=E+F;C3=D

16、+H+J-F;return ;elseint A1m*m/4,A2m*m/4,A3m*m/4,A4m*m/4;int B1m*m/4,B2m*m/4,B3m*m/4,B4m*m/4;int C1m*m/4,C2m*m/4,C3m*m/4,C4m*m/4;int Dm*m/4,Em*m/4,Fm*m/4,Gm*m/4,Hm*m/4,lm*m/4,Jm*m/4;int temp1m*m/4,temp2m*m/4;get_half_value(A1,&A0,m);get_half_value(A2,&Am/2,m);get_half_value(A3,&Am*m/2,m);get_half_valu

17、e(A4,&Am*m/2+m/2,m);get_half_value(B1,&B0,m);get_half_value(B2,&Bm/2,m);get_half_value(B3，&Bm*m/2,m);get_half_value(B4,&Bm*m/2+m/2,m);matrix_add_sub(B2,B4,temp1,m/2,-);matrix_mul(A1,temp1,D,m/2);matrix_add_sub(B3,B1,temp1,m/2,-);matrix_mul(A4,temp1,E,m/2);matrix_add_sub(A3,A4,temp1,m/2,+);matrix_mul

18、(temp1,B1,F,m/2);matrix_add_sub(A1,A2,temp1,m/2,+);matrix_mul(temp1,B4,G,m/2);matrix_add_sub(A3,A1,temp1,m/2,-);matrix_add_sub(B1,B2,temp2,m/2,+);matrix_mul(temp1,temp2,H,m/2);matrix_add_sub(A2,A4,temp1,m/2,-);matrix_add_sub(B3,B4,temp2,m/2,+);matrix_mul(temp1,temp2,l,m/2);matrix_add_sub(A1,A4,temp1

19、,m/2,+);matrix_add_sub(B1,B4,temp2,m/2,+);matrix_mul(temp1,temp2,J,m/2);matrix_add_sub(E,l,temp1,m/2,+);matrix_add_sub(J,G,temp2,m/2,-);matrix_add_sub(temp1,temp2,C1,m/2,+); matrix_add_sub(D,G,C2,m/2,+);matrix_add_sub(E,F,C3,m/2,+);matrix_add_sub(D,H,temp1,m/2,+);matrix_add_sub(J,F,temp2,m/2,-);matr

20、ix_add_sub(temp1,temp2,C4,m/2,+);update_half_value(C1,&C0,m);update_half_value(C2,&Cm/2,m);update_half_value(C3,&Cm*m/2,m);update_half_value(C4,&Cm*m/2+m/2,m);return ;13.#i ncludeint main( void)int a 67=16,4,3,12,6,0,3,4,-5,6,7,0,0,2,6,0,-1,-2,3,6,8,5,3,4,0,0,-2,7,-1,7,4,0,7,-5,6,0,-1,3,4,12,4,2;int

21、 b 67,c67;int i,j,k;int max;int flag;int temp;for(i=0;i6;i+)for(j=0;j7;j+)bij=aij; cij=-1;for(i=1;i5;i+)for(j=0;j7;j+)max=0;for(k=j-2;k=j+2;k+) if(k6)break;elseif(bij+bi-1kmax) max=bij+bi-1k;flag=k;bij=max;cij=flag;for(j=1；j=5;j+)max=O;for(k=j-2;k=j+2;k+)if(k6)break;elseif(bij+bi-1kmax)max=bij+bi-1k

22、; flag=k;bij=max;cij=flag;max=0;for(j=1;jmax)max=bij;flag=j;prin tf(%dn,max);temp=ciflag;prin tf(%5d,aitemp);for(j=i;j0;j-)temp=cjtemp;pri ntf(%5d,a卜1temp);pri ntf(n);return 0;14.#i ncludeint main( void)int A6=0,3,7,9,12,13;int B6=0,5,10,11,11,11;int C6=0,4,6,11,12,12;int AB6 6;int temp6;int abc 6;i

23、nt max;int flag;int i,j,k;for(i=0;i=5;i+)max=0;for(j=0;jmax) max=ABij;tempi=max;max=0;for(i=0;imax)max=abci;flag=i;pri ntf(max=%dn,max);pri ntf(c=%dn,5-flag); max=max-C5-flag; for(i=0;i=flag;i+)if(ABflagi=max)pri ntf(b=%dn,i);prin tf(a=%dn,flag-i);break;return 0;16.#i nclude#defi ne N 100int search(

24、int *a,int left,int right); int sum_buf(i nt *a,i nt left,i nt right); int main( void)int aN;int i;int s;for(i=0;iN;i+)ai=1;a24=2;s=search(a,0,N-1);prin tf(%dn,s);return 0;int sum_buf(i nt *a,i nt left,i nt right)int i;int sum=0;for(i=left;i=right;i+) sum+=ai;return sum;int search(int *a,int left,in

25、t right)int mid=(left+right)/2;if(left=right-1)if(aleftsum_buf(a,mid+1,right) return search(a,left,mid-1);elseif(sum_buf(a,left,mid-1)sum_buf(a,mid+1,right) return search(a,left,mid);elseretur n search(a,mid+1,right);17.#i ncludeint job 62=3,8,12,10,5,9,2,6,9.3,11,1;int x6,bestx6,f1=0,bestf,f27=0;vo

26、id try(i nt i);void swap(i nt a,i nt b);int main( void)int i,j;bestf=32767;for(i=0;i6;i+)xi=i;try(0);for(i=0;i6;i+)prin tf(%d ,bestxi);prin tf(nbestf=%dn,bestf); return 0;void try(i nt i)int j；if(i=6) for(j=0;j6;j+) bestxj=xj;bestf=f2i;elsefor(j=i;jf1) f2i+1=f2i+jobxj1;elsef2i+1=f1+jobxj1;if(f2i+1be

27、stf)swap(i,j);try(i+1);swap(i,j);f1=f1-jobxj0;void swap(i nt i,i nt j)int temp;temp=xi;xi=xj;xj=temp;18.#i nclude#defi ne N 5 N个数字#defi ne M 2 M个加号char bufN;int aN;char bM+1N;in t cM+1;int try(i nt t);void swap( int t1,i nt t2);int add();void output();in t mi n=99999;int mai n()int i;for(i=0;iN;i+)s

28、ca nf(%c,&bufi);a0=0;for(i=1;i=M;i+)ai=1;for(;i=N)sum=add();if(summi n)min=sum;for(i=0;iM+1;i+)ci=atoi(bi);/*for(i=0;iN;i+)prin tf(%d,ai);pri ntf(n);*/ elsefor(j=t;jN;j+)/if(at!=aj)swap(t,j);try(t+1);swap(t,j);/else/try(t+1);void swap(i nt t1,i nt int t;t=at1;at1=at2;at2=t;int add()int sum=0;int i=0

29、;int j;int k=0;int h=0;for(i=0;iM+1;i+) for(j=0;jN;j+) bij=Q;i=0;j=0;h=0;k=0;for(j=0；jN;j+)if(aj=1)h=0;i+；bih=bufjpri ntf(%d “,atoi(bi);pri ntf(%d %d %c n,i,h,bih);h+;elsebih=bufj;pri ntf(%d %d %c n,i,h,bih);pri ntf(%d ,atoi(bi);h+;/*for(i=0;iM+1;i+)for(j=0;jN;j+)pri ntf(%c ,bij);pri ntf(n);*/for(i=0;iM+1;i+)sum+=atoi(bi);return sum;void output()int i;for(i=0;iM+1;i+)pri ntf(%d,atoi(b