习题答案第四章算法设计与分析吕国英.docx
《习题答案第四章算法设计与分析吕国英.docx》由会员分享，可在线阅读，更多相关《习题答案第四章算法设计与分析吕国英.docx（21页珍藏版）》请在冰点文库上搜索。
习题答案第四章算法设计与分析吕国英
习题答案第四章-算法设计与分析-吕国英
Lt
D
算法设计与分析〔第二版〕
主编：
吕国英
习题答案
第四章
1.
#include
intmain（void）
{
intbuf[100];
intn;
inti,j,k;
scanf（"%d",&n）;
for（i=0;ibuf[i]=2;
for（i=0;i{
for（j=0;j{
buf[j]+=2;
}
}
for（j=0;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.
#include
intmain（void）
{
intn=2;
inti;
for（i=1;i<=9;i++）
{
n=（n+2）*2;
}
printf（"%d\n",n）;
return0;
}
3.
#include
intmain（void）
{
inta=54;
intn;
intm;
printf（"计算机先拿3张牌\n"）;
a=a-3;
while（a>=0）
{
printf（"还剩%d张牌\n",a）;
printf（"你拿几张？
请输入：
"）;
scanf（"%d",&n）;
if（n>4||n<1||n>a）
{
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.
#include
intd;
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.
#include
charchess[8][8];
intis_safe（introw,intcol）;
intqueen（introw,intcol,intn）;
intmain（void）
{
inti,j;
for（i=0;i<8;i++）
for（j=0;j<8;j++）
chess[i][j]='X';
queen（0,0,0）;
for（i=0;i<8;i++）
{
for（j=0;j<8;j++）
printf（"%c",chess[i][j]）;
printf（"\n"）;
}
return0;
}
intis_safe（introw,intcol）
{
inti,j;
for（i=0;i<8;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;
else
if（is_safe（row,col））
{
chess[row][col]='Q';
for（i=0;i<8;i++）
for（j=0;j<8;j++）
{
result+=queen（i,j,n+1）;
if（result>0）
break;
}
if（result>0）
return1;
else
{
chess[row][col]='X';
return0;
}
}
else
return0;
}
6.
#include
intmain（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.
#include
intmain（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.
#include
intmain（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.
#include
#defineN10
voidmax_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];
}
else
if（m==n-1）
{
if（a[m]{
*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（lmin1{
if（lmin2{
*min1=lmin1;
*min2=lmin2;
}
else
{
*min1=lmin1;
*min2=rmin1;
}
}
else
if（rmin2{
*min1=rmin1;
*min2=rmin2;
}
else
{
*min1=rmin1;
*min2=lmin1;
}
if（lmax1>rmax1）
{
if（lmax2>rmax1）
{
*max1=lmax1;
*max2=lmax2;
}
else
{
*max1=lmax1;
*max2=rmax1;
}
}
else
if（rmax2>lmax1）
{
*max1=rmax1;
*max2=rmax2;
}
else
{
*max1=rmax1;
*max2=lmax1;
}
}
}
10.
#include
intadd（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];
}
else
if（flag==right-1）
{
returna[flag]+a[right];
}
else
{
mid=（flag+right）/2;
returnadd（a,flag,mid）+add（a,mid+1,right）;
}
}
11.
#include
intmain（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;i<5;i++）
{
max=a[i][0];
n=0;
for（j=1;j<3;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
*
*Createdon2021年4月22日,下午5:
21
*/
#include
#include
#defineN4
voidmatrix_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;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;i{
if（ch=='+'）
C[i]=A[i]+B[i];
else
C[i]=A[i]-B[i];
}
}
voidupdate_half_value（int*A,int*B,intm）
{
inti,j;
for（i=0;i{
for（j=0;j{
B[i*m+j]=A[i*m/2+j];
}
}
}
voidget_half_value（int*A,int*B,intm）
{
inti,j;
for（i=0;i{
for（j=0;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[3]）*（B[0]+B[3]）;
C[0]=E+I+J-G;
C[1]=D+G;
C[2]=E+F;
C[3]=D+H+J-F;
return;
}
else
{
intA1[m*m/4],A2[m*m/4],A3[m*m/4],A4[m*m/4];
intB1[m*m/4],B2[m*m/4],B3[m*m/4],B4[m*m/4];
intC1[m*m/4],C2[m*m/4],C3[m*m/4],C4[m*m/4];
intD[m*m/4],E[m*m/4],F[m*m/4],G[m*m/4],H[m*m/4],I[m*m/4],J[m*m/4];
inttemp1[m*m/4],temp2[m*m/4];
get_half_value（A1,&A[0],m）;
get_half_value（A2,&A[m/2],m）;
get_half_value（A3,&A[m*m/2],m）;
get_half_value（A4,&A[m*m/2+m/2],m）;
get_half_value（B1,&B[0],m）;
get_half_value（B2,&B[m/2],m）;
get_half_value（B3,&B[m*m/2],m）;
get_half_value（B4,&B[m*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,&C[0],m）;
update_half_value（C2,&C[m/2],m）;
update_half_value（C3,&C[m*m/2],m）;
update_half_value（C4,&C[m*m/2+m/2],m）;
return;
}
}
13.
#include
intmain（void）
{
inta[6][7]={
{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}
};
intb[6][7],c[6][7];
inti,j,k;
intmax;
intflag;
inttemp;
for（i=0;i<6;i++）
for（j=0;j<7;j++）
{
b[i][j]=a[i][j];
c[i][j]=-1;
}
for（i=1;i<5;i++）
{
for（j=0;j<7;j++）
{
max=0;
for（k=j-2;k<=j+2;k++）
{
if（k<0）
continue;
else
if（k>6）
break;
else
{
if（b[i][j]+b[i-1][k]>max）
{
max=b[i][j]+b[i-1][k];
flag=k;
}
}
}
b[i][j]=max;
c[i][j]=flag;
}
}
for（j=1;j<=5;j++）
{
max=0;
for（k=j-2;k<=j+2;k++）
{
if（k<0）
continue;
else
if（k>6）
break;
else
{
if（b[i][j]+b[i-1][k]>max）
{
max=b[i][j]+b[i-1][k];
flag=k;
}
}
}
b[i][j]=max;
c[i][j]=flag;
}
max=0;
for（j=1;j<=5;j++）
{
if（b[i][j]>max）
{
max=b[i][j];
flag=j;
}
}
printf（"%d\n",max）;
temp=c[i][flag];
printf（"%5d",a[i][temp]）;
for（j=i;j>0;j--）
{
temp=c[j][temp];
printf（"%5d",a[j-1][temp]）;
}
printf（"\n"）;
return0;
}
14.
#include
intmain（void）
{
intA[6]={0,3,7,9,12,13};
intB[6]={0,5,10,11,11,11};
intC[6]={0,4,6,11,12,12};
intAB[6][6];
inttemp[6];
intabc[6];
intmax;
intflag;
inti,j,k;
for（i=0;i<=5;i++）
{
max=0;
for（j=0;j<=i;j++）
{
AB[i][j]=A[i-j]+B[j];
if（AB[i][j]>max）
max=AB[i][j];
}
temp[i]=max;
}
max=0;
for（i=0;i<=5;i++）
{
abc[i]=temp[i]+C[5-i];
if（abc[i]>max）
{
max=abc[i];
flag=i;
}
}
printf（"max=%d\n",max）;
printf（"c=%d\n",5-flag）;
max=max-C[5-flag];
for（i=0;i<=flag;i++）
{
if（AB[flag][i]==max）
{
printf（"b=%d\n",i）;
printf（"a=%d\n",flag-i）;
break;
}
}
return0;
}
16.
#include
#defineN100
intsearch（int*a,intleft,intright）;
intsum_buf（int*a,intleft,intright）;
intmain（void）
{
inta[N];
inti;
ints;
for（i=0;ia[i]=1;
a[24]=2;
s=search（a,0,N-1）;
printf（"%d\n",s）;
return0;
}
intsum_buf（int*a,intleft,intright）
{
inti;
intsum=0;
for（i=left;i<=right;i++）
sum+=a
升级会员 