《计算机常用算法与程序设计案例教程》习题解答 下载本文

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

习题解答提要

习题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)。 试描述以上算法。

解:设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-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

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??100n?1)<250(1?2??n)4n?3<250?n<250nn6

时间复杂度为O(nn)。

1-3 若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-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(\

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(\阶对称方阵为:\\n\ for(i=1;i<=n;i++)

{ for(j=1;j<=n;j++) // 输出对称方阵 printf(\ printf(\ } }

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\}

习题2

2-1 解不等式

设n为正整数,解不等式

2010?1?111?????2011 1?1/21?1/2?1/31?1/2???1/n解:上下限一般为键盘输入的a,b。

// 解不等式: a<1+1/(1+1/2)+...+1/(1+1/2+...+1/n) #include void main()

{ long a,b,c,d,i; double ts,s;

printf(\请输入a,b: \ scanf(\ 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为: %ld≤n≤%ld \\n\}

2-2 韩信点兵

韩信在点兵的时候,为了知道有多少个兵,同时又能保住军事机密,便让士兵排队报数。 按从1至5报数,记下最末一个士兵报的数为1; 再按从1至6报数,记下最末一个士兵报的数为5; 再按1至7报数,记下最末一个报的数为4; 最后按1至11报数,最末一个士兵报的数为10。