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

算法设计与分析（第二版）主编：吕国英习题答案第四章1.#includestdio.hintmain(void){intbuf[100];intn;inti,j,k;scanf(%d,&n);for(i=0;in;i++)buf[i]=2;for(i=0;in-1;i++){for(j=0;jn-i-1;j++){buf[j]+=2;}}for(j=0;jn;j++){if(buf[j]=10){buf[j+1]+=buf[j]/10;buf[j]=buf[j]%10;}}for(i=n-1;i=0;i--)printf(%d,buf[i]);printf(\n);return0;}2.#includestdio.hintmain(void){intn=2;inti;for(i=1;i=9;i++){n=(n+2)*2;}printf(%d\n,n);return0;}3.#includestdio.hintmain(void){inta=54;intn;intm;printf(计算机先拿3张牌\n);a=a-3;while(a=0){printf(还剩%d张牌\n,a);printf(你拿几张？请输入：);scanf(%d,&n);if(n4||n1||na){printf(错误！重新拿牌\n);continue;}a=a-n;printf(还剩%d张牌\n,a);if(a==0)break;m=5-n;printf(计算机拿%d\n,m);a=a-m;}return0;}4.#includestdio.hintd;inta1,a2;intfun(intn);intmain(void){intn;printf(n=?,d=?,a1=?,a2=?);scanf(%d%d%d%d\n,&n,&d,&a1,&a2);printf(%d\n,fun(n));return0;}intfun(intn){if(n==1)returna1;if(n==2)returna2;returnfun(n-2)-(fun(n-1)-d)*2;}5.#includestdio.hcharchess[8][8];intis_safe(introw,intcol);intqueen(introw,intcol,intn);intmain(void){inti,j;for(i=0;i8;i++)for(j=0;j8;j++)chess[i][j]='X';queen(0,0,0);for(i=0;i8;i++){for(j=0;j8;j++)printf(%c,chess[i][j]);printf(\n);}return0;}intis_safe(introw,intcol){inti,j;for(i=0;i8;i++){if(chess[row][i]=='Q')return0;if(chess[i][col]=='Q')return0;}i=row;j=col;while(i!=-1&&j!=-1){if(chess[i--][j--]=='Q')return0;}i=row;j=col;while(i!=-1&&j!=8){if(chess[i--][j++]=='Q')return0;}i=row;j=col;while(i!=8&&j!=-1){if(chess[i++][j--]=='Q')return0;}i=row;j=col;while(i!=8&&j!=8){if(chess[i++][j++]=='Q')return0;}return1;}intqueen(introw,intcol,intn){inti,j;intresult=0;if(n==8)return1;elseif(is_safe(row,col)){chess[row][col]='Q';for(i=0;i8;i++)for(j=0;j8;j++){result+=queen(i,j,n+1);if(result0)break;}if(result0)return1;else{chess[row][col]='X';return0;}}elsereturn0;}6.#includestdio.hintmain(void){inti,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(大马%d\n中马%d\n小马%d\n\n\n,i,j,k);}}return0;}7.#includestdio.hintmain(void){inti;for(i=1;i=10000;i++){if(i%2==1&&i%3==2&&i%5==4&&i%6==5&&i%7==0)printf(%d\n,i);}return0;}8.#includestdio.hintmain(void){inti;intsum;inta1,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(%d\n,i);}}}}return0;}9.#includestdio.h#defineN10voidmax_min(int*a,intm,intn,int*min1,int*min2,int*max1,int*max2);intmain(void){inta[N]={2,3,4,5,34,7,9,6,43,21};intmin1,min2;intmax1,max2;max_min(a,0,N-1,&min1,&min2,&max1,&max2);printf(min1=%d\nmin2=%d\nmax1=%d\nmax2=%d\n,min1,min2,max1,max2);return0;}voidmax_min(int*a,intm,intn,int*min1,int*min2,int*max1,int*max2){intlmin1,lmin2,lmax1,lmax2;intrmin1,rmin2,rmax1,rmax2;intmid;if(m==n){*min1=*min2=*max1=*max2=a[m];}elseif(m==n-1){if(a[m]a[n]){*min1=a[m];*min2=a[n];*max1=a[n];*max2=a[m];}else{*min1=a[n];*min2=a[m];*max1=a[m];*max2=a[n];}}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;}}elseif(rmin2lmin1){*min1=rmin1;*min2=rmin2;}else{*min1=rmin1;*min2=lmin1;}if(lmax1rmax1){if(lmax2rmax1){*max1=lmax1;*max2=lmax2;}else{*max1=lmax1;*max2=rmax1;}}elseif(rmax2lmax1){*max1=rmax1;*max2=rmax2;}else{*max1=rmax1;*max2=lmax1;}}}10.#includestdio.hintadd(int*a,intflag,intright);intmain(void){inta[10]={1,2,3,4,5,6,7,8,9,10};intsum=add(a,0,9);printf(%d\n,sum);return0;}intadd(int*a,intflag,intright){intmid;if(flag==right){returna[flag];}elseif(flag==right-1){returna[flag]+a[right];}else{mid=(flag+right)/2;returnadd(a,flag,mid)+add(a,mid+1,right);}}11.#includestdio.hintmain(void){inta[5][3]={{-50,17,-42},{-47,-19,-3},{36,-34,-43},{-30,-43,34},{-23,-8,-45}};inti,j;intmax,n;intsum=0;for(i=0;i5;i++){max=a[i][0];n=0;for(j=1;j3;j++){if(a[i][j]max){max=a[i][j];n=j;}}sum+=max;printf(a[%d][%d]=%d\n,i,n,max);}printf(%d\n,sum);return0;}12./**File:newmain.c*Author:nirnava**Createdon2010年4月22日,下午5:21*/#includestdio.h#includestdlib.h#defineN4voidmatrix_mul(int*mul1,int*mul2,int*mul3,intlength);voidmatrix_add_sub(int*A,int*B,int*C,intm,charch);voidupdate_half_value(int*A,int*B,intm);voidget_half_value(int*A,int*B,intm);intmain(void){inti,j;intmul1[N*N]={1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6};intmul2[N*N]={7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2};intmul3[N*N];matrix_mul(mul1,mul2,mul3,N);for(i=0;iN*N;i++){printf(%5d,mul3[i]);if((i+1)%N==0)printf(\n);}return0;}voidmatrix_add_sub(int*A,int*B,int*C,intm,charch){inti;for(i=0;im*m;i++){if(ch=='+')C[i]=A[i]+B[i];elseC[i]=A[i]-B[i];}}voidupdate_half_value(int*A,int*B,intm){inti,j;for(i=0;im/2;i++){for(j=0;jm/2;j++){B[i*m+j]=A[i*m/2+j];}}}voidget_half_value(int*A,int*B,intm){inti,j;for(i=0;im/2;i++){for(j=0;jm/2;j++){A[i*m/2+j]=B[i*m+j];}}}voidmatrix_mul(int*A,int*B,int*C,intm){if(m==2){intD,E,F,G,H,I,J;D=A[0]*(B[1]-B[3]);E=A[3]*(B[2]-B[0]);F=(A[2]+A[3])*B[0];G=(A[0]+A[1])*B[3];H=(A[2]-A[0])*(B[0]+B[1]);I=(A[1]-A[3])*(B[2]+B[3]);J=(A[0]+A[