《计算机常用算法与程序设计案例教程习题答.doc》由会员分享，可在线阅读，更多相关《计算机常用算法与程序设计案例教程习题答.doc（77页珍藏版）》请在三一文库上搜索。
1、计算机常用算法与程序设计案例教程习题解答提要习题11-1 分数分解算法描述把真分数a/b分解为若干个分母为整数分子为“1”的埃及分数之和： （1） 寻找并输出小于a/b的最大埃及分数1/c； （2） 若c900000000，则退出； （3） 若c900000000，把差a/b-1/c整理为分数a/b，若a/b为埃及分数，则输出后结束。 （4） 若a/b不为埃及分数，则继续（1）、（2）、（3）。试描述以上算法。解：设 (这里int(x)表示取正数x的整数)，注意到，有 算法描述：令c=d+1，则 input (a,b) while(1) c=int(b/a)+1; if(c900000000)
2、 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=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)=(n1)(n+1)/4设n=2u，语句m=m+1的执行频数
3、为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+22!+ 33!+ nn!=(n+1)!1时间复杂度为O(n+1)!).（4）for(a=1;a=a*10099;b=2) for(x=0,k=1;kma1+(m-1)a2+am, 则log(p(n)=ma1logn+(m-1)a2logn+=(ma1+(m-1)a2+)logn clogn因而有O(log(p(n)=O(logn)。1-4 构建对称方阵观察图1-5所示的7阶对称方阵： 图1
4、-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,a3030; printf(
5、 请确定方阵阶数n: ); scanf(%d,&n); for(i=1;i=n;i+) for(j=1;j=n;j+) if(i=j | i+j=n+1) aij=0; / 方阵对角线元素赋值 if(i+jn+1 & ij) aij=i; / 方阵上部元素赋值 if(i+jj) aij=j; / 方阵左部元素赋值 if(i+jn+1 & ij) aij=n+1-i; / 方阵下部元素赋值 if(i+jn+1 & ij) aij=n+1-j; / 方阵右部元素赋值 printf( %d阶对称方阵为:n,n); for(i=1;i=n;i+) for(j=1;j=n;j+) / 输出对称方阵 pr
6、intf(%3d,aij); 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);习题22-1 解不等式设n为正整数，解不等式解：上下限一般为键盘输入的a,
7、b。/ 解不等式: a1+1/(1+1/2)+.+1/(1+1/2+.+1/n)b#include #includevoid main() long a,b,c,d,i; double ts,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为: %ldn%ld n,c,d);2-2 韩信点
8、兵韩信在点兵的时候，为了知道有多少个兵，同时又能保住军事机密，便让士兵排队报数。按从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开始递增
9、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) print
10、f(至少有兵: %ld 个。,x); break; 2-3 分解质因数对给定区间m,n的正整数分解质因数,每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。例如, 2012=2*2*503, 2011=(素数!)。解：对区间中的每一个整数i(b=i)，用k(2sqrt(i)试商：若不能整除，说明该数k不是b的因数，k增1后继续试商。若能整除，说明该数k是b的因数，打印输出k*；b除以k的商赋给b(b=b/k)后继续用k试商(注意，可能有多个k因数)，直至不能整除，k增1后继续试商。按上述从小至大试商确定的因数显然为质因数。如果有大于sqrt(n)的因数(至多一
11、个!),在试商循环结束后要注意补上，不要遗失。如果整个试商后b的值没有任何缩减，仍为原待分解数n，说明n是素数，作素数说明标记。若k是b的因数，按格式输出，然后b=b/k后继续试商k。若k不是b的因数，则k增1后继续。若上述试商完成后1bi，说明i有一个大于sqrt(i)的因数，要补上该因数。若试商后b还是原来的i,则i是素数。/ 质因数分解乘积形式 #includemath.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);f
12、or(i=m;i=n;i+) / i为待分解的整数 printf(%ld=,i); b=i;k=2; while(k1) printf(%ld*,k);continue; / k为质因数,返回再试 if(b=1) printf(%ldn,k); k+; if(b1 & bi) printf(%ldn,b); / 输出大于i平方根的因数 if(b=i) printf(素数!)n);w+; / b=i,表示i无质因数 2-4 基于素数代数和的最大最小定义和： (和式中第k项(2k-1)*(2k+1)的符号识别：当(2k-1)与(2k+1)中至少有一个素数，取“+”；其余取“-”。例如和式中第13项
13、取“-”，即为-25*27。)1) 求s(2011)。2) 设1=n=2011，当n为多大时，s(n)最大。3) 设1=n=1，即(2k-1)与(2k+1)中至少有一个素数，实施“+”；否则，若ak+ak+1=0，即(2k-1)与(2k+1)中没有素数，实施“-”。同时，设置最大值变量smax，最小值变量smin。在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；与smin比较确定最小值，同时记录此时的项数k2。/ 基于素数的整数和 #include#includevoid main() int t,j,n,k,k1,k2,a3000; long s,smax,sm
14、in; printf( 请输入整数n: ); scanf(%d,&n); for(k=1;k=n+1;k+) ak=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) ak=1; / 标记第k个奇数2k-1为素数 s=3;smax=0;smin=s; for(k=2;k=1) s+=(2*k-1)*(2*k+1); / 实施代数和 else s-=(2*k-1)*(2*k+1); if(ssmax)smax=s;k1=k; / 比较求最大值smax if(s1(k=09)，
15、说明d中存在有重复数字，返回。在不存在重复数字的情形下，检测若f0+f1+f4=0，说明7位平方数d中没有数字“0”,“1”,“4”,d满足题意要求，打印输出。/ 组成没有重复数字的7位平方数 #include #include void main()int k,m,n,t,f10; 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;k0) m=w%10;fm+;w=w/10; for(t=0,k=1;k1) t=1; / 测试三个平方数是否有重复数字
16、if(t=0 & f0+f1+f4=0) / 测试平方数中没有数字0,1,4 n+; printf( %2d: ,n); printf( %ld=%ld2 n,d,a); printf( 共可组成%d个没有重复数字的7位平方数.n,n); 2-6 写出例2-2中对称方阵的完整程序，并运行程序。对称方阵程序：#include void main()int i,j,n,a3030; printf( 请确定方阵阶数n: ); scanf(%d,&n); for(i=1;i=n;i+) for(j=1;j=n;j+) if(i+j=n+1 & i=j) aij=(n+1)/2-i+1; / 方阵上部元
17、素赋值 if(i+jj) aij=(n+1)/2-j+1; / 方阵左部元素赋值 if(i+j=n+1 & i=j) aij=i-n/2; / 方阵下部元素赋值 if(i+jn+1 & ij) aij=j-n/2; / 方阵右部元素赋值 printf( %d阶对称方阵为:n,n); for(i=1;i=n;i+) for(j=1;j=n;j+) / 输出对称方阵 printf(%3d,aij); printf(n); 2-7 四则运算式把数字1,2,.,9这9个数字填入以下含加减乘除的综合运算式中的9个中,使得该式成立+-=0 要求数字1,2,.,9这9个数字在各式中都出现一次且只出现一次，且
18、约定数字“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(19)的个数。若某一f(x)不为1，不满足数字1,2,.,9这九个数字都出现一次且只出现一次，标记t=1.若所有f(x)全为1，满足数字1,2,.,9这九个数字都出现一次且
19、只出现一次，保持标记t=0, 则输出所得的完美综合运算式。设置n统计解的个数。（2） 程序实现/ 四则运算式 #include void main()int x,y,t,k,a,b,c,d,e,n=0; int m6,f11; 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;d100) continue; m1=a;m2=c;m3=e;m4=b;m5=d; for(x=0;x=9;x+) fx=0; for(k=1;k0) x=y%10;fx=fx+1;y=(y-x)/10; / 分离数
20、字f数组统计 for(t=0,x=1;x=9;x+) if(fx!=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个奇数中的合数的个数
21、。对于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;kn，则区间f+1,f+n中的n个数为最小的连续n个合数。应用试商法求指定区间c,d(约定起始数c=3，d=c+10000)上的所有素数。求出该区间内的一个素数m，设前一个素数为f,
22、判别：若m-fn，则输出结果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;jn) / 满足条
23、件即行输出 printf(最小的%d个连续合数区间为:,n); printf(%ld,%ld。 n,f+1,f+n); getch();return; if(t=0) f=m; / 每求出一个素数m后赋值给f if(md) c=d+2;d=c+10000; / 每一轮试商后改变c,d转下一轮 2-10 和积9数字三角形求解和为给定的正整数s（s45）的9个互不相等的正整数填入9数字三角形，使三角形三边上的4个数字之和相等（s1）且三边上的4个数字之积也相等（s2）。图2-7 9数字三角形（1）求解要点。把和为s的9个正整数存储于b数组b(1)，b(9)中，分布如下图所示。为避免重复，不妨约定三
24、角形中数字“下小上大、左小右大”，即b(1)b(7)b(4)且b(2)b(3)且b(6)b(5)且b(9)b(8)。图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)%30，则继续探索；否则，记s1=(s+b(1)+b(7)+b(4)/3。2）根据约定对b(3)、b(5)和b(8)的值进行探索，设置： b(3)的取值范围为(s1
25、-b(1)-b(4)/2+1s1-b(1)-b(4)。 b(5)的取值范围为(s1-b(4)-b(7)/2+1s1-b(4)-b(7)。 b(8)的取值范围为(s1-b(1)-b(7)/2+1s1-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，则继续探索；否则探索成功，打印输出结果，接着继续探索直到所有数字组探索
26、完毕为止。（2）9数字三角形求解程序设计。/ 9数字三角形求解 #include#includevoid main() int k,j,t,s,s1,s2,n,b10; printf( 请输入正整数s：); scanf(%d,&s); n=0; for(b1=1;b1=(s-21)/3;b1+) for(b7=b1+1;b7=(s-28)/2;b7+) for(b4=b7+1;b4=s-36;b4+) if(s+b1+b4+b7)%3!=0) continue; s1=(s+b1+b4+b7)/3; for(b3=(s1-b1-b4)/2+1;b3s1-b1-b4;b3+) for(b5=(s
27、1-b4-b7)/2+1;b5s1-b4-b7;b5+) for(b8=(s1-b1-b7)/2+1;b8s1-b1-b7;b8+) b2=s1-b1-b4-b3; b6=s1-b4-b7-b5; b9=s1-b1-b7-b8; t=0; for(k=1;k=8;k+) for(j=k+1;j=9;j+) if(bk=bj) t=1;k=8;break; if(t=1) continue; s2=b1*b2*b3*b4; if(b4*b5*b6*b7!=s2) continue; if(b1*b9*b8*b7!=s2) continue; n+; printf( %3d：%2d,n,b1);
28、for(k=2;k=9;k+) printf(, %2d,bk); printf( s1=%d, s2=%d n,s1,s2); printf(共%d个解。,n);习题33-1 递推求解b数列已知b数列定义：递推求b数列的第20项与前20项之和。解： #include void main() int k,n; long b3000,s; printf( 请输入n: ); scanf(%d,&n); b1=1;b2=2;s=3; for(k=3;k=n;k+) bk=3*bk-1-bk-2;s+=bk; printf( b(%d)=%ld n,n,bn); printf( s=%ld n,s);
29、 3-2 双关系递推数列集合M定义如下：1）2）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)=3*m(p3)+1;p3+;特别注意：两队列若出现相等时，给m数组赋值后，两排头都要增1。if(2*m(p2)=3*m(p3) m(i)=2*m(p2)+1;p2+;
30、 p3+; / 为避免重复项，P2，p3均须增1 （2） 程序设计/ 双关系递推 #include void main() int n,p2,p3,i;long s,m3000; m1=1;s=1; p2=1;p3=1; / 排头p2,p3赋初值 printf( 请输入n: ); scanf(%d,&n); for(i=2;i=n;i+) if(2*mp23*mp3) mi=2*mp2+1; s+=mi;p2+; else mi=3*mp3+1; s+=mi; if(2*mp2=3*mp3) p2+; / 为避免重复项，P2须增1 p3+; printf( m(%d)=%ldn,n,mn);
31、printf( s=%ldn,s); 3-3 多幂序列设x,y,z为非负整数，试计算集合的元素由小到大排列的多幂序列第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循环中通过比较赋值：当ab且ac时，由赋值fk=a确定为序列的第k项；然后a=a*2，即a按递推规律乘2，为
32、后一轮比较作准备；当ba且bc时，由赋值fk=b确定为序列的第k项；然后b=b*3，即b按递推规律乘3，为后一轮比较作准备。当ca且cb时，由赋值fk=c确定为序列的第k项；然后c=c*5，即c按递推规律乘5，为后一轮比较作准备。递推过程描述：a=2;b=3;c=5; / 为递推变量a,b,c赋初值 for(k=2;k=n;k+) if(ab & ac) fk=a;a=a*2; / 用a给fk赋值 else if(ba & bc) fk=b;b=b*3; / 用b给fk赋值 else fk=c;c=c*5; / 用c给fk赋值 在这一算法中，变量a,b,c是变化的，分别代表2的幂、3的幂与5的幂。上述递推算法的时间复杂度与空间复杂度均为O(n)。（2）多幂序列程序实现/ 多幂序列求解 #include void main()int k,m,t,