《计算机常用算法与程序设计案例教程》
习题解答提要
习题1
1-1 分数分解算法描述
把真分数a/b 分解为若干个分母为整数分子为“1”的埃及分数之和： （1） 寻找并输出小于a/b 的最大埃及分数1/c ； （2） 若c>900000000，则退出；
（3） 若c ≤900000000，把差a/b-1/c 整理为分数a/b ，若a/b 为埃及分数，则输出后结束。
（4） 若a/b 不为埃及分数，则继续（1）、（2）、（3）。 试描述以上算法。
解：设)(int a
b d = (这里int(x)表示取正数x 的整数)，注意到1+< b d ，有 ) 1()1(1 1+-+++=d b b d a d b a 算法描述：令c=d+1，则 input (a,b) while(1) {c=int(b/a)+1; if(c>900000000) 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,k2次。因而k循环体的执行次数s满足 250(1250250s ＜＜＜ 时间复杂度为O(n n )。 1-3 若p(n)是n 的多项式，证明：O(log(p(n)))=O(logn)。 证：设m 为正整数，p(n)=a1×n m +a2×n m-1 +…+am ×n ， 取常数c>ma1+(m-1)a2+…+am, 则 log(p(n))=ma1×logn+(m-1)a2×logn+…=(ma1+(m-1)a2+…)×logn 因而有O(log(p(n)))=O(logn)。 1-4 构建对称方阵 观察图1-5所示的7阶对称方阵： 图1-5 7阶对称方阵 试构造并输出以上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） 程序实现 #include void main() {int i,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+j a[i][j]=i; // 方阵上部元素赋值 if(i+j a[i][j]=j; // 方阵左部元素赋值 if(i+j>n+1 && i>j) a[i][j]=n+1-i; // 方阵下部元素赋值 if(i+j>n+1 && i 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整除？ 解：程序为 #include void main() { int a,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); } 习题2 2-1 解不等式 设n 为正整数，解不等式 2011/12/111 3/12/1112/11112010<++++++++++ 解：上下限一般为键盘输入的a,b 。 // 解不等式: a<1+1/(1+1/2)+...+1/(1+1/2+...+1/n) #include { long a,b,c,d,i; double ts,s; printf(" 请输入a,b: "); scanf("%d,%d",&a,&b); i=0;ts=0;s=0; while(s ts=ts+(double)1/i; s=s+1/ts; } c=i; while(s 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 (mod 5) x=6z+5 x=5 (mod 6) x=7u+4 x=4 (mod 7) x=11v+10 x=10 (mod 11) 其中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. 程序实现 // 韩信点兵 #include void main() { long int x; 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后继续。 若上述试商完成后1 若试商后b还是原来的i,则i是素数。 // 质因数分解乘积形式 #include"math.h" #include void main() {long int b,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(b>1) {printf("%ld*",k); continue; // k为质因数,返回再试 } if(b==1) printf("%ld\n",k); } k++; } if(b>1 && b printf("%ld\n",b); // 输出大于i平方根的因数 if(b==i) {printf("(素数!)\n");w++;} // b=i,表示i无质因数 } } 2-4 基于素数代数和的最大最小 定义和： ? + ? ± ± + + n s n =n ? ? - 9 ? 2( )1 )1 2( 7 7 5 )(+ 3 1 5 3 (和式中第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。 // 基于素数的整数和 #include #include void main() { int t,j,n,k,k1,k2,a[3000]; long s,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); // 实施代数和 else s-=(2*k-1)*(2*k+1); if(s>smax){smax=s;k1=k;} // 比较求最大值smax if(s } printf("s(%d)=%ld \n",n,s); printf("当k=%d时s有最大值: %ld\n",k1,smax); printf("当k=%d时s有最小值: %ld\n",k2,smin); } 2-5 特定数字组成的平方数 用数字2,3,5,6,7,8,9可组成多少个没有重复数字的7位平方数？ 解：求出最小7位数的平方根b, 最大7位数的平方根c. 用a枚举[b，c]中的所有整数，计算d=a*a，这样确保所求平方数在d中。 设置f数组统计d中各个数字的个数。如果f[3]=2，即平方数d中有2个“3”。 检测若f[k]>1(k=0——9)，说明d中存在有重复数字，返回。 在不存在重复数字的情形下，检测若f[0]+f[1]+f[4]=0，说明7位平方数d中没有数字“0”,“1”,“4”,d满足题意要求，打印输出。 // 组成没有重复数字的7位平方数 #include #include void main() {int k,m,n,t,f[10]; long a,b,c,d,w; n=0; b=sqrt(2356789);c=sqrt(9876532); for(a=b;a<=c;a++) {d=a*a; w=d; // 确保d为平方数 for(k=0;k<=9;k++) f[k]=0; while(w>0) { m=w%10;f[m]++;w=w/10;} for(t=0,k=1;k<=9;k++) if(f[k]>1) t=1; // 测试三个平方数是否有重复数字 if(t==0 && f[0]+f[1]+f[4]==0) // 测试平方数中没有数字0,1,4 {n++; printf(" %2d: ",n); printf(" %ld=%ld^2 \n",d,a); } } printf(" 共可组成%d个没有重复数字的7位平方数.\n",n); } 2-6 写出例2-2中对称方阵的完整程序，并运行程序。 对称方阵程序： #include void main() {int i,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<=n+1 && i<=j) a[i][j]=(n+1)/2-i+1; // 方阵上部元素赋值 if(i+j a[i][j]=(n+1)/2-j+1; // 方阵左部元素赋值 if(i+j>=n+1 && i>=j) a[i][j]=i-n/2; // 方阵下部元素赋值 if(i+j>n+1 && i a[i][j]=j-n/2; // 方阵右部元素赋值 } printf(" %d阶对称方阵为:\n",n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) // 输出对称方阵 printf("%3d",a[i][j]); printf("\n"); } } 2-7 四则运算式 把数字1,2,...,9这9个数字填入以下含加减乘除的综合运算式中的9个□中,?使得该式成立 □□×□+□□□÷□-□□=0 要求数字1,2,...,9这9个数字在各式中都出现一次且只出现一次，且约定数字“1”不出现在数式的一位数中（即排除各式中的各个1位数为1这一平凡情形）。 （1）求解要点 设式右的5个整数从左至右分别为a,b,c,d,e,其中a,e为二位整数，b,d为大于1的一位整数，c为三位整数。设置a,b,c,d循环，对每一组a,b,c,d,计算e=a*b+c/d。若其中的c/d非整数，或所得e非二位数，则返回。 然后分别对5个整数进行数字分离，设置f数组对5个整数分离的共9个数字进行统计，f(x)即为数字x(1—9)的个数。 若某一f(x)不为1，不满足数字1,2,...,9这九个数字都出现一次且只出现一次，标记t=1. 若所有f(x)全为1，满足数字1,2,...,9这九个数字都出现一次且只出现一次，保持标记t=0, 则输出所得的完美综合运算式。 设置n统计解的个数。 （2）程序实现 // 四则运算式 #include void main() {int x,y,t,k,a,b,c,d,e,n=0; int m[6],f[11]; for(a=12;a<=98;a++) for(b=2;b<=9;b++) for(c=123;c<=987;c++) // 对a,b,c,d 实施枚举 for(d=2;d<=9;d++) {x=c/d;e=a*b+x; if(c!=x*d || e>100) continue; m[1]=a;m[2]=c;m[3]=e;m[4]=b;m[5]=d; for(x=0;x<=9;x++) f[x]=0; for(k=1;k<=5;k++) {y=m[k]; while(y>0) {x=y%10;f[x]=f[x]+1; y=(y-x)/10; // 分离数字f数组统计 } } for(t=0,x=1;x<=9;x++) if(f[x]!=1) {t=1; break;} // 检验数字0--9各只出现一次 if(t==0) // 输出一个解，用n统计个数 {n++; printf("%2d: %2d*%1d+%3d/%1d-%2d=0 \n",n,a,b,c,d,e); } } printf(" n=%d.\n",n); } 2-8 合数世纪探求 定义一个世纪的100个年号中不存在一个素数，即100个年号全为合数的世纪称为合数世纪。 探索最早的合数世纪。 （1）设计要点 应用穷举搜索，设置a世纪的的50个奇数年号(偶数年号无疑均为合数)为b，用k试商判别b是否为素数，用变量s统计这50个奇数中的合数的个数。 对于a世纪，若s=50，即50个奇数都为合数，找到a世纪为最早的合数世纪，打印输出后退出循环结束。 （2）合数世纪程序设计 // 合数世纪探求 #include #include void main() {long a,b,k; int s,x; a=1; while (1) {a++;s=0; // 检验a世纪 for(b=a*100-99;b<=a*100-1;b+=2) // 穷举a世纪奇数年号b {x=0; for(k=3;k<=sqrt(b);k+=2) if(b%k==0) {x=1;break;} if(x==0)break; // 当前为非合数世纪时，跳出循环进行下世纪的探求 s=s+x; // 年号b为合数时，x=1，s增1 } if(s==50) // s=50，即50个奇数均为合数 { printf("最早出现的合数世纪为 %ld 世纪!\n",a); break; } } } 2-9 最小连续n个合数 试求出最小的连续n个合数。（其中n是键盘输入的任意正整数。） （1）设计要点 求出区间[c,d]内的所有素数(区间起始数c可由小到大递增)，检验其中每相邻两素数之 差。若某相邻的两素数m,f之差大于n，即m-f>n，则区间[f+1,f+n]中的n个数为最小的连续n个合数。 应用试商法求指定区间[c,d](约定起始数c=3，d=c+10000)上的所有素数。求出该区间内的一个素数m，设前一个素数为f,?判别： 若m-f>n，则输出结果[f+1,f+n]后结束； 否则，作赋值f=m，为求下一个素数作准备。 如果在区间[c,d]中没有满足条件的解，则作赋值：c=d+2，d=c+10000，继续试商下去，直到找出所要求的解。 （2）程序实现 // 求最小的连续n个合数 #include #include void main() { long c,d,f,m,j; int t,n; printf(" 求最小的n个连续合数.\n"); printf(" 请输入n:"); scanf("%d",&n); c=3;d=c+10000; f=3; while(1) { for(m=c;m<=d;m+=2) { for(t=0,j=3;j<=sqrt(m);j+=2) if(m%j==0) // 实施试商 {t=1;break;} if(t==0 && m-f>n) // 满足条件即行输出 { printf("最小的%d个连续合数区间为:",n); printf("[%ld,%ld]。 \n",f+1,f+n); getch();return; } if(t==0) f=m; // 每求出一个素数m后赋值给f } if(m>d) {c=d+2;d=c+10000;} // 每一轮试商后改变c,d转下一轮 } } 2-10 和积9数字三角形 求解和为给定的正整数s（s≥45）的9个互不相等的正整数填入9数字三角形，使三角 形三边上的4个数字之和相等（s1）且三边上的4个数字之积也相等（s2）。 图2-7 9数字三角形 （1）求解要点。 把和为s的9个正整数存储于b数组b(1)，…，b(9)中，分布如下图所示。为避免重复，不妨约定三角形中数字“下小上大、左小右大”，即b(1) 图2-8 b数组分布示意图 可以根据约定对b(1)、b(7)和b(4)的值进行循环探索，设置： b(1)的取值范围为1～(s-21)/3（因其他6个数之和至少为21）。 b(7)的取值范围为b(1)+1～(s-28)/2。 b(4)的取值范围为b(7)+1～(s-36)。 同时探索判断步骤如下： 1）若(s+b(1)+b(7)+b(4))%3≠0，则继续探索；否则，记s1=(s+b(1)+b(7)+b(4))/3。 2）根据约定对b(3)、b(5)和b(8)的值进行探索，设置： b(3)的取值范围为(s1-b(1)-b(4))/2+1～s1-b(1)-b(4)。 b(5)的取值范围为(s1-b(4)-b(7))/2+1～s1-b(4)-b(7)。 b(8)的取值范围为(s1-b(1)-b(7))/2+1～s1-b(1)-b(7))。 同时根据各边之和为s1，计算出b(2)、b(6)和b(9)： b(2)=s1-b(1)-b(4)-b(3) b(6)=s1-b(4)-b(5)-b(7) b(9)=s1-b(1)-b(7)-b(8) 3）若b数组存在相同正整数，则继续探索。 4）设s2=b(1)*b(2)*b(3)*b(4)，若另两边之积不为s2，则继续探索；否则探索成功，打印输出结果，接着继续探索直到所有数字组探索完毕为止。 （2）9数字三角形求解程序设计。 // 9数字三角形求解 #include #include void main() { int k,j,t,s,s1,s2,n,b[10]; printf(" 请输入正整数s："); scanf("%d",&s); n=0; for(b[1]=1;b[1]<=(s-21)/3;b[1]++) for(b[7]=b[1]+1;b[7]<=(s-28)/2;b[7]++) for(b[4]=b[7]+1;b[4]<=s-36;b[4]++) { if((s+b[1]+b[4]+b[7])%3!=0) continue; s1=(s+b[1]+b[4]+b[7])/3; for(b[3]=(s1-b[1]-b[4])/2+1;b[3] b[2]=s1-b[1]-b[4]-b[3]; b[6]=s1-b[4]-b[7]-b[5]; b[9]=s1-b[1]-b[7]-b[8]; t=0; for(k=1;k<=8;k++) for(j=k+1;j<=9;j++) if(b[k]==b[j]) {t=1;k=8;break;} if(t==1) continue; s2=b[1]*b[2]*b[3]*b[4]; if(b[4]*b[5]*b[6]*b[7]!=s2) continue; if(b[1]*b[9]*b[8]*b[7]!=s2) continue; n++; printf(" %3d：%2d",n,b[1]); for(k=2;k<=9;k++) printf(", %2d",b[k]); printf(" s1=%d, s2=%d \n",s1,s2); } } printf("共%d个解。",n); } 习题3 3-1 递推求解b 数列 已知b 数列定义： )2(3,2,12121>-===--n b b b b b n n n 递推求b 数列的第20项与前20项之和。 解： #include { int k,n; long b[3000],s; printf(" 请输入n: "); scanf("%d",&n); b[1]=1;b[2]=2;s=3; for(k=3;k<=n;k++) { b[k]=3*b[k-1]-b[k-2]; s+=b[k]; } printf(" b(%d)=%ld \n",n,b[n]); printf(" s=%ld \n",s); } 3-2 双关系递推数列 集合M 定义如下： 1）M ∈1 2）21,31x M x M x M ∈?+∈+∈ 3）再无别的数属于M 试求集合M 元素从小到大排列的第2011个元素与前2011 个元素之和。 解：（1）设计要点 设n 个数在数组m 中，2x+1与3x+1均作为一个队列，从两队列中选一排头（数值较小者）送入数组m 中。所谓“排头”就是队列中尚未选入m 的最小的数（下标）。这里用p2表示2x+1这一列的排头的下标，用p3表示3x+1这一列的排头的下标。 if(2*m(p2)<3*m(p3)) { m(i)=2*m(p2)+1;p2++;} if(2*m(p2)>3*m(p3)) { m(i)=3*m(p3)+1;p3++;} 特别注意：两队列若出现相等时，给m 数组赋值后，两排头都要增1。 if(2*m(p2)==3*m(p3)) { m(i)=2*m(p2)+1; p2++; p3++; // 为避免重复项，P2，p3均须增1 } （2） 程序设计 // 双关系递推 #include {int n,p2,p3,i;long s,m[3000]; m[1]=1;s=1; p2=1;p3=1; // 排头p2,p3赋初值 printf(" 请输入n: "); scanf("%d",&n); for(i=2;i<=n;i++) if(2*m[p2]<3*m[p3]) { m[i]=2*m[p2]+1; s+=m[i]; p2++; } else { m[i]=3*m[p3]+1; s+=m[i]; if(2*m[p2]==3*m[p3]) p2++; // 为避免重复项，P2须增1 p3++; } printf(" m(%d)=%ld\n",n,m[n]); printf(" s=%ld\n",s); } 3-3 多幂序列 设x,y,z 为非负整数，试计算集合 }0,0,0|5,3,2{≥≥≥=z y x M z y x 的元素由小到大排列的多幂序列第n 项与前n 项之和。 （1）递推算法设计 集合由2的幂、3的幂与5的幂组成，实际上给出的是3个递推关系。 显然，第1项也是最小项为1（当x=y=z=0时）。 从第2项开始，为了实现从小到大排列，设置3个变量a,b,c ，a 为2的幂，b 为3的幂，c 为5的幂，显然a,b,c 互不相等。 设置k 循环（k=2,3,…,n ，其中n 为键盘输入整数），在k 循环外赋初值：a=2;b=3;c=5;s=1; 在k循环中通过比较赋值： 当a 当b 当c 递推过程描述： a=2;b=3;c=5; // 为递推变量a,b,c赋初值 for(k=2;k<=n;k++) { if(a { f[k]=a;a=a*2;} // 用a给f[k]赋值