《计算机常用算法与程序设计案例教程》习题解答

《计算机常用算法与程序设计案例教程》习题解答提要习题11-1分数分解算法描述把真分数a/b分解为若干个分母为整数分子为“1”的埃及分数之和：（1）寻找并输出小于a/b的最大埃及分数1/c；（2）若c900000000，则退出；（3）若c≤900000000，把差a/b-1/c整理为分数a/b，若a/b为埃及分数，则输出后结束。（4）若a/b不为埃及分数，则继续（1）、（2）、（3）。试描述以上算法。解：设)(intabd(这里int(x)表示取正数x的整数)，注意到1dabd，有)1()1(11dbbdadba算法描述：令c=d+1，则input(a,b)while(1){c=int(b/a)+1;if(c900000000)return;else{print(1/c+);a=a*c-b;b=b*c;//a,b迭代，为选择下一个分母作准备if(a==1){print(1/b);return;}}}1-2求出以下程序段所代表算法的时间复杂度（1）m=0;for(k=1;k=n;k++)for(j=k;j=1;j--)m=m+j;解：因s=1+2+…+n=n(n+1)/2时间复杂度为O(n2)。（2）m=0;for(k=1;k=n;k++)for(j=1;j=k/2;j++)m=m+j;解：设n=2u+1，语句m=m+1的执行频数为s=1+1+2+2+3+3+…+u+u=u(u+1)=(n−1)(n+1)/4设n=2u，语句m=m+1的执行频数为s=1+1+2+2+3+3+…+u=u2=n2/4时间复杂度为O(n2)。（3）t=1;m=0;for(k=1;k=n;k++){t=t*k;for(j=1;j=k*t;j++)m=m+j;}解：因s=1+2×2!+3×3!+…+n×n!=(n+1)!−1时间复杂度为O((n+1)!).（4）for(a=1;a=n;a++){s=0;for(b=a*100−1;b=a*100−99;b−=2){for(x=0,k=1;k=sqrt(b);k+=2)if(b%k==0){x=1;break;}s=s+x;}if(s==50)printf(%ld\n,a);break;}}解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环/2b次。因而k循环体的执行次数s满足25(991991001)250(12)432502506snnnnnn＜＜＜＜时间复杂度为O(nn)。1-3若p(n)是n的多项式，证明：O(log(p(n)))=O(logn)。证：设m为正整数，p(n)=a1×nm+a2×nm-1+…+am×n，取常数cma1+(m-1)a2+…+am,则log(p(n))=ma1×logn+(m-1)a2×logn+…=(ma1+(m-1)a2+…)×lognclogn因而有O(log(p(n)))=O(logn)。1-4构建对称方阵观察图1-5所示的7阶对称方阵：图1-57阶对称方阵试构造并输出以上n阶对称方阵。解：这是一道培养与锻炼我们的观察能力与归纳能力的案例，一个一个元素枚举赋值显然行不通，必须全局着眼，分区域归纳其构造特点，分区域枚举赋值。（1）设计要点设方阵中元素的行号为i，列号为j。可知主对角线：i=j；次对角线：i+j=n+1。两对角线赋值“0”。按两条对角线把方阵分成上部、左部、右部与下部4个区,如图1-6所示。图1-6对角线分成的4个区上部按行号i赋值；下部按行号函数n+1-i赋值。左部按列号j赋值；右部按列号函数n+1-j赋值。（2）程序实现#includestdio.hvoidmain(){inti,j,n,a[30][30];printf(请确定方阵阶数n:);scanf(%d,&n);for(i=1;i=n;i++)for(j=1;j=n;j++){if(i==j||i+j==n+1)a[i][j]=0;//方阵对角线元素赋值if(i+jn+1&&ij)a[i][j]=i;//方阵上部元素赋值if(i+jn+1&&ij)a[i][j]=j;//方阵左部元素赋值if(i+jn+1&&ij)a[i][j]=n+1-i;//方阵下部元素赋值if(i+jn+1&&ij)a[i][j]=n+1-j;//方阵右部元素赋值}printf(%d阶对称方阵为:\n,n);for(i=1;i=n;i++){for(j=1;j=n;j++)//输出对称方阵printf(%3d,a[i][j]);printf(\n);}}1-5据例1-2的算法，写出求解n个“1”组成的整数能被2011整除的程序。修改程序，求出n至少为多大时，n个“1”组成的整数能被2013整除？解：程序为#includestdio.hvoidmain(){inta,c,p,n;p=2011;c=1111;n=4;//变量c与n赋初值while(c!=0)//循环模拟整数竖式除法{a=c*10+1;c=a%p;n=n+1;//每试商一位n增1}printf(由%d个1组成的整数能被%d整除。\n,n,p);}习题22-1解不等式设n为正整数，解不等式2011/12/1113/12/1112/11112010n解：上下限一般为键盘输入的a,b。//解不等式:a1+1/(1+1/2)+...+1/(1+1/2+...+1/n)b#includestdio.h#includemath.hvoidmain(){longa,b,c,d,i;doublets,s;printf(请输入a,b:);scanf(%d,%d,&a,&b);i=0;ts=0;s=0;while(sa){i=i+1;ts=ts+(double)1/i;s=s+1/ts;}c=i;while(sb){i=i+1;ts=ts+(double)1/i;s=s+1/ts;}d=i-1;printf(\n满足不等式的正整数n为:%ld≤n≤%ld\n,c,d);}2-2韩信点兵韩信在点兵的时候，为了知道有多少个兵，同时又能保住军事机密，便让士兵排队报数。按从1至5报数,记下最末一个士兵报的数为1；再按从1至6报数,记下最末一个士兵报的数为5；再按1至7报数,记下最末一个报的数为4；最后按1至11报数,最末一个士兵报的数为10。你知道韩信至少有多少兵?1.求解要点设兵数为x，则x满足下述的同余方程组:x=5y+1即x=1(mod5)x=6z+5x=5(mod6)x=7u+4x=4(mod7)x=11v+10x=10(mod11)其中y,z,u,v都为正整数。试求满足以上方程组的最小正整数x。应用枚举可得到至少的兵数。x从1开始递增1取值枚举当然可以，但不必要。事实上枚举次数可联系问题的具体实际大大缩减。（1)注意到x除11余10，于是可设置x从21开始，以步长11递增。此时，只要判别前三个条件即可。（2)由以上第2，4两方程知x+1为11的倍数，也为6的倍数。而11与6互素，因而x+1必为66的倍数。于是取x=65开始，以步长66递增。此时,只要判别x%5=1与x%7=4两个条件即可。这样可算得满足条件的最小整数x即点兵的数量。2.程序实现//韩信点兵#includestdio.hvoidmain(){longintx;x=65;while(1){x=x+66;if(x%5==1&&x%7==4){printf(至少有兵:%ld个。,x);break;}}}2-3分解质因数对给定区间[m,n]的正整数分解质因数,每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。例如,2012=2*2*503,2011=(素数!)。解：对区间中的每一个整数i(b=i)，用k(2——sqrt(i))试商：若不能整除，说明该数k不是b的因数，k增1后继续试商。若能整除，说明该数k是b的因数，打印输出k*；b除以k的商赋给b(b=b/k)后继续用k试商(注意，可能有多个k因数)，直至不能整除，k增1后继续试商。按上述从小至大试商确定的因数显然为质因数。如果有大于sqrt(n)的因数(至多一个!),在试商循环结束后要注意补上，不要遗失。如果整个试商后b的值没有任何缩减，仍为原待分解数n，说明n是素数，作素数说明标记。若k是b的因数，按格式输出，然后b=b/k后继续试商k。若k不是b的因数，则k增1后继续。若上述试商完成后1bi，说明i有一个大于sqrt(i)的因数，要补上该因数。若试商后b还是原来的i,则i是素数。//质因数分解乘积形式#includemath.h#includestdio.hvoidmain(){longintb,i,k,m,n,w=0;printf([m,n]中整数分解质因数（乘积形式）.\n);printf(请输入m,n:);scanf(%ld,%ld,&m,&n);for(i=m;i=n;i++)//i为待分解的整数{printf(%ld=,i);b=i;k=2;while(k=sqrt(i))//k为试商因数{if(b%k==0){b=b/k;if(b1){printf(%ld*,k);continue;//k为质因数,返回再试}if(b==1)printf(%ld\n,k);}k++;}if(b1&&bi)printf(%ld\n,b);//输出大于i平方根的因数if(b==i){printf((素数!)\n);w++;}//b=i,表示i无质因数}}2-4基于素数代数和的最大最小定义和：)12()12(97755331)(nnns(和式中第k项±(2k-1)*(2k+1)的符号识别：当(2k-1)与(2k+1)中至少有一个素数，取“+”；其余取“-”。例如和式中第13项取“-”，即为-25*27。)1)求s(2011)。2)设1=n=2011，当n为多大时，s(n)最大。3)设1=n=2011，当n为多大时，s(n)最小。解：代数和式中各项的符号并不是简单的正负相间，而是随着构成素数而改变。因而在求和之前应用“试商判别法”对第k个奇数2k-1是否为素数进行标注：若2k-1为素数，标注a[k]=1；否则，若2k-1不是素数，a[k]=0。设置k循环（1——n），循环中分别情况求和：若a[k]+a[k+1]=1，即(2k-1)与(2k+1)中至少有一个素数，实施“+”；否则，若a[k]+a[k+1]==0，即(2k-1)与(2k+1)中没有素数，实施“-”。同时，设置最大值变量smax，最小值变量smin。在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；与smin比较确定最小值，同时记录此时的项数k2。//基于素数的整数和#includestdio.h#includemath.hvoidmain(){intt,j,n,k,k1,k2,a[3000];longs,smax,smin;printf(请输入整数n:);scanf(%d,&n);for(k=1;k=n+1;k++)a[k]=0;for(k=2;k=n+1;k++){for(t=0,j=3;j=sqrt(2*k-1);j+=2)if((2*k-1)%j==0){t=1;break;}if(t==0)a[k]=1;//标记第k个奇数2k-1为素数}s=3;smax=0;smin=s;for(k=2;k=n;k++){if(a[k]+a[k+1]=1)s+=(2*k-1)*(2*k+1);//实施代数和elses-=(2*k-1)*(2*k+1);if(ssmax){smax=s;k1=k;}//比较求最大值smaxif(ssmin){smin=s;k2=k;}//比较求最大值smin}printf(s(%d)=%ld\n,n,s);printf(当k=%d时s有最大值:%ld\n,k1,smax);prin