算法设计和分析（第二版）习题答案（第三章）2010年06月15日星期二下午 03:51算法设计和分析（第二版）主编：吕国英习题答案第三章：1.#include<stdlib.h>#include<stdio.h>int main(int argc,char **argv){int n;int i,j,k;int *buf;printf("请输入n的数值:");scanf("%d",&n);buf=(int *)malloc(n*sizeof(int)); for(i=0;i<n;i++){buf[i]=2;}for(i=n-2;i>=0;i--)for(j=i;j>=0;j--){buf[j]+=2;}}for(k=0;k<=n-2;k++){if(buf[k]>=10){buf[k+1]+=buf[k]/10;buf[k]%=10;}}for(i=n-1;i>=0;i--)printf("%d",buf[i]); printf("\n");return 0;}2.#include<stdio.h>int main(int argc,char **argv)int buf[6][6];int i,j;printf("任意输入6个数字:");for(i=0;i<6;i++)scanf("%d",&buf[0][i]);for(i=0;i<5;i++){for(j=0;j<5;j++){buf[i+1][j+1]=buf[i][j];}buf[i+1][0]=buf[i][j];}for(i=0;i<6;i++){for(j=0;j<6;j++)printf("%d ",buf[i][j]);printf("\n");}return 0;}#include<stdio.h>#define N 7int main(int argc,char **argv) {int buf[N][N];int i,j,k,m,n;int a=0,b=N-1;int count=1;for(i=0;i<(N/2)+(N%2);i++) {for(j=a;j<=b;j++){buf[a][j]=count++;}for(k=a+1;k<=b;k++){buf[k][b]=count++;}for(m=b-1;m>=a;m--){buf[b][m]=count++;}for(n=b-1;n>a;n--){buf[n][a]=count++;}a++;b--;}for(i=0;i<N;i++){for(j=0;j<N;j++)printf("%5d",buf[i][j]);printf("\n");}return 0;}4.#include<stdio.h>#define N 5int main(int argc,char **argv) {int buf[N][N];int i,j,k;int count=1;int n=0;for(i=0;i<N;i++){for(k=0,j=n;j>=0;j--,k++) buf[j][k]=count++;n++;}for(i=0;i<N;i++){for(j=0;j<N-i;j++)printf("%5d",buf[i][j]);printf("\n");}return 0;}5.#include<stdio.h>#define N 5int main(int argc,char **argv) {int buf[N][N];int i,j;int a=0,b=N-1;int count=1;for(i=0;i<N/2+N%2;i++){for(j=a;j<=b;j++)buf[a][j]=count;for(j=a+1;j<=b;j++)buf[j][b]=count;for(j=b-1;j>=a;j--)buf[b][j]=count;for(j=b-1;j>a;j--)buf[j][a]=count;count++;a++;b--;}for(i=0;i<N;i++){for(j=0;j<N;j++)printf("%5d",buf[i][j]);printf("\n");}return 0;}6.#include<stdio.h>#include<stdlib.h>typedef struct s_node s_list;typedef s_list *link;struct s_node{char ch;int flag;link next;};link top;void push(char ch,int flag){link newnode;newnode=(link)malloc(sizeof(s_list)); newnode->ch=ch;newnode->flag=flag;newnode->next=NULL;if(top==NULL){top=newnode;}else{newnode->next=top;top=newnode;}}int pop(){int flag;link stack;if(top!=NULL){stack=top;top=top->next;flag=stack->flag;free(stack);}return flag;}int op(char ch){switch(ch){case '+':return 1;break;case '-':return 2;break;case '*':return 3;break;case '/':return 4;break;default:return 5;}}void nirnava(char *buf,int count)//count个数，buf数组{int bool=1;int min;int j;int i;int k;int flag;for(i=0;i<count;i++){if(buf[i]=='(')push(buf[i],i);if(buf[i]==')'){flag=pop();if(flag!=0){if((buf[flag-1]=='(')&&(buf[i+1]==')')) {buf[flag]='!';buf[i]='!';}min=op(buf[flag]);for(j=flag+1;j<i;j++) {if(buf[j]=='(') {push(buf[j],j);bool=0;continue;}elseif(buf[j]==')'){pop();bool=1;continue;}if(bool==1){if(min>op(buf[j]))min=op(buf[j]); }if(i<count-1){if((buf[i+1]=='+')||(buf[i+1]=='-')) {if(flag==0){buf[i]='!';buf[flag]='!';}elseif(op(buf[flag-1])<=min){buf[i]='!';buf[flag]='!';}}elseif((buf[i+1]=='*')||(buf[i+1]=='/')){if(flag==0){buf[i]='!';buf[flag]='!';}elseif((min>=op(buf[i+1])&&op(buf[flag-1])<=min)) {buf[i]='!';buf[flag]='!';}}}elseif(i==count-1){if(flag==0){buf[i]='!';buf[flag]='!';}elseif(op(buf[flag-1])<=min){buf[i]='!';buf[flag]='!';}}}}for(k=0;k<count;k++){if(buf[k]!='!') printf("%c",buf[k]);}printf("\n");}int main(void){char buf[255];int i;for(i=0;i<255;i++){scanf("%c",&buf[i]);if(buf[i]=='\n') break;}buf[i]='\0';nirnava(buf,i);return 0;}7.#include<stdio.h>#include<stdlib.h>int ack(int m,int n);int count=0;int main(int argc,char **argv) {int m,n;scanf("%d%d",&m,&n);printf("%d\n",ack(m,n));printf("%d\n",count);return 0;}int ack(int m,int n){count++;if(m==0)return n+1;elseif(n==0)return ack(m-1,1);elsereturn ack(m-1,ack(m,n-1));}8.#include<stdio.h>char buf[1024];int is_huiwen(int a,int count){if(a==count/2){return 1;}elseif(buf[a]==buf[count-a-1])return (is_huiwen(a-1,count))&&1;else{return 0;}}int main(void){int count;int i;for(i=0;i<1024;i++){scanf("%c",&buf[i]);if(buf[i]=='\n') break;}count=i;i--;printf("%d",is_huiwen(i,count)); return 0;}9.#include<stdio.h>char buf[100];int pos(int a,int b){if(b-a==1)return 1;elseif(b-a==0)return 1;elsereturn pos(a,b-1)+pos(a,b-2); }int main(void){int a,b;scanf("%d%d",&a,&b);printf("%d",pos(a,b));return 0;}10.#include<stdio.h>#define MAX 1024int buf[MAX];int main(void){int m,n;int i;scanf("%d%d",&m,&n);for(i=0;i<MAX;i++)buf[i]=0;i=0;while(buf[i%m]==0){buf[i%m]=1;i+=n;}for(i=0;i<m;i++){if(buf[i]==0) printf("%d ",i);}return 0;}11.#include<stdio.h>int main(void){int temp,temp1;int count=0;int n;int i;scanf("%d",&n);for(i=1;i<=n;i++){temp=i%10;if(temp==5)count++;elseif(temp==0){temp1=i;while((temp1%10)==0){temp1=temp1/10;count++;}}}printf("%d",count);return 0;}12.#include<stdio.h>int main(void){int count=0;int buf[53];int i,n;for(i=1;i<53;i++){buf[i]=1;}for(n=2;;n++){for(i=n;i<53;i+=n) {buf[i]=1-buf[i];count++;if(count>=104)break;}if(count>=104)}for(i=1;i<53;i++){if(buf[i]==1)printf("%d ",i);}printf("\n");return 0;}13.#include<stdio.h>int main(void){int a,b,c,d,e;for(a=1;a<=5;a++)for(b=1;b<=5;b++)if(a!=b)for(c=1;c<=5;c++)if(c!=a&&c!=b)for(d=1;d<=5;d++)if(d!=a&&d!=b&&d!=c)e=15-a-b-c-d;if(e!=a&&e!=b&&e!=c&&e!=d)if(((b==3)+(c==5)==1)&&((d==2)+(e==4)==1)&&((b==1) +(e==4)==1)&&((c==1)+(b==2)==1)&&((d==2)+(a==3)==1))printf("a=%d,b=%d,c=%d,d=%d,e=%d",a,b,c,d,e);}return 0;}14.#include<stdio.h>int main(void){int buf[3];int i;int mul;int temp;for(i=10;i<=31;i++){mul=i*i;temp=mul;buf[0]=temp%10;temp=temp/10;buf[1]=temp%10;temp=temp/10;buf[2]=temp;if((buf[0]==buf[1])||(buf[0]==buf[2])||(buf[1]==bu f[2])){printf("%d^2=%d\n",i,mul);}}return 0;}15.#include<stdio.h>int main(void){int a,b,c;for(a=1;a<=3;a++)for(b=1;b<=3;b++)if(a!=b){c=6-a-b;if(c!=a&&c!=b)if((a!=1)&&((c!=1)&&(c!=3))==1)printf("a=%d,b=%d,c=%d",a,b,c); }return 0;}16.#include<stdio.h>int main(void){int k;int n;scanf("%d",&n);k=(n%4==0)+(n%7==0)*2+(n%9==0)*4;switch(k){case 7:printf("all");break;case 6:printf("7 and 9");break;case 5:printf("4 and 9");break;case 4:printf("9");break;case 3:printf("4 and 7");break;case 2:printf("7");break;case 1:printf("4");break;case 0:printf("none");break;}return 0;}17.#include<stdio.h>int main(void){int a,b,c,d;printf("please think of a number between 1 and 100.\n"); printf("your number divided by 3 has a remainder of "); scanf("%d",&a);printf("your number divided by 4 has a remainder of "); scanf("%d",&b);printf("your number divided by 7 has a remainder of "); scanf("%d",&c);printf("let me think a moment...\n");d=36*c+28*a+21*b;while(d>84)d=d-84;printf("your number was %d\n",d);return 0;}18.#include<stdio.h>int main(void){int buf[10];int i,j;int mul;int temp1,temp2;int bool;for(i=5000;i<=9999;i++){bool=0;for(j=0;j<10;j++) buf[j]=0;temp1=i;while(temp1>0) {if((++buf[temp1%10])>1){bool=1;break;}temp1/=10;}if(bool==1) continue;mul=i*2;temp2=mul;while(temp2>0){if((++buf[temp2%10])>1){bool=1;break;}temp2/=10;}if(bool==1)continue;printf("2*%d=%d\n",i,mul);}return 0;}19.#include<stdio.h>#include<stdlib.h>int ppow(int a,int b){int mul=1;int i;for(i=0;i<b;i++){mul=a*mul;}return mul;}int main(void){int t;char buf[10];int i,j,k;int sum=0;for(i=0;i<10;i++){scanf("%c",&buf[i]);if(buf[i]=='\n') break;}buf[i]='\0';for(j=0;j<i;j++){if((buf[j]>='0')&&(buf[j]<='9')) buf[j]=buf[j]-48;elseif((buf[j]>='A')&&(buf[j]<='F'))buf[j]=buf[j]-55;elseexit(1);}k=0;for(j=i-1;j>=0;j--){t=ppow(16,k);sum=sum+t*(int)buf[j];k++;}printf("%d\n",sum);return 0;}20.#include<stdio.h>int main(void){int a;int b;int c;int i;int buf[10];for(a=10;a<=99;a++){for(i=0;i<10;i++)buf[i]=0;if((++buf[a%10]>1)||(++buf[a/10%10]>1)) continue;for(b=100;b<=999;b++){for(i=0;i<10;i++){if((i!=a%10)&&i!=a/10%10)buf[i]=0;}if((++buf[b%10]>1)||(++buf[b/10%10]>1)||(++buf[b/100%10] >1))continue;c=a*b;if(c<10000&&c>999){if((++buf[c%10]>1)||(++buf[c/10%10]>1)||(++buf[c /100%10]>1)||(++buf[c/1000%10]>1))continue;elseprintf("%d*%d=%d\n",a,b,c);}}}return 0;}21.#include<stdio.h>int main(void){int a;int b;int i;int t;int buf[10];int bool;for(a=317;a<1000;a++){bool=0;for(i=0;i<10;i++)buf[i]=0;if((++buf[a%10]>1)||(++buf[a/10%10]>1)||(++buf[a/1 00%10]>1))continue;b=a*a;t=b;for(i=0;i<6;i++){if(++buf[t%10]>1){bool=1;break;}t=t/10;}if(bool==1)continue;printf("%d^2=%d\n",a,b);}return 0;}22.#include<stdio.h>int main(void){int buf[100];int i;int n;int max;int temp;for(i=1;i<100;i++){scanf("%d",&buf[i]);if(buf[i]==0)break;}n=i;max=buf[1]+buf[2]+buf[3]+buf[4];for(i=2;i%10!=1;i++){temp=buf[i%10]+buf[(i+1)%10]+buf[(i+2)%10]+buf[(i+ 3)%10];if(temp>max)max=temp;}printf("max=%d\n",max);return 0;}23.#include<stdio.h>void nirnava(int n){if(n<10)printf("%d ",n);else{nirnava(n/10);printf("%d ",n%10);}}int main(void){int count=0;int n;int i;int t;scanf("%d",&n);t=n;while(t>0){printf("%d ",t%10);t=t/10;count++;}printf("\n");nirnava(n);printf("\n%d位数\n",count);}24.#include<stdio.h>int main(void){int buf[4]={2,3,5,7};int i,j,k,temp,m;int bool;int mul;for(i=0;i<4;i++)for(j=0;j<4;j++)for(k=0;k<4;k++)for(m=0;m<4;m++){bool=0;mul=(buf[i]+buf[j]*10+buf[k]*100)*buf[m];if(mul<1000)continue;temp=mul;while(temp>0){if((temp%10==2)||(temp%10==3)||(temp%10==5)||(temp%10==7 )){}else{bool=1;break;}temp/=10;}if(bool==0){printf("%d%d%d * %d= %d\n",buf[k],buf[j],buf[i],buf[m],mul);}}return 0;}25.#include<stdio.h>int main(void){int buf[4]={2,3,5,7};int i,j,k,m,n;int bool;int mul,mul1,mul2;int temp,temp1,temp2;for(i=0;i<4;i++)for(j=0;j<4;j++)for(k=0;k<4;k++)for(m=0;m<4;m++)for(n=0;n<4;n++){bool=0;mul=(buf[i]+buf[j]*10+buf[k]*100)*(buf[m]+buf[n] *10);mul1=(buf[i]+buf[j]*10+buf[k]*100)*buf[m];mul2=(mul-mul1)/10;if((mul<10000)||(mul1<1000)||(mul2<1000)) continue;temp=mul;temp1=mul1;temp2=mul2;while(temp>0){if((temp%10==2)||(temp%10==3)||(temp%10==5)||(temp%10= =7)){}else{bool=1;break;}temp/=10;}if(bool==0){while(temp1>0){if((temp1%10==2)||(temp1%10==3)||(temp1%10==5) ||(temp1%10==7)){}else{bool=1;break;}temp1/=10;}}if(bool==0)while(temp2>0){if((temp2%10==2)||(temp2%10==3)||(temp2%10==5)||(t emp2%10==7)){}else{bool=1;break;}temp2/=10;}if(bool==0){printf("第一行 : %d%d%d\n第二行 : %d%d\n第三行 : %d\n 第四行 : %d\n第五行 : %d\n\n\n\n\n",buf[i],buf[j],buf[k],buf[m],buf[n],mul1,mu l2,mul);}}return 0;}26.#include<stdio.h>//从a到b是不是循环节int is_xunhuan(int *buf,int a,int b) {int i;if(a==b){for(i=1;i<10;i++){if(buf[a]==buf[a+i]){}elsereturn 0;}}elsefor(i=a;i<=b;i++){if(buf[i]==buf[i+b-a+1]){}else{return 0;}return 1;}int main(void){int buf[1024];int yushu;int m,n;int i,j,k;scanf("%d%d",&m,&n); yushu=m;buf[0]=0;i=1;while(yushu!=0){yushu=yushu*10;buf[i]=yushu/n;yushu=yushu%n;i++;if(i==1024) break;if(i<1024){printf("有限小数\n");printf("%d.",buf[0]);for(j=1;j<i;j++)printf("%d",buf[j]);printf("\n");}else{printf("循环小数\n");for(i=1;i<100;i++)for(j=i;j<200;j++){if(is_xunhuan(buf,i,j)){printf("%d.",buf[0]);if(i>1){for(k=1;k<i;k++)printf("%d",buf[k]);printf("(");for(k=i;k<=j;k++)printf("%d",buf[k]);printf(")");printf("\n");return 0;}}}return 0;}27.#include<stdio.h>int main(void){int n;char eng[12][10]={"一月","二月","三月","四月","五月","六月","七月","八月","九月","十月","十一月","十二月"};scanf("%d",&n);printf("%s\n",eng[n-1]);return 0;}算法设计和分析（第二版）主编：吕国英习题答案第四章1.#include<stdio.h>int main(void){int buf[100];int n;int i,j,k;scanf("%d",&n);for(i=0;i<n;i++)buf[i]=2;for(i=0;i<n-1;i++){for(j=0;j<n-i-1;j++) {buf[j]+=2;}}for(j=0;j<n;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");return 0;}2.#include<stdio.h>int main(void){int n=2;int i;for(i=1;i<=9;i++){n=(n+2)*2;}printf("%d\n",n);return 0;}3.#include<stdio.h>int 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(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;}return 0;}4.#include<stdio.h>int d;int a1,a2;int fun(int n);int main(void){int n;printf("n=?,d=?,a1=?,a2=?");scanf("%d%d%d%d\n",&n,&d,&a1,&a2); printf("%d\n",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.#include<stdio.h>char chess[8][8];int is_safe(int row,int col);int queen(int row,int col,int n); int main(void){int i,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");}return 0;}int is_safe(int row,int col){int i,j;for(i=0;i<8;i++){if(chess[row][i]=='Q') return 0;。
