《算法设计与分析实用教程》习题参考解答

.

《算法设计与分析实用教程》参考解答

1-1 加减得1的数学游戏

西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。

例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。

（1） 若输入两个不同的正整数a,b均为偶数，显然不可能得到1。

设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2） 算法描述

// 两数若干次加减结果为1的数学游戏 #include void main()

{long a,b,d,n,x,y;

printf(\请输入整数a,b: \ scanf(\ if(a%2==0 && b%2==0)

{ printf(\ n=0; while(1) { n++;

for(x=1;x<=n;x++)

{ y=n+1-x;d=x*a-y*b;

if(d==1 || d==-1) // 满足加减结果为1 { printf(\} } }

请输入整数a,b: 2012,19 961

请输入整数a,b: 101,2013 606

.

.

1-2 埃及分数式算法描述

分母为整数分子为“1”的分数称埃及分数，试把真分数a/b分解为若干个分母不为b的埃及分数之和。

（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）。 试描述以上算法。

解：设d?int(b) (这里int(x)表示取正数x的整数)，注意到d?b?d?1，有

aa a?1?a(d?1)?bbd?1b(d?1)

算法描述：令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-3 求解时间复杂度

求出以下程序段所代表算法的时间复杂度。 （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

2

时间复杂度为O(n)。 （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的执行频数为

22

s=1+1+2+2+3+3+…+u=u=n/4

2

时间复杂度为O(n)。 （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(\}

解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环b/2次。因而k循环体的执行次数s满足

s＜25(99?199?L?100n?1)＜250(1?2?L?n)4n?3＜250?n＜250nn6

算法的时间复杂度为O(nn)。

1-4 时间复杂度的一个性质

若p(n)是n的多项式，证明：O(log(p(n)))=O(logn)。

mm-1

证：设m为正整数，p(n)=a1×n+a2×n+…+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-5 统计n!中数字“0”的个数

修改1.3.2计算n!的算法，统计并输出n!中数字“0”的个数及其尾部连续“0”的个数（n<10000）。

解：计算n!完成后，在j（1——m）循环中通过 if(a[j]==0) p++; 统计n!中数字“0”的个数p。

应用q=1; while(a[q]==0) q++;统计尾部连续“0”的个数q-1。 // 统计n!中0的个数及尾部连续0的个数（n<10000）

#include #include void main()

{ int g,j,k,m,n,p,q,t,a[40000];double s; printf(\请输入正整数n(n<10000): \ scanf(\ // 输入n s=0;

for(k=2;k<=n;k++)

s+=log10(k); // 对数累加确定n!的位数m m=(int)s+1;

for(k=1;k<=m;k++)

a[k]=0; // 数组清零 a[1]=1;g=0;

for(k=2;k<=n;k++)

for(j=1;j<=m;j++)

{ t=a[j]*k+g; // 数组累乘并进位 a[j]=t; g=t/10; } p=0;

for(j=m;j>=1;j--) if(a[j]==0) p++; // p统计n!中0的个数 q=1;

while(a[q]==0) q++; // q尾部连续0的个数 printf(\输出结果 } 数据测试：

请输入正整数n(n<10000): 1000 p=472,q=249

.

.

请输入正整数n(n<10000): 2013 p=1032,q=501

1-6 构建斜折对称方阵

图1-4是一个7阶斜折对称方阵，试观察斜折对称方阵的构造特点，总结归纳其构造规律，设计并输出n（奇数）阶斜折对称方阵。

图1-4 7阶斜折对称方阵

（1） 构造规律与赋值要点

对n阶方阵中的每一个元素都必须赋值，但不可能逐行逐列地一个个赋值，有必要分析方阵的构造特点，分块或分片实施。

斜折对称方阵的构造特点：两对角线上均为“0”，依两对角线把方阵分为4个区域，每一区域表现为同数字依附两对角线折叠对称，至上下左右正中元素为n/2。

同样设置2维a[n][n]数组存储方阵中元素，行号为i，列号为j，a[i][j]为第i行第j列元素。

令m=(n+1)/2, 按m把方阵分成的4个小矩形区如图1-5所示。

图1-5 按m分成的4个小矩形

注意到方阵的主对角线（从左上至右下）上元素为：i=j，则左上区与右下区依主对角线赋值：a[i][j]=abs(i-j);

注意到方阵的次对角线（从右上至左下）上元素为：i+j＝n+1，则右上区与左下区依次对角线赋值：a[i][j]=abs(i+j-n-1);

(2) 程序设计 // 斜折对称方阵 #include #include void main()

{int i,j,m,n,a[30][30];

printf(\请确定方阵阶数(奇数)n: \if(n%2==0)

.