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

算法设计与分析（第二版）主编：吕国英习题答案第四章1.#include int main(void) int buf100; int n; int i,j,k; scanf(%d,&n); for(i=0;in;i+) bufi=2; for(i=0;in-1;i+) for(j=0;jn-i-1;j+) bufj+=2; for(j=0;j=10) bufj+1+=bufj/10; bufj=bufj%10; for(i=n-1;i=0;i-) printf(%d,bufi); printf(n); return 0; 2.#includeint main(void)int n=2;int i;for(i=1;i=9;i+)n=(n+2)*2;printf(%dn,n);return 0;3.#includeint main(void)int a=54;int n;int m;printf(计算机先拿3张牌n);a=a-3;while(a=0)printf(还剩%d张牌n,a);printf(你拿几张？请输入：);scanf(%d,&n);if(n4|na)printf(错误！重新拿牌n);continue;a=a-n;printf(还剩%d张牌n,a);if(a=0)break;m=5-n;printf(计算机拿%dn,m);a=a-m;return 0;4.#includeint d;int a1,a2;int fun(int n);int main(void)int n;printf(n=?,d=?,a1=?,a2=?);scanf(%d%d%d%dn,&n,&d,&a1,&a2);printf(%dn,fun(n);return 0;int fun(int n)if(n=1)return a1;if(n=2)return a2;return fun(n-2)-(fun(n-1)-d)*2;5.#includechar chess88;int is_safe(int row,int col);int queen(int row,int col,int n);int main(void)int i,j;for(i=0;i8;i+)for(j=0;j8;j+)chessij=X;queen(0,0,0);for(i=0;i8;i+)for(j=0;j8;j+)printf(%c ,chessij);printf(n);return 0;int is_safe(int row,int 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&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 queen(int row,int col,int n)int i,j;int result=0;if(n=8)return 1;elseif(is_safe(row,col)chessrowcol=Q;for(i=0;i8;i+)for(j=0;j0)break;if(result0)return 1;elsechessrowcol=X;return 0;elsereturn 0;6.#includeint main(void)int i,j,k;for(i=1;i=33;i+)for(j=1;j=50;j+)k=100-i-j;if(k%2=0)if(3*i+2*j+k/2=100)printf(大马%dn中马%dn小马%dnnn,i,j,k);return 0;7.#includeint main(void)int i;for(i=1;i=10000;i+)if(i%2=1&i%3=2&i%5=4&i%6=5&i%7=0)printf(%dn,i);return 0;8.#includeint 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)a4=i/1000;if(a1!=a4&a2!=a4&a3!=a4)sum=(a1+a2+a3+a4)*(a1+a2+a3+a4);if(i%sum=0)printf(%dn,i);return 0;9.#include #define N 10 void max_min(int *a,int m,int n,int *min1,int *min2,int *max1,int *max2); int main(void) int aN=2,3,4,5,34,7,9,6,43,21; int min1,min2; int max1,max2; max_min(a,0,N-1,&min1,&min2,&max1,&max2); printf(min1=%dnmin2=%dnmax1=%dnmax2=%dn,min1,min2,max1,max2); return 0; void max_min(int *a,int m,int n,int *min1,int *min2,int *max1,int *max2) int lmin1,lmin2,lmax1,lmax2; int rmin1,rmin2,rmax1,rmax2; int mid; if(m=n) *min1=*min2=*max1=*max2=am; else if(m=n-1) if(aman) *min1=am; *min2=an; *max1=an; *max2=am; else *min1=an; *min2=am; *max1=am; *max2=an; else mid=(m+n)/2; max_min(a,m,mid,&lmin1,&lmin2,&lmax1,&lmax2); max_min(a,mid+1,n,&rmin1,&rmin2,&rmax1,&rmax2); if(lmin1rmin1) if(lmin2rmin1) *min1=lmin1; *min2=lmin2; else *min1=lmin1; *min2=rmin1; else if(rmin2rmax1) if(lmax2rmax1) *max1=lmax1; *max2=lmax2; else *max1=lmax1; *max2=rmax1; else if(rmax2lmax1) *max1=rmax1; *max2=rmax2; else *max1=rmax1; *max2=lmax1; 10.#include int add(int *a,int flag,int right); int main(void) int a10=1,2,3,4,5,6,7,8,9,10; int sum=add(a,0,9); printf(%dn,sum); return 0; int add(int *a,int flag,int right) int mid; if(flag=right) return aflag; else if(flag=right-1) return aflag+aright; else mid=(flag+right)/2; return add(a,flag,mid)+add(a,mid+1,right); 11.#includeint 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;int sum=0;for(i=0;i5;i+)max=ai0;n=0;for(j=1;jmax)max=aij;n=j;sum+=max;printf(a%d%d=%dn,i,n,max);printf(%dn,sum);return 0;12./* * File: newmain.c* Author: nirnava* Created on 2010年4月22日, 下午5:21*/#include#include#define N 4void matrix_mul(int *mul1,int *mul2,int *mul3,int length);void matrix_add_sub(int * A,int * B,int * C,int m,char ch);void update_half_value(int * A,int * B,int 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,mul3,N);for(i=0;iN*N;i+)printf(%5d,mul3i);if(i+1)%N=0)printf(n);return 0;void matrix_add_sub(int * A,int * B,int * C,int m,char ch)int i;for(i=0;im*m;i+)if(ch=+)Ci=Ai+Bi;elseCi=Ai-Bi;void update_half_value(int * A,int * B,int m)int i,j;for(i=0;im/2;i+)for(j=0;jm/2;j+)Bi*m+j=Ai*m/2+j;void 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=Bi*m+j;void matrix_mul(int *A,int *B,int *C,int m)if(m=2)int 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+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,Im*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_value(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(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,I,m/2);matrix_add_sub(A1,A4,temp1,m/2,+);matrix_add_sub(B1,B4,temp2,m/2,+);matrix_mul(temp1,temp2,J,m/2);matrix_add_sub(E,I,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,-);matrix_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.#includeint main(void)int a67=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 b67,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=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;max=0;for(j=1;jmax)max=bij;flag=j;printf(%dn,max);temp=ciflag;printf(%5d,aitemp);for(j=i;j0;j-)temp=cjtemp;printf(%5d,aj-1temp);printf(n);return 0;14.#includeint 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 AB66;int temp6;int abc6;int 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;printf(max=%dn,max);printf(c=%dn,5-flag);max=max-C5-flag;for(i=0;i=flag;i+)if(ABflagi=max)printf(b=%dn,i);printf(a=%dn,flag-i);break;return 0;16.#include#define N 100int search(int *a,int left,int right);int sum_buf(int *a,int left,int 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);printf(%dn,s);return 0;int sum_buf(int *a,int left,int right)int i;int sum=0;for(i=left;i=right;i+)sum+=ai;return sum;int search(int *a,int left,int 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);elsereturn search(a,mid+1,right);17.#includeint job62=3,8,12,10,5,9,2,6,9.3,11,1;int x6,bestx6,f1=0,bestf,f27=0;void try(int i);void swap(int a,int b);int main(void)int i,j;bestf=32767;for(i=0;i6;i+)xi=i;try(0);for(i=0;i6;i+)printf(%d ,bestxi);printf(nbestf=%dn,bestf);return 0;void try(int 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+1bestf)swap(i,j);try(i+1);swap(i,j);f1=f1-jobxj0;void swap(int i,int j)int temp;temp=xi;xi=xj;xj=temp;18.#include#define N 5 /N个数字#define M 2 /M个加号char bufN;int aN;char bM+1N;int cM+1;int try(int t);void swap(int t1,int t2);int add();void output();int min=99999;int main()int i;for(i=0;iN;i+)scanf(%c,&bufi);a0=0;for(i=1;i=M;i+)ai=1;for(;i=N)sum=add();if(summin)min=sum;for(i=0;iM+1;i+)ci=atoi(bi);/*for(i=0;iN;i+)printf(%d,ai);printf(n);*/elsefor(j=t;jN;j+)/if(at!=aj)swap(t,j);try(t+1);swap(t,j);/else/try(t+1);void swap(int t1,int t2)int t;t=at1;at1=at2;at2=t;int add()int sum=0;int i=0;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=bufj;/printf(%d ,atoi(bi);/printf(%d %d %c n,i,h,bih);h+;elsebih=bufj;/printf(%d %d %c n,i,h,bih);/printf(%d ,atoi(bi);h+;/*for(i=0;iM+1;i+)for(j=0;jN;j+)printf(%c ,bij);printf(n);*/for(i=0;iM+1;i+)sum+=atoi(bi);return sum;void output()int i;for(i=0;iM+1;i+)printf(%d,atoi(bi);if(i!=M)