算法设计与分析习题答案.doc

算法设计与分析习题答案（第二版）主编：吕国英习题答案习题答案第三章：1.#include #include 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=0;i-) for(j=i;j=0;j-) bufj+=2; for(k=0;k=10) bufk+1+=bufk/10; bufk%=10; for(i=n-1;i=0;i-) printf(%d,bufi); printf(n); return 0; 2.#include int main(int argc,char *argv) int buf66; int i,j; printf(任意输入6个数字:); for(i=0;i6;i+) scanf(%d,&buf0i); for(i=0;i5;i+) for(j=0;j5;j+) bufi+1j+1=bufij; bufi+10=bufij; for(i=0;i6;i+) for(j=0;j6;j+) printf(%d ,bufij); printf(n); return 0; 3.#include #define N 7 int main(int argc,char *argv) int bufNN; 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+) bufaj=count+; for(k=a+1;k=a;m-) bufbm=count+; for(n=b-1;na;n-) bufna=count+; a+; b-; for(i=0;iN;i+) for(j=0;jN;j+) printf(%5d,bufij); printf(n); return 0; 4.#include #define N 5 int main(int argc,char *argv) int bufNN; int i,j,k; int count=1; int n=0; for(i=0;i=0;j-,k+) bufjk=count+; n+; for(i=0;iN;i+) for(j=0;jN-i;j+) printf(%5d,bufij); printf(n); return 0; 5.#include #define N 5 int main(int argc,char *argv) int bufNN; int i,j; int a=0,b=N-1; int count=1; for(i=0;iN/2+N%2;i+) for(j=a;j=b;j+) bufaj=count; for(j=a+1;j=a;j-) bufbj=count; for(j=b-1;ja;j-) bufja=count; count+; a+; b-; for(i=0;iN;i+) for(j=0;jN;j+) printf(%5d,bufij); printf(n); return 0; 6.#include#includetypedef struct s_node s_list;typedef s_list *link;struct s_nodechar 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;icount;i+) if(bufi=()push(bufi,i); if(bufi=) flag=pop(); if(flag!=0) if(bufflag-1=()&(bufi+1=) bufflag=!; bufi=!; min=op(bufflag); for(j=flag+1;jop(bufj) min=op(bufj); if(icount-1) if(bufi+1=+)|(bufi+1=-) if(flag=0) bufi=!; bufflag=!; else if(op(bufflag-1)=op(bufi+1)&op(bufflag-1)=min) bufi=!; bufflag=!; else if(i=count-1) if(flag=0) bufi=!; bufflag=!; else if(op(bufflag-1)=min) bufi=!; bufflag=!; for(k=0;kcount;k+) if(bufk!=!)printf(%c,bufk); printf(n);int main(void)char buf255;int i;for(i=0;i255;i+) scanf(%c,&bufi); if(bufi=n)break; bufi=0;nirnava(buf,i);return 0;7.#include#includeint ack(int m,int n);int count=0;int main(int argc,char *argv)int m,n;scanf(%d%d,&m,&n);printf(%dn,ack(m,n);printf(%dn,count);return 0;int ack(int m,int n)count+;if(m=0) return n+1;else if(n=0) return ack(m-1,1); else return ack(m-1,ack(m,n-1);8.#includechar buf1024;int is_huiwen(int a,int count)if(a=count/2) return 1; else if(bufa=bufcount-a-1) return (is_huiwen(a-1,count)&1; else return 0; int main(void)int count;int i;for(i=0;i1024;i+) scanf(%c,&bufi); if(bufi=n)break; count=i;i-;printf(%d,is_huiwen(i,count);return 0;9.#includechar buf100;int pos(int a,int b)if(b-a=1) return 1;else if(b-a=0) return 1; else return 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#define MAX 1024int bufMAX;int main(void)int m,n;int i;scanf(%d%d,&m,&n);for(i=0;iMAX;i+) bufi=0;i=0;while(bufi%m=0) bufi%m=1; i+=n; for(i=0;im;i+) if(bufi=0)printf(%d ,i); return 0;11.#include 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+; else if(temp=0) temp1=i; while(temp1%10)=0) temp1=temp1/10; count+; printf(%d,count); return 0; 12.#includeint main(void)int count=0;int buf53;int i,n;for(i=1;i53;i+) bufi=1; for(n=2;n+) for(i=n;i=104) break; if(count=104)break; for(i=1;i53;i+) if(bufi=1)printf(%d ,i); printf(n);return 0;13.#includeint 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.#includeint main(void)int buf3;int i;int mul;int temp;for(i=10;i=31;i+) mul=i*i; temp=mul; buf0=temp%10; temp=temp/10; buf1=temp%10; temp=temp/10; buf2=temp; if(buf0=buf1)|(buf0=buf2)|(buf1=buf2) printf(%d2=%dn,i,mul); return 0;15.#includeint 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.#includeint 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 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(d84) d=d-84; printf(your number was %dn,d); return 0; 18.#includeint main(void)int buf10;int i,j;int mul;int temp1,temp2;int bool;for(i=5000;i=9999;i+) bool=0; for(j=0;j0) if(+buftemp1%10)1) bool=1; break; temp1/=10; if(bool=1)continue; mul=i*2; temp2=mul; while(temp20) if(+buftemp2%10)1) bool=1; break; temp2/=10; if(bool=1)continue; printf(2*%d=%dn,i,mul); return 0;19.#include #include int ppow(int a,int b) int mul=1; int i; for(i=0;ib;i+) mul=a*mul; return mul; int main(void) int t; char buf10; int i,j,k; int sum=0; for(i=0;i10;i+) scanf(%c,&bufi); if(bufi=n) break; bufi=0; for(j=0;j=0)&(bufj=A)&(bufj=0;j-) t=ppow(16,k); sum=sum+t*(int)bufj; k+; printf(%dn,sum); return 0; 20.#includeint main(void)int a;int b;int c;int i;int buf10;for(a=10;a=99;a+) for(i=0;i1)|(+bufa/10%101)continue; for(b=100;b=999;b+) for(i=0;i1)|(+bufb/10%101)|(+bufb/100%101) continue; c=a*b; if(c999) if(+bufc%101)|(+bufc/10%101)|(+bufc/100%101)|(+bufc/1000%101) continue; else printf(%d*%d=%dn,a,b,c); return 0;21.#include int main(void) int a; int b; int i; int t; int buf10; int bool; for(a=317;a1000;a+) bool=0; for(i=0;i1)|(+bufa/10%101)|(+bufa/100%101) continue; b=a*a; t=b; for(i=0;i1) bool=1; break; t=t/10; if(bool=1) continue; printf(%d2=%dn,a,b); return 0; 22.#includeint main(void)int buf100;int i;int n;int max;int temp;for(i=1;imax)max=temp; printf(max=%dn,max);return 0;23.#includevoid nirnava(int n)if(n0) printf(%d ,t%10); t=t/10; count+; printf(n);nirnava(n);printf(n%d位数n,count);24.#includeint main(void)int buf4=2,3,5,7;int i,j,k,temp,m;int bool;int mul;for(i=0;i4;i+) for(j=0;j4;j+) for(k=0;k4;k+)for(m=0;m4;m+) bool=0; mul=(bufi+bufj*10+bufk*100)*bufm; if(mul0) 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 = %dn,bufk,bufj,bufi,bufm,mul); return 0;25.#includeint main(void)int buf4=2,3,5,7;int i,j,k,m,n;int bool;int mul,mul1,mul2;int temp,temp1,temp2;for(i=0;i4;i+) for(j=0;j4;j+) for(k=0;k4;k+)for(m=0;m4;m+) for(n=0;n4;n+) bool=0; mul=(bufi+bufj*10+bufk*100)*(bufm+bufn*10); mul1=(bufi+bufj*10+bufk*100)*bufm; mul2=(mul-mul1)/10; if(mul10000)|(mul11000)|(mul20) if(temp%10=2)|(temp%10=3)|(temp%10=5)|(temp%10=7) else bool=1; break; temp/=10; if(bool=0) while(temp10) if(temp1%10=2)|(temp1%10=3)|(temp1%10=5)|(temp1%10=7) else bool=1; break; temp1/=10; if(bool=0) while(temp20) if(temp2%10=2)|(temp2%10=3)|(temp2%10=5)|(temp2%10=7) else bool=1; break; temp2/=10; if(bool=0) printf(第一行 : %d%d%dn第二行 : %d%dn第三行 : %dn第四行 : %dn第五行 : %dnnnnn,bufi,bufj,bufk,bufm,bufn,mul1,mul2,mul); return 0;26.#include/从a到b是不是循环节int is_xunhuan(int *buf,int a,int b)int i;if(a=b) for(i=1;i10;i+) if(bufa=bufa+i) else return 0; else for(i=a;i=b;i+) if(bufi=bufi+b-a+1) else return 0; return 1;int main(void)int buf1024;int yushu;int m,n;int i,j,k;scanf(%d%d,&m,&n);yushu=m;buf0=0;i=1;while(yushu!=0) yushu=yushu*10; bufi=yushu/n; yushu=yushu%n; i+; if(i=1024)break; if(i1024) printf(有限小数n); printf(%d.,buf0); for(j=1;ji;j+)printf(%d,bufj); printf(n); else printf(循环小数n); for(i=1;i100;i+)for(j=i;j1) for(k=1;ki;k+) printf(%d,bufk); printf(); for(k=i;k=j;k+) printf(%d,bufk); printf(); printf(n); return 0; return 0;27.#includeint main(void)int n;char eng1210=一月,二月,三月,四月,五月,六月,七月,八月,九月,十月,十一月,十二月;scanf(%d,&n);printf(%sn,engn-1);return 0;第四章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;else if(is_safe(row,col) chessrowcol=Q;for(i=0;i8;i+) for(j=0;j0) break; if(result0) return 1;else chessrowcol=X; return 0; else return 0;6.#includeint main(void)int i,j,k;for(i=1;i=33;i+) for(j=1;j=50;j+) k=100-