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

《计算机常用算法与程序设计案例教程》

习题解答提要

习题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,k

2次。因而k 循环体的执行次数s 满足

250(1250250s L L ＜＜＜

时间复杂度为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+jj)

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;