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

《计算机常用算法与程序设计案例教程习题答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《计算机常用算法与程序设计案例教程》习题解答提要习题11-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(x)表示取正数x的整数)，注意到，有算法描述：令c=d+1，则input(a,b)while(1){c=int(b/a)+1;if(c>900000000)retu

2、rn;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

3、)/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)pri

4、ntf("%ld",a);break;}}解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环次。因而k循环体的执行次数s满足时间复杂度为O()。1-3若p(n)是n的多项式，证明：O(log(p(n)))=O(logn)。证：设m为正整数，p(n)=a1×nm+a2×nm-1+…+am×n，取常数c>ma1+(m-1)a2+…+am,则log(p(n))=ma1×logn+(m-1)a2×logn+…=(ma1+(m-1)a2+…)×logn

5、方阵试构造并输出以上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）程序实现#includevoidmain(){inti,j,n,a[30][30];p

6、rintf("请确定方阵阶数n:");scanf("%d",&n);for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(i==j

7、

8、i+j==n+1)a[i][j]=0;//方阵对角线元素赋值if(i+jj)a[i][j]=j;//方阵左部元素赋值if(i+j>n+1&&i>j)a[i][j]=n+1-i;//方阵下部元素赋值if(i+j>n+1&&i

9、<=n;i++){for(j=1;j<=n;j++)//输出对称方阵printf("%3d",a[i][j]);printf("");}}1-5据例1-2的算法，写出求解n个“1”组成的整数能被2011整除的程序。修改程序，求出n至少为多大时，n个“1”组成的整数能被2013整除？解：程序为#includevoidmain(){inta,c,p,n;p=2011;c=1111;n=4;//变量c与n赋初值while(c!=0)//循环模拟整数竖式