C程序设计习题解答.doc

C+程序设计习题解答（王挺）杂项1背包问题1趣味题1打印万年历2期末考试题3求解123456789=1004Chapter 44P103T04104P103T04114P103T04125P103T04135输出不大于的Fibonacci数列5Stein算法求最大公约数-移位法5P102 T04156P102 T04166P102 T04176P102 T04197P102 T04207P102 T04217Chapter 57p136 T5.57p136 T5.68p136 T5.68p136 T5.108p136 T5.118p137 T5.149p137 T5.169p137 T5.199Chapter 69求组合算法9P159 T6.310P159 T6.410P159 T6.410p159 T6.1111p159 T6.1211p159 T6.1811p159 T6.2012Chapter 712p195T70612p195T70712p195T70812p195T70913P195T71014P195T71114P196T71314Chapter 815p222T80315p222 T08030415p222T8517p222 T8060917附加18Chapter 918P241 T9.118P241 T9.219P241 T9.320P241 T9.521补充22Chapter 1123p288 T11.223P289 T11.923/使用结构实现栈24/利用类实现栈数据结构25Chapter 1226P305 T120426p305 T120527P306 T120627P306 T120729P306 T120829Chapter 1330P334 T13附加题30P334 T130331P334 T130432P335 T130533P335 T130634p335 T130734p336 T130835P336 T130936向量矩阵综合应用37Chapter 1440P373 T140540Chapter 1642P422 T160242P422 T160342P423 T160543P422 T1605-243Chapter 1744P436 T170644P436 T170745P436 T170945P436 T171045II杂项/*背包问题背包问题的求解，求解除所有的可能解法，非递归*/#include#include using namespace std;typedef int DataElem;class Stackprivate:int size;int top;DataElem * elem; public:Stack(int size);void Push(DataElem e);void Pop(DataElem &e);bool Empty();int TopPtr();int& operator(int i)assert(isize=size;top=-1;void Stack:Pop(DataElem &e)assert(top!=-1);e=elemtop-;void Stack:Push(DataElem e)assert(top!=size-1);elem+top=e;bool Stack:Empty()return top=-1;void print(Stack & s,DataElem* w)for(int i=0;i=s.TopPtr();i+)coutwsi;cout0 & k=0)s.Push(k);T-=wk;k+;if(T=0)print(s,w);s.Pop(k);T+=wk;k+;while(!s.Empty()|k!=n);void main()DataElem w=1,2,3,4,5,6,7,8,9,10;knapsack(w,10/*背包大小,必须保证此值不小于数组w的元素中的最大值*/,sizeof(w)/sizeof(DataElem);/*趣味题计算N！，要求打印出每一位*/#include #include #include using namespace std;typedef char DataElem;/定义双向链表节点数据类型typedef struct _tagNodestruct _tagNode * pre;DataElem data;struct _tagNode *next;NODE,*PNODE;void main()PNODE head,tail,cur;int n;/calculate n!coutn;head=new NODE;head-data=1;head-pre=head-next=0;tail=head;int prd,carry;struct _timeb64 starttime,endtime;_ftime64(&starttime);for(int i=1;idata*i+carry;cur-data=prd%10;/末位carry=prd/10;/进位cur=cur-pre;while(carry)/链表上的所有节点和乘数相乘完毕后还有进位cur=new NODE;cur-data=carry%10;cur-next=head;cur-pre=0;head-pre=cur;head=cur;carry/=10;while(head)coutdata);cur=head;head=head-next;delete cur;coutendltime escape :;_ftime64(&endtime);cout(endtime.time*1000+litm)-(starttime.time*1000+litm)/1000.0 secondendl;cin.get();cin.get();/*打印万年历*/#include#includeusing namespace std;void main()int mm13=0,31,28,31,30,31,30,31,31,30,31,30,31;char *monthname=January,February,March,April,May,June,July,August,September,October,November,December;int y,w,i,j;couty;if(!(y%400)|!(y%4)& y%100)mm2=29;y-;w=y+y/4-y/100+y/400+1;w%=7;y+;for(i=1;i13;i+)/*switch (i/3)case 1:coutntti spring.n;break;case 2:coutntti summer.n;break;case 3:coutntti autumn.n;break;default:coutntti winter.n;*/coutendl monthnamei-1endl;cout SUN MON TUE WED THU FRI SATn;for(j=0;jw;j+)cout ;for(j=1;j=mmi;j+)coutsetw(5)j;w+;if(w%=7)=0)coutendl;/*期末考试题*/#include using namespace std;class Aprivate:int age;char *name;public:A();A(A& a);A(char *str,int n);A();void outputA();A:A(A&a)age=a.age;name=new charstrlen()+1;strcpy(name,);A:A()coutDistructor nameendl;delete name;A:A(char *str,int n)age=n;name=new charstrlen(str)+1;strcpy(name,str);A:A()age=0;name=NULL;void A:outputA()coutnameageendl;void main()A a(zhangsan,15);A b(lisi,16);A *pa=new A(wangwu,17);delete pa;union integerchar ch;short s;int i;long l;void main()integer comb;comb.ch=a;comb.l=0x41424344coutcomb.ch;#include using namespace std;enum weekdaymon=1,tue,wed,thu,fri,sta,sun=0;char * strweek=sun,mon,tue,wed,thu,fri,sta;void main()coutwed;coutstrweekwed;#include using namespace std;void main()char *suit4 = Hearts,Diamonds, Clubs, Spades ;coutsuit33;#include using namespace std;void main()int a3=0,*pa=a;char *pc;short *ps=(short *)pa;pc=(char *)pa;for(int i=0;i12;i+)*(pc+i)=1;coutps5;/*求解123456789=100，其中中只能填写+或-*/#include #include using namespace std;void main()int a7=1,23,4,56,7,8,9;int sign6;int i;int sum;for(i=61;i64;i+)sum=a0;for(int j=0;j6;j+)signj=(i&(1j)=0?-1:1;sum+=aj+1*signj;if(sum=100)couta0;for(int j=0;j6;j+)cout(signj=1)?+:-)aj+1;cout=100y，则输出x-y，否则，输出y-x设计一个程序，输出x与y的差的绝对值，不能使用abs函数*/#include using namespace std;void main() double x,y; cinxy; if(xy) coutx-y; else couty-x;/*P103T0411输入一个不多于5位的正整数，要求，/（）求出它是几位数；/(2)分别打印出每一位数字/（）按逆序打印出每一位数字*/#include #include /required by log10()using namespace std;void main() int a,b,k; cina; /判断是几位的最简洁算法 /cout99999 | a0) coutyour Enter is too big endl; exit(0); else if(a/10000!=0) cout5endl; else if(a/1000!=0) cout4endl; else if(a/100!=0) cout3endl; else if(a/10!=0) cout2endl; else cout1endl; /顺序输出每一位 b=a; k=10000; while(b) if(b/k!=0) coutb/kt; b=b-b/k*k; k/=10; /按逆序输出每一位 while(a) couta%10t; a/=10; /*P103T0412编写一个程序，输入个数，确定并打印其中的最大值*/#include using namespace std;void main() int a,max,n; n=10; cinmax; n-; while(n0) cina; if(maxa) max=a; n-; coutmaxendl;/*P103T0413读取个float类型的非值，确定其是否能构成一个三角形*/#include #include #include using namespace std;#define EPSLON 1e-10void main() float a,b,c; cinabc; assert(fabs(a)EPSLON); assert(b!=0); assert(c!=0); if(a+bc & a+cb & b+ca) coutYesendl; else coutNo;/*输出不大于的Fibonacci数列*/#include using namespace std;void main() int f1=1; int f2=1,f3; coutf1tf2100) break; coutf3t; f1=f2; f2=f3; /*Stein算法求最大公约数-移位法首先引进一个符号：g_c_d是greatest common divisor（最大公约数）的缩写，g_c_d( x,y ) 表示x和y的最大公约数。然后有一个事实需要了解：一个奇数的所有约数都是奇数。这个很容易，下面我们要用到。来研究一下最大公约数的性质，我们发现有g_c_d( k*x,k*y ) = k*g_c_d( x,y ) 这么一个非常好的性质（证明我就省去了）。说他好是因为他非常符合我们化小的思想。我们试取k=2 ，则有g_c_d( 2x,2y ) = 2 * g_c_d( x,y )。这使我们很快联想到将两个偶数化小的方法。那么一奇一个偶以及两个奇数的情况我们如何化小呢？先来看看一奇一偶的情况：设有x和y两个数，其中y为奇数。因为y的所有约数都是奇数，所以a = g_c_d( 2x,y ) 是奇数。根据x是个偶数不难联想到，a应该是x的约数。我们来证明一下：(2x)%a=0，设x=n*a，因为a是奇数，x是偶数，则必有n是偶数。又因为x=(n/2)*a，所以x%a=0，即a是x的约数。因为a也是y的约数，所以a是x和y的公约数，有g_c_d( 2x,y ) = g_c_d( x,y )。因为g_c_d( x,y )明显是x和y的公约数，又有g_c_d( x,y ) y，我们注意到x+y和x-y是两个偶数，则有g_c_d( x+y,x-y ) = 2 * g_c_d( (x+y)/2,(x-y)/2 )，那么g_c_d( x,y ) 与g_c_d( x+y,x-y ) 以及g_c_d( (x+y)/2,(x-y)/2 ) 之间是不是有某种联系呢？为了方便我设m=(x+y)/2 ，n=(x-y)/2 ，容易发现m+n=x ，m-n=y 。设a = g_c_d( m,n )，则m%a=0,n%a=0 ，所以(m+n)%a=0，(m-n)%a=0 ，即x%a=0 ，y%a=0 ，所以a是x和y的公约数，有g_c_d( m,n )= g_c_d(x,y)。再设b = g_c_d( x,y )肯定为奇数，则x%b=0,y%b=0 ，所以(x+y)%b=0 ，(x-y)%b=0 ，又因为x+y和x-y都是偶数，跟前面一奇一偶时证明a是x的约数的方法相同，有(x+y)/2)%b=0,(x-y)/2)%b=0 ，即m%b=0 ，n%b=0 ，所以b是m和n的公约数，有g_c_d( x,y ) y ：1.均为偶数g_c_d( x,y ) =2g_c_d( x/2,y/2 )；2.均为奇数g_c_d( x,y ) = g_c_d( (x+y)/2,(x-y)/2 )；2.x奇y偶 g_c_d( x,y ) = g_c_d( x,y/2 )；3.x偶y奇 g_c_d( x,y ) = g_c_d( x/2,y ) 或g_c_d( x,y )=g_c_d( y,x/2 )；现在我们已经有了递归式，还需要再找出一个退化情况。注意到g_c_d(x,x)=x，我们就用这个。*/unsigned int gcd(unsigned int x,unsigned int y) unsigned int i,j,t; if (x = 0) return y; if (y = 0) return x; for (i = 0 ; 0 = (x & 1 );x = 1 ,+i); for (j = 0 ; 0 = (y & 1 );y = 1 ,+j); if (j i) i = j; for (;) if(x y) t = y,y = x,x = t; if( 0 = (x -= y) return y = 1 ); /*P102 T0415输出156的二进制、进制、进制和进制的对照表*/#include #include #include /required by class string.using namespace std;#define I 156void main() string s;/存储二进制的各个位 int i=1,a; for(;i=I;i+) a=i; coutdecat; s.clear(); /计算数的二进制表示 while(a) s=(char)(a%2)+48)+s; a/=2; coutsetw(8)setfill(0)st; coutoctithexiendl; /*P102 T0416输出个数，按从大到小的顺序输出*/#include using namespace std;void main() int a,b,c,d; cinabcd; if(ab) swap(a,b); if(ac) swap(a,c); if(ad) swap(a,d); if(bc) swap(b,c); if(bd) swap(b,d); if(cd) swap(c,d); couta b c dendl;/*P102 T0417求解一元二次方程的根*/#include #include using namespace std;void main() double a,b,c; double delta; coutPlease Enter a,b,cabc; if(fabs(a)1e-10 & fabs(b)1e-10)/a=0 and b=0,Input error couta and b are zero endl; return; if(fabs(a)1e-10)/a=0 coutThe Only root is c/bendl; else delta=b*b-4*a*c; if(fabs(delta)1e-10)/two same roots coutthe two same roots are :endl; cout-b/2/a0)/two difference roots couthas two roots :endl; cout(-b+sqrt(delta)/2/aendl; cout(-b-sqrt(delta)/2/aendl; else/two complex roots couthas two complex roots :endl; cout-b/2/a+sqrt(-delta)/2/aiendl; cout-b/2/a-sqrt(-delta)/2/aiendl; /*P102 T0419求正整数的所有因子*/#include using namespace std;void main() int a,i; coutPlese Enter aa; for(int i=1;ia/2+1;i+) if(a%i) continue; coutitendl; /*P102 T0420计算输入正整数的各位的数字的和，如输入，输出*/#include using namespace std;void main() int a,sum; while(1) coutPlese Enter aa; if(a0) return; sum=0; while(a) sum+=a%10; a/=10; coutsumendl; /*P102 T0421求数列/1，/2，/3，/5，/8，.前20项之和*/#include using namespace std;void main() int n1,n2,n3; int d1,d2,d3; n1=2;n2=3; d1=1;d2=2; double sum=0; sum+=(double)n1/d1+(double)n2/d2; for(int i=0;i18;i+) n3=n1+n2; d3=d1+d2; sum+=(double)n3/d3; n1=n2; d1=d2; n2=n3; d2=d3; coutsumendl;Chapter 5/*p136 T5.5求400以内的亲密对数，如果A的因子之和等于B，B的因子之和等于A，则A和B是亲密对数*/#include#includeusing namespace std;int factorialSum(int n)int sum=0;for(int i=1;i=n/2;i+)if(n%i=0)sum+=i;return sum;void main()int fs=0;for(int i=1;i=400;i+)fs=factorialSum(i);for(int j=i;j=400;j+)if(fs=j & factorialSum(j)=i)coutisetw(5)jendl;break;/*p136 T5.6编写一个递归函数，将一个十进制正整数转换成任意进制。*/#include using namespace std;void trans(int n,int base)if(nbase)coutn;elsetrans(n/base,base);coutn%base;void main()trans(375,4);/将十进制的375转换成4进制/*p136 T5.6编写一个函数，将一个数转换成任意进制。*/#include using namespace std;int reverse(int n,int base)int sum=0;while(n)sum=sum*10+n%base;n/=base;return sum;void main()coutreverse(reverse(378,8),10);/*p136 T5.10用牛顿迭代法求方程的根，初值由键盘输入（1.5）*/#include#includeusing namespace std;double f(double x)return 2*x*x*x-4*x*x+3*x-6;double f1(double x)return 6*x*x-4*x+3;double fun(double x1,double (*f1)(double),double (*f2)(double)double x0;dox0=x1;x1=x0-(*f1)(x0)/(*f2)(x0);while(fabs(x1-x0)1e-7);return x1;void main()double x0,x1;coutplease Enter the x1x1;coutfun(x1,f,f1)endl;/*p136 T5.11验证歌德巴赫猜想：任意一个充分大的偶数总可以分解为两个素数之和。*/#include #include using namespace std;int isPrime(int n)if(n=1) return 0;if(n=2) return 1;for(int i=2;in;for(int i=2;i=n-2;i+)if(isPrime(i) & isPrime(n-i)coutn=i+n-iendl;/*p137 T5.14用内联函数circleArea提示用户输入园半径，计算并打印园面积。*/#include using namespace std;#define PI 3.14159inline void circleArea()double radius;coutradius;coutPI*radius*radius;void main()area();/*p137 T5.16编写一个递归函数，实现反序输出一个函数。*/#include using namespace std;void reverse(char *str)if(strlen(str)=1)cout*str;elsereverse(str+1);cout*str;void main()reverse(abcd);/*p137 T5.19用递归方法和非递归方法输出Hermite前n项。*/#include #include using namespace std;double Hermite(double x,int n)/递归方法if(n=0)return 1;else if(n=1)return 2*x;elsereturn 2*x*Hermite(x,n-1)-2*(n-1)*Hermite(x,n-2);void Hermite1(double x,int n)/非递归方法double H0=1,H1=2*x,H2;coutH0tH1t;for(int i=2;in;i+)H2=2*x*H1-2*(i-1)*H0;coutH2t;H0=H1;H1=H2;void main()for(int i=0;i10;i+)coutHermite(1.0,i)t;coutendl;Hermite1(1.0,10);Chapter 6/*求组合算法*/#include using namespace std;#define MAXN 100 int aMAXN;void comb(int m,int k) int i,j; for(i=m;i=k;i-) ak=i; if(k1) comb(i-1,k-1); else for(j=a0;j0;j-) printf(%4d,aj); printf(n); void main() a0=3; comb(4,a0); /*P159 T6.3求n个数的均方差*/#include using namespace std;double average(double a,int n)double avg=0.0;for(int i=0;in;i+)avg+=ai;return avg/n;double fangcha(double a,int n)double M=average(a,n);double D=0;for(int i=0;in;i+)D+=(ai-M)*(ai-M);return D;void main()double a10=1,2,3,4,5,6,7,8,9,0;coutfangcha(a,10);/*P159 T6.4求一个方阵的两条对角线的元素之和*/#include #include using namespace std;void main()const int n=5;int ann;int i,j;int sum=0;srand(unsigned)time(NULL);for(i=0;in;i+)for(j=0;jn;j+)aij=rand();if(i=j | i+j=n-1)/两条对角线元素下标特点sum+=aij;coutaijt;coutendl;coutthe sum is:sumendl;/*P159 T6.4用二维数组存放一个班级20名同学的两门课程的成绩，先