算法设计与分析课后答案田翠华着

参考答案

第1章

一、选择题

1.C2,A3.C4.CADB5.B6.B

7.D8,B9.B10.Bll.D12.B

二、填空题

1.输入；输出；确定性；可行性；有穷性

2.程序；有穷性

3.算法复杂度

4.时间复杂度；空间复杂度

5.正确性；简明性；高效性；最优性

6.精确算法；启发式算法

7.复杂性尽可能低的算法；其中复杂性最低者

8.最好性态；最坏性态；平均性态

9.基本运算

10.原地工作

三、简答题

1.高级程序设计语言的主要好处是：

（1）高级语言更接近算法语言，易学、易掌握，一般工程技

术人员只需要几周时间的培训就可以胜任程序员的工作;

(2)高级语言为程序员提供了结构化程序设计的环境和工

具，使得设计出来的程序可读性好，可维护性强，可靠性高；

(3)高级语言不依赖于机器语言，与具体的计算机硬件关系

不大，因而所写出来的程序可移植性好、重用率高；

(4)把复杂琐碎的事务交给编译程序，所以自动化程度高，

发用周期短，程序员可以集中集中时间和精力从事更重要的创造

性劳动，提高程序质量。

2.使用抽象数据类型带给算法设计的好处主要有：

(1)算法顶层设计与底层实现分离，使得在进行顶层设计时

不考虑它所用到的数据，运算表示和实现；反过来，在表示数据

和实现底层运算时，只要定义清楚抽象数据类型而不必考虑在什

么场合引用它。这样做使算法设计的复杂性降低了，条理性增强

了，既有助于迅速开发出程序原型，又使开发过程少出差错，程

序可靠性高。

(2)算法设计与数据结构设计隔开，允许数据结构自由选择,

从中比较，优化算法效率。

(3)数据模型和该模型上的运算统一在抽象数据类型中，反

映它们之间内在的互相依赖和互相制约的关系，便于空间和时间

耗费的折衷，灵活地满足用户要求。

(4)由于顶层设计和底层实现局部化，在设计中出现的差错

也是局部的，因而容易查找也容易纠正，在设计中常常要做的增、

删、改也都是局部的，因而也都容易进行。因此，用抽象数据类

型表述的算法具有很好的可维护性。

(5)算法自然呈现模块化，抽象数据类型的表示和实现可以

封装，便于移植和重用。

(6)为自顶向下逐步求精和模块化提供有效途径和工具。

(7)算法结构清晰，层次分明，便于算法正确的证明和复杂

性的分析。

3.算法的复杂度是算法运行所需要的计算机资源的量。

4.当问题的规模递增时，将复杂度的极限称为渐进复杂度。

5.采用复杂性渐近性态替代算法复杂度，使得在数量级上

估计一个算法的执行时间成为可能。

四、计算题

1.验证下面的关系：

0(1)<0(log77)<0(Z?)<0(Z?log77)<0(z?2)

及0(2。)<0(〃!)<0(4)。

证明1：数学归纳法。

证明2：反证法。

证明3：定义证明

令f,(77)=0(1),五(〃)=0(logz?),£(〃)=0(n),工(〃)=

0(7?10g7?),£(〃)=05)。

根据"(力I=|0(g(〃))I定义，可知一定存在两个正的常数C

和马，使得对所有的gA)，有A77)<cg(〃)o

那么，就有£(〃)WC,工(〃)WGlog/7,f£n)WCsn,

f.\(n)WGniogn,f5(z?)C5n0

所以，O(g(M)之间的比较可以通过HA)之间的比较得以实

现。

而当〃o时，G<Glogz?<Qn<CAz?logz?<C5成立。

再根据。(g(M)表示所有/'(M增长的阶不超过g(M的

函数的集合，它用以表达一个算法运行时间的上界。

则△(〃)的上界<£(〃)的上界〈右5)的上界<工(血的上界〈

£(〃)的上界

那么就验证了

0(1)<0(log77)<0(2?)<0(nlogT?)<0(772)O

同理，有：0(2")<0(「!)<0(4)。

证明4：极限法(通常使用罗比塔法则)。

"1而->8。6/。(1。8〃)=0,所以，。⑴vO(k)g〃).

limO(log刀)/0(刀)=limC,logn/C/i=C.ZClim(Ioge/n)/l=0,所以，O(logn)<0(〃)。

n->a>n->oo2L2〃->oo

limO(〃)/O(〃log〃)=lim〃/(〃log〃)=0,所以，。(〃)vO(〃log〃)。

“一>oo«—>t»

limO(nlogn)/0(n2)=lim(nlogn)/(w2)=lim(logn)/n=0,所以，O(nlogn)<0(1)。

所以，有：0(1)<O(logn)<0(n)<O(/ilogn)<0(n2)o

nn

同理,可证：O(2)<O(n!)<O(n)o

2.找出下述证明中的错误：因为〃=0(〃)，2n=0(/?),…,

故：

〃Il

Z5=Z°(〃)=0(〃)〃=0(/)

氏=|^=1

解答：概念不清。

n-0(/?),2/7=0(z?),…,是集合，是说〃，2n,…，的阶是

n,不是数值上相等。

力如是数值求和，即首项为〃的〃项等差为〃的数列求和

*=1

所以，$>*之。5)。应该是

*=lA=l

“

牛-

17?+277+3Z?+•+nn=Z?(TT+1)n/2,而

”

小O(w)+O(7i)++0(〃)

〃个

=0(max(1,2,3,4，…，n))//根据性质0(f)十0(g)

=0(max(f,g))

=0(/7)〃集合操作，上界的并取最大者

3.求以下各式的渐进表达式：

2n

5/?+8n,3n~/11+3",56+3/n,logn,6log4o

解答：

2

54+8n=0(/7);1

34/11+3"=0(3");

56+3/〃=0(1)//0(1)表示常数；

logz?"=0(log/?);

6log4"=0(7?)o

4.按照渐进阶从低到高的顺序排列下列表达式：

n,log/?,3”,45n,6,3n2,〃!。

解答：

2

log??,45n,3n,5rT,3",n\0

5.确定关系：对于下列各组函数f(n)和gin),确定f

(7?)=0(g(n))或广(〃)=Q(g(〃))或/'(〃)=0(g(〃))，

并简述理由。

(1)f(〃)=logIT,g(7?)=log〃+7;

(2)f(72)=logn,g(7?)=小；

(3)f(77)=n,g(7?)=log2n；

(4)f(z?)=nlogn+n,g(z?)=logz?；

(5)f(z?)=11,g(z?)=og11；

(6)f(72)=log'n,g(/?)=log72;

(7)f(z?)=2",g(72)=100if-,

(8)f(A)=2",g(77)=3flo

解答：

(1)f(n)=log//=。(log〃+7)=0(g(〃))；

(2)f(n)=logn=0(小)=0(g(n))；

(3)f(zz)=n=Q(log2z?)=Q(g(n))；

(4)f(n)=nlogn+n=Q(logn)=Q(g(/?))；

(5)f(.ri')=11=0(log11)=0(g(/?))；

(6)f(.ri')=log?n=Q(log7?)=Q(g(〃))；

(7)f(/7)=2"=。(100n)=Q(g(〃))；

(8)f(n)=2"=0(3")=0(g(加)。

6.证明：〃！=0(")o

证明：

n\«(2^/z)1~(k/e)"(1+0(1/〃))

=lim(2乃〃)'~(1+0(1/〃))/〃"=0

/.n\=。(〃")

7.证明：如果一个算法在平均情况下的计算时间复杂度是。

(f(n)),则该算法在最坏情况下所需的计算时间是。(f(n))o

证明：

4(N)=ZP(I)T(NJ)<ZP(/)甲axTXM/'QTXM/')gP(/)

IWDNIWDN1EDFT/£%

=T(N，m)

r、”x⑻=。亿£"))=Q(。(/(")))=。(/("))

8.硬件厂商XYZ公司宣称他们最新研制的微处理器运行速

度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分

别为〃，n2,r和加的各算法，若用ABC公司的计算机在1小时

内能解输入规模为〃的问题，那么用XYZ公司的计算机在1小时内

分别能解输入规模为多大的问题？

解答：

n=100/2；

n2=100z?2,n=10z?;

n3=100z?3,n=10V3Z?=4.64Z?;

n!=100z?!,/.n<z?+logl00=z7+6.64O

9.

(1)假设某算法在输入规模为免时的计算时间为7(加=3

X2"。在某台计算机上实现并完成该算法的时间为1秒。现有另一

台计算机，其运行速度为第一台的64倍，那么在这台新机器上用

同一算法在1秒内能解输入规模为多大的问题？

(2)若上述算法的计算时间改进为7(加=4,其他条件不

变，则在新机器上用力秒时间能解输入规模为多大的问题？

(3)若上述算法的计算时间进一步改进为T(加=8,其他

条件不变，那么我们在新机器上用方秒时间能解输入规模为多大

的问题？

解答：

(1)设新机器用同一算法在t秒内能解输入规模为n'的问

题，则有

7(A)=3X2"=3X2"'/64,得〃'=TT+6；

(2)n2=64T72,得=872；

(3)由于7(加=8为常数，因此算法可以为解任意规模的

问题。

五、上机题

二分检索是指在一个已经排序的数组中查找一个指定的数据

是否存在的问题。进一步说，假定一个具有"个元素的整型数组a

和一个整数x,数组a的元素已经按由小到大的顺序排序，希望查

找x在数组a中是否出现。若出现，输出对应的数组元素下标，

否则，输出不存在信息。

编程时具体的实现方法是：将x与a的中间元素a\_N/2]比

较，如果相等则结束。否则，若x〈a[AV2],由于a是有序的，

可以肯定x只可能出现在前半个数组中；若x>a[AV2],则x

只可能出现在后半个数组中。然后，将得到的半个数组看成原来

的数组，继续重复上述过程直到数组的所有元素比较完毕或发现

一个相等的元素为止。

在进行程序设计时，％是数组大小的上限，实际的元素个数由

键盘输人。

#include<stdio.h>.

ttdefneN50

intbsearch(int*a,intn,intx)〃参数为数组、元素

个数和被查找的值

{intk=0,m=n-l,mid;//k,m,mid为被查找区间的最小、

最大和中间元素下标

while(k<=m)〃若最小下标超过最大下标则终止循

环，说明不存在

{mid=(k+m)/2;〃取中间下标，注意整数相除取整

if(x==a[mid];

returnmid;〃相等时绮束，返回元求下标

else

if(x<a[mid])

m=mid-1;//x应在前半个数组中，最大下标凋

整

else

k=mid+1;//x应在后半个数组中，最小下标调

整

)

return-1;〃执行此语句时，必有k>m,即x不存在，

返回-1作标志

}

voidmain()

{inta[N],x,n,rt,k;

printf("inputcount(<=50):");//输人数组元素

个数

scanf("%d",&n);

printf(u'Inputal1elermnts:'');

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

scanf(“肌!”，&a[k]);〃输人数组元素，元素可

用空格分隔

printf("inputdatasearchedv;

scanf("%d",&x);〃输人被查找的值x

rt=bsearch(a,n,x);〃执行查找

(rt==-l)?printf("\nNot

found."):printf("\nFound:%d.”,rt);}〃显示查找结果

第2章

一、选择题

1.C2.C

二、填空题

1.递推法；生成函数法；特征方程法；数学归纳法；不规

则法

2.递归消除有利于提高算法的时空性能；研究递归消除有

利于透彻理解递归机制

三、简答题

1.人们在解决一些复杂问题时，为了降低问题的复杂程度

(如问题的规模等)，一般总是将问题逐层分解，最后归结为一些

最简单的问题。这种将问题逐层分解的过程，实际上并没有对问

题进行求解，而只是在解决了最后那些最简单的问题后，再沿着

原来分解的逆过程逐步进行综合，这就是递归的基本思想。

2.假定所求解递归方程的解(系列)是某个函数(如G(x))

展开成无穷级数后的系数，于是，可以先利用递归方程求出G(x)

的解析表达式，然后，再将G(x)展成无穷级数，其4项的系数

自然就是递归方程的通解形式。

四、计算题

1.求和：

⑴t<a

i=l

(2)y,,.'

乙Cn

i-i

解答：

(1)设和为s,则有

S=a+2a2+3/+•••+〃/①

等式两边同乘a,得

aS=a2+2a+,''+na"，｝②

①-②得：

(1-a)S=a+a2+a+'^+a1-na'y

整理得：

S-a(l-a")/(1-a)--na^/(1-a)

(2)设和为S,则有

当〃为偶数时，

S=C：+2c：+3C；++n/2c"2+(”/2+l)C；/2+,++(n-2)Cf2+(H-1)C；-1+nC；,

；；；/2；

=nC'n+nC+++“Cl"+n/2C+nC

=〃/2(C：+d+C；++C；/2+C；/2t,++C：-2+C：；-'+C；；)+n/2C：；

=n/2(2"-l)+n/2

=iilnX

当〃为奇数时，

S=C：+2C；+3C；++(«-l)/2cz"2+5+1)/Ze：""?++(n_2)C；2+(n_1)C；I+nC：

=，C+〃C；+〃c；++y+〃c：

="(C：+C：+C；++C：-W)+"C：2.

=n12(C：+C：+C；++a”"2+C；*i"2++(n-2)C；-2+("-1)C；'+C；)+"/2C；

=n/2(2"-l)+n/2

=〃2”T

设勿，〃都是整数，计算

(1)|_(〃+而/2」+[_(zr研1)/2」

(2)「(〃+勿)/2]+「(zr■研1)/2~|

解答：

(1)因为勿，〃都是整数，所以〃+勿与止勿同时为奇数或偶数。

当〃+勿与77-勿同时为奇数时，原式=(〃+zzrl)/2+(zr研1)/2=

n

当〃+勿与/?-勿同时为偶数时，原式=(〃+%)/2+(27-%)/2=n

(2)同理，",〃都是整数，所以〃+勿与〃-勿同时为奇数或偶

数。

当〃+勿与77-勿同时为奇数时，原式=(〃+研1)/2+(77-/ZT+-1)/2=

〃+1

当〃+勿与n-m同时为偶数时，原式=(77+勿)/2+(n~瑶]2+1=〃+1

3.判断下述等式的真伪：

(I)(Lx」)s=Lx1/2J

(2)「(「一)”21=「/2]

(3)r(Lx」)"21=「一1

解答：(i)当户此k为整数时，原等式成立。

当k为整数时，原等式不成立。此时左端不一定为整数，

而右端为整数。

(2)等式成立。

(3)当尸长k为整数时，原等式成立。

当xW*,A为整数时，原等式不成立。此时，(Lx」)"2<「x

1匕所以左端小于右端。

4.求证：

(1)l_x」+l_y」Wx+y

(2)「x]+「yl2「x+y〕

(3)「log(z?+l)~|=Llogz?J+1

(4)L(x+ni)/n\=L(LxJ+力)/〃」

⑸力?/2」=L〃74

k=\

证明：

(1)当X,y为整数时，原等式成立。

当x,y不为整数时，令x=|_x」+Ax,y=LyJ+Ay,其

中0<Ax,AyWlo则有

x+y=|_x」+Ax+|_y」+Ay=L.x」+L,y」+Ax+A

y

因为0<Ax,Ay<1,所以0<Nx+ky<2

贝l」l_x」+Ly」+Ax+Ay〉Lx」+Ly」，即有：x+y

>L^J+LyJ

所以，原不等式Lx」+Ly」Wx+y成立。

(2)当x,y为整数时，原不等式成立。

当x,y不为整数时，令x=「x]—Ax,y=「y]—Ay,其

中0<Ax,Ay<1。则有：

「x+yl=「「x]-Ax+「y]-Ay[=「「x[+「y]—(A

x+Ay)1

因为0WAx,Ay<1,所以有0WNx+Ny<2。因此，

「x+y1W「「xl+「y]]=「xl+「4

所以，原不等式「4+「yl2「x+y]成立。

(3)当〃为2"时，「log(〃+l)]=A+1,而LlogzzJ+1=A+1,

所以，原等式成立。

当〃不为2"时，则次此处A=|_log〃」，那么2"+1"

+1W2,则有：

riog(?2+l)l=A+1,Llogz?J+1=k+\,所以，原等式成立。

(4)若要使原等式成立，必有

而“(8+间/〃-(|_》」+，”)/“=0,这里x=l_x」+Ax,0WAx<1

左端=litn|(|_A*J+|^B^|t^pJ+/nyn|=limx/n=0=右端

所以，原等式成立。

(5)当周2研1时，炉0,1,2,3,…，那么

左端=0+1+1+2+2+3+3+…+研犷2*(1+))m/2-m{\+in)

右端=L(2〃汁1尸/4」=|_(4/+4研1)/4」=/(1+勿)=左端

所以，原等式成立。

当〃=2/时，炉0,1,2,3,…，那么

左端=0+1+1+2+2+3+3+…+(/zrl)+(/zrl)+/»

2*(l+zzrl)(zzrl)/2+/=m

右端=l_(2勿)2/4」-m-/=左端

所以，原等式成立。

5.设x,y为任意实数，定义：

{xmody-x-y\_x/yJ,当yW0

xmod0=x

依据上述定义：

(1)若尸T,计算xmod28o

(2)若xmod3=2,xmod5=3,求xmod15。

解答：

(1)当尸T时，mod28=(-l)mod28=(-1)-28L(T)/28」

=-1-28*(-1)「1/28~|=27

(2)

①当xmod3=2,xmod5=3,那么有命题xmod(2zrl)=z?

成立，此时x>0。

用数学归纳法证明命题：当炉2时，有xmod3=2,成立。

当72=3时，有xmod5=3,成立。

假设当n-A时，有Amod(2A-1)=k

成立，

然后证明当行A+1成立。所以，命题成立。

即有：xmod(2(A+1)-1)=A+1。

根据命题Amod(2T?-1)=n,有在Amod(2zrl)=Amodl5中，

2/7-1=15,则77=8o

所以，Amodl5=8o

②

xmod3=2,xmod5=3,此时x>0,否则不满足定义

，存在整数左，kz,使得：x=3左+2,同时，x=5^+3,

即有：3左+2=54+3,得左=(5左+1)/3=5(左T)

/3+2

•••左，人为整数存在整数衣，使得：k=(左T)/3,即

有：左=3A+1

...x=5L+3=5(34+l)+3=15A+8

jrmodl5=8o

6.求序列2,5,13,35,…2"+3"的生成函数。

解答：根据题义，得

{〃（0）=2,72=0

H（n）=2n+3n,n=l,2,3,…

设生成函数为G（X）=£“（〃）X”，将〃（〃）=2〃+3"代入，得

n=O

G（x）=£（2"+3"卜"，

n-O

将上式展开并整理，得

G(x)=[2-5才+(2n+2+3n)Z*+(3*2a+2*3"|)xF/[(1-2^)(1-3^)]

7.给定a0=l,l31=1,a*2=a〃+i+6a0,试求出a〃的非递归形式的表

达式。

解答：原方程所对应的特征方程为:

a2-a-6=0

为齐次方程，则齐次解：S=3,3=-2,重数均为1。

记通解的形式为：3=4s"+氏72"=43"+B（-2）n

将ao=l,ai=l代入上式，得

A+B=l

34-2炉1

解得：4=3/5,分2/5

从而，得当的非递归形式的表达式为：4=(3日+(-2).)/5。

8.设有ao=O,ai=l,a2=-l和a„=-an-i+16a„-2-20a^,当n

23。求出a”的表达式。

解答：原递归方程所对应的特征方程为：

/+/-16^20=0

解得特征方程的根：6=-5,0=2,重数分别为1和2。

nn

记通解的形式为：a尸(A+Bn)qx+Cq/=(A+Bn)*2+6*(-5)"

将ao=0,a}=1,&=T代入上式，得

"A+C=0

Y

2(4+而-5C=1

4(4+26)+(-5y--1

解得：4=5/49,炉1/7,^-5/49

从而，得名的非递归形式的表达式为：a尸(5/49W7)*2"

+(-5严/49。

9.设为=1,4=5,a尸ag+6a",当〃22。求出的解析表达

解答：原递推方程的特征方程为

*-『6=0,则齐次特征方程为

齐次特征的解为：6=3,桃=-2,重数均为1。

记通解的形式为：4=力6"+方Q2”=43"+6(-2)n

将a()=l,ai=5代入上式，得

{4+B=l

3A-2B=5

解得：4=7/5,企-2/5

n0+1

记通解的形式为：an=Aq：+Bq2=(7*3"+(-2))/5

10.求解方程：

{T(2)=1,n=l

7(〃)="〃丁(4/2)+〃，〃>2,且有片使得机2?”

解答：由递归方程，递推得

75)=/7,/2T(771/2)+n

=J2[(J2)"27(5")/2)+J2]+A

=n/2nI/4T(Z?I/1)+n+n

=/2，/2/71/4[(/7l/4)1/2A(/7，/4)1/2)W/，]+2/7

=nV4口i/«T(/)+3〃

令％2九则有

,QBG&J付）彷）r（丹3"

=22*'>2-^；(22-)+4„

=22"+*+22逐“++2：(2)+及

=22'+^

7(/7)=/2(l/2+log(log/7))

11.求证方程

x(l)=1,n=1

r-1

的解是x(n+l)=CZ/(n+l)

证明：根据递归方程，递推得

x⑵=x(l)x(1)=1=8/2

x(3)=x(l)x(2)+x(2)x(1)=1+1=2=C\/3

x(4)=x(1)x(3)+x(2)x(2)+x(3)x(l)=5=

x(5)=x(l)x(4)+x(2)x(3)+x(3)x(2)+

x⑷x⑴=14=C%/5

X(〃)=C''2(片l)/〃

X(》1)=仁2〃/(加1)

12.求证递归方程

{7(1)=0

7(/7)=T(Ln/2\)+T(「〃/21)+〃-1,A>1

的解是=A「log/21-2riogn1+lo

证明：

(1)当炉2时，由递归方程和初值，推得

T(2)=7(1)+7(1)+2-1=0+0+2-1=1

由方程的解，得T(2)=2-2+1=1。所以，结论成立。

(2)假设当时成立，既有7(m=在「logA]-2M+1

是原递归方程的解。

那么当〃=A+1时，下面证明7U+1)=(A+l)「log(4+l)]-2r

1。晨是原递归方程的解。

当〃WA时，7(14/2」)+T(「k/2\)+hl=k「log£|-2「侬八

+1

当〃=4+1且女为奇数时，有

7([_(女+1)/2」)+7(「(々+1)/21)+A+1-1

=7(|_4/2」+1)+7(「女/2])+k

=27(「4/21)+4

=2[\k/2\•Flog「4/211-2「皿「"211+i]+攵

=(4+1)•「log「4/211-2「侬「SU"+2+左

riog(k+1)/2+10g21

=(A+1)(Flog(A+l)/2+11)-2+1

=(A+1)「log(A+l)-1+11-2riog(k+1)1+1

=(々+1)「log(A+l)1-2riog(k+1)1+1

=T(A+1)

当77=々+1且4为偶数时，有

7(1_01)/2」)+7(「(4+1)/2])+A+1-1

=7(4/2)+7U/2+1)+k

=(V2)riog(V2)l-2riog(k/2)1+1+[(A/2+1)「logJ/2+1)1

-2riog(k/2+l)1+1]+k

=(4/2+A/2+l)Flog(V2)l-(2「0(k/2)1+2「io，(k/2+Dl)+2+k

=(々+1)Flog(V2)l-2r，og(k/2)1+1+2+k

=T(A+1)

即当n-k+\时，命题成立。

所以，原命题成立。

五、上机题

1.计算Hermite多项式

Voidmain()

(

Printf(“\n%f”,H(2,2.0));〃输出结果76.000000

)

DobuleH(intn,floatx)

Switch(n)

Case0:return1;

Case1:2*x;

)

Return2*x*H(n-1,x)-2*(nT)*H(n-2,x)

)

2.求解汉诺塔问题

汉诺塔问题：设4B、。是三根金针。开始时，在金针4上

有〃只纸盘，这些纸盘自下而上，由大到小地叠放一起，各纸盘

从小到大编号为1,2,…，n,如图A-1所示。现要求将金针A

上的这一叠纸盘移到金针夕上，并仍按同样顺序叠置。

图AT汉诺塔问题的初始状态

在移动纸盘时应遵守以下移动规则：

规则(1)：每次只能移动一个纸盘；

规则(2)：任何时刻都不允许将较大的纸盘压在较小的纸盘

之上；

规则(3)：在满足移动规则(1)和(2)的前提下，可将纸

盘移至小B,。中任一根金针上。

分析与解答：

(1)汉诺塔问题的递归算法如下:

publicstaticvoidHanoi(intn,intA,intB,intC)

if(n>0){

Hanoi(n-1,A,C,B)'

Move(n,A,B);

Hanoi(n-1,C,B,A);

}

}

(2)汉诺塔问题的非递归算法。

教材中所述非递归算法的目的塔座不确定。当n为奇数时，

目的塔座是B,按顺时针方向移动；而当n为偶数时，目的塔座为

C,按反时针方向移动。为确定起见，规定目的塔座为B。汉诺塔

问题的非递归算法可描述如下：

publicstaticvoidHanoi(intn)

(

int[]top={0,0,0}

int口口tower=newint[n+1][3];

intx,y,min=0;

Booleanb,bb;

for(inti=0;i〈=n;i++)

{tower[i][0]=n-i+l;tower[i][1]=n+l;

tower[i][2]=n+l;}

top[0]=n;b=odd(n);bb=true;;

while(top[l]<n){

if(bb){

x=min;

if(b)y=(x+l)%3

elsey=(x+2)%3;

min=y;bb=false;

else{

if(tower[top[x]][x]>tower[top[y]]|y])

{inttmp=x;x=y;y_tmp;}

move(tower[top[x]][x],x+1,y+1);

tower[top[y]+1][y]=tower[top[x]][x]

top[x]—;top[y]++;

下面用数学归纳法证明递归算法和非递归算法产生相同的移

动序列。

当〃=1和〃=2时容易直接验证。设当kWn~\时，递归算

法和非递归算法产生完全相同的移动序列。考察的情形。

将移动分为顺时针移动(C)、逆时针移动(CC)和非最小圆

盘塔座间的移动(0)。

当〃为奇数时，顺时针非递归算法产生的移动序列为：C,0,

C,0,C；逆时针非递归算法产生的移动序列为：CC,0,CC,

0,…，CCo

当n为偶数时，顺时针非递归算法产生的移动序列为：CC,0,

CC,0,…，CC；逆时针非递归算法产生的移动序列为：C,0,C,

0,…，Co

①当n为奇数时，顺时针递归算法Hanoi(n,A,B,C)产

生的移动序列为：

Hanoi(n-1,A,C,B)产生的移动序列，0,Hanoi(n-1,

C,B,A)产生的移动序列。

Hanoi(n—1,A,C,B)和Hanoi(n-1,C,B,A)均为偶

数圆盘逆时针移动问题。由数学归纳法知，产生的移动序列均为:

C,0,C,0,…，Co因此，Hanoi(n,A,B,C)产生的移动序

列为：C,0,C,0,­•,Co

②当n为偶数时，顺时针递归算法Hanoi(n,A,B,C)产

生的移动序列为：

Hanoi(n-1,A,C,B)产生的移动序列，0,Hanoi(n-1,

C,B,A)产生的移动序列。

Hanoi(〃一1,A,C,B)和Hanoi(n-l,C,B,A)均为奇

数圆盘逆时针移动问题。由数学归纳法知，产生的移动序列均为:

CC,0,CC,0,…，CCo因此，Hanoi(〃，A,B,C)产生的移动

一序列为:CC,0,CC,0,…，CCo

当n为奇数和偶数时的逆时针递归算法也类似。

由数学归纳法即知，递归算法和非递归算法产生相同的移动

序列。

(3)双色汉诺塔问题：设4、B、。是三根金针。开始时，在

金针4上有〃只纸盘，这些纸盘自下而上，由大到小地叠放一起,

各纸盘从小到大编号为1,2,n,奇数编号圆盘为白色，偶数

编号圆盘为黑色。如图A-2所示。现要求将金针4上的这一叠纸

盘移到金针夕上，并仍按同样顺序叠置。

图A-2双色汉诺塔问题的初始状态

在移动纸盘时应遵守以下移动规则：

规则（1）：每次只能移动一个纸盘；

规则（2）：任何时刻都不允许将较大的纸盘压在较小的纸盘

之上；

规则（3）：任何时刻都不允许将同色圆盘叠在一起；

规则（4）：在满足移动规则（1）和（3）的前提下，可将纸

盘移至4,B,。中任一根金针上。

试设计一个算法，用最少的移动次数将塔座4上的〃个圆盘

移到塔座夕上，并仍按同样顺序叠置。

分析与解答：

可用教材中的标准Hanoi塔算法。问题是要证明标准Hanoi

塔算法不违反规则（3）。

用数学归纳法。

设Hanoi(〃，A,B,。)将塔座A上的n个圆盘，以塔座C

为辅助塔座，移到目的塔座方上的标准Hanoi塔算法。

归纳假设：当圆盘个数小于〃时，Hanoi(z?,A,B,C)不违

反规则(3),且在移动过程中，目的塔座B上最底圆盘的编号与n

具有相同奇偶性，辅助塔座C上最底圆盘的编号与n具有不同奇

偶性。

当圆盘个数为n时，标准Hanoi塔算法Hanoi(〃，A,B,C)

由以下3个步骤完成。

①Hanoi(n—1,A,C,B)；

②Move(4B)；

③HanoiC,B,A)O

按归纳假设，步骤①不违反规则(3),且在移动过程中，塔

座C上最底圆盘的编号与n-\具有相同奇偶性，塔座夕上最底圆

盘的编号与n-1具有不同奇偶性，从而塔座夕上最底圆盘的编号

与〃具有相同奇偶性，塔座C上最底圆盘的编号与n具有不同奇

偶性。

步骤②也不违反规则(3),且塔座B上最底圆盘的编号与n

相同。

按归纳假设，步骤③不违反规则(3),且在移动过程中，塔

座夕上倒数第2个圆盘的编号与n-1具有相同奇偶性，塔座A上

最底圆盘的编号与n-l具有不同奇偶性，从而塔座夕上倒数第2

个圆盘的编号与〃具有不同奇偶性，塔座A上最底圆盘的编号与n

具有相同奇偶性。

因此在移动过程中，塔座夕上圆盘不违反规则(3),而且塔

座8上最底圆盘的编号与〃具有相同奇偶性，塔座。上最底圆盘

的编号与n具有不同奇偶性。

由数学归纳法即知，Hanoi(〃，A,B,C)不违反规则(3)。

第3章

一、选择题

1.B2.B

二、填空题

1.LlognJ+1

2.2n-l

三、简答题

1.将一个难以直接解决的大问题，分割成一些规模较小的

类型相同问题，这些子问题相互独立，以便各个击破，分而治之。

如果原问题可分割成勿个子问题，\＜辰小并且这些子问题都可

解，然后求解这些问题，那么就可利用这些子问题的解求出原问

题的解；如果子问题还比较复杂而不能直接求解，还可以继续细

分，直到子问题足够小，能够直接求解为止。此外，为了得到原

始问题的解，必须找到一种途径能够将各个子问题的解组合成原

始问题的一个完整答案。

2.将待查的数据与非降序数组中的中间元素进行比较，若

二者相等则表示查到；若该数据小于中间元素的值，则下次在数

组的前半部分中继续找；否则，在数组的后半部分中查找。即每

次检索将与待查数据的比较次数减半。如此继续进行下去，直到

查到该值的元素或不存在所查找的数据。此种分治方法，称为二

分检索。

四、计算题

1.作一个“二分”检索算法，它将原集合分成1/3和2/3

大小的两个子集。分析此算法并与算法3.1比较。

输入：已按非减序分类的〃个元素的数组4和％才是被检索

的项。40]未用。

输出：若乃在[中，输出下标j满足加刃=片，否则输出0。

IntBinarySearch(A,n,X)

{intk=l;m=n;

while(k<=m)

{j=(k+m)/3;/*j=l(k+m)/3j*/

if(X==A[j])

returnj;

if(X<A[jJ)

m=j-1

else

k=j+1;

return0；

}

时间分析:比较次数7(〃)上…/2T(2/3)/2

2.作一个“三分”检索算法，它首先检查1/3处的元素是

否与X相等，然后检查2/3处的元素，等等。这样，或者找到X,

或者将集合缩小到原来的1/3O试写出此算法并分析其复杂性。

输入：已安排减序分类的〃个元素的数组4和％才是被检索

的项。爪0]未用。

输出：若X在A中，输出下标j满足A[j]=X,否则输出0。

IntThirdSearch(A,n,X)

{intk=1;m=n;

While(k<=m)

{i=(k+m)/3;/*i=L(k+m)/3」*/

if(X==A[i])

returni;

if(X<A[iD

m=i-1

else

{j=2(k+m)/3)/;/*j=[2(k+m)/3)j

*/

if(X==A[j])

returnj;

if(X<A[j])

{k=i+1;

m=j-1}

else

k=j+1;

return0；

}

时间分析：比较次数7(止,一…:二，,

']l/3*(l+T(〃/3))+2/3(2+7'(〃/3))=5/3+7'(〃/3)n>\

解得方程：T(n)=l+log3n

3.设计一个在有n个元素的集合中通过比较找出最大和次

最大元素的算法，使其复杂度为n+ilognj-2。

算法：找最大和次大元素

输入：有n个元素的数组A

输出：最大和次最大元素Max和SubMax。

voidFind(A)〃递归算法

{if(|A|==2)

{设A={a,b}

(Max,SubMax)(Max(a,b),SubMax(a,b));

}

else

{把A分成两个子集Al和A2,各有一半元素；

(Maxl^SubMaxl)Find(Al);

(Max2^SubMax2)Find(A2);

SubMax3=Min(Maxi,Max2);

SubMax4=Max(SubMaxi,SubMax2)

(Ma^~SubMax)(Max(Max1,

Max2),SubMax(SubMax3,SubMax4))

)

}

时间分析：T(n)为算法的最坏时间。当n=2时，T(n)=l；当

n>2时，则需要进行两次递归调用及之后的比较。故有：

[1〃=2

r(，1)=[2T(n/2)+4n<2

T(n)=5n/2

4.求解最接近中位数的k个数：给定由n个互不相同的数

组成的集合A以及正整数kWn,设计一个0(n)时间复杂度的查

找A中最接近A的中位数的k个数的算法。在采用分治法进行查

找时，为了满足分治法的平衡原则，需要将数组分成两个大小基

本相同的子数组，其中的那个划分点就是中位数。所以，中位数

是指数组中能将数组划分成两个大小基本相同的两个子数组的那

个元素，即中位数是第Fn/21小的数。

解析：

(1)找出A中的中位数mid；

(2)计算T={|a-mid|,aeA}；

(3)找出T的第k小元素b；

(4)根据b找出所要的解{|a-mid|^b,aeA}。

由于在最坏情况想选择的时间复杂度为0(n)o所以，(1)和

(3)需要0(n)次计算，(2)和(4)也只需要。(n)次计算。

因此，本算法在最坏情况下，时间复杂度为0(n)。

例如，A={50,13,80,30,6,27,35},k=3,求最接

近中位数的k个数。

(1)找出A中的中位数mid：将A排序=[6,13,27,30,

35,50,80},mid=30o

(2)计算T={|a-mid|,awA}：T={20,13,50,0,24,

3,5}o

(3)找出T的第k小元素b：T的第k小元素b=5o

(4)根据b找出所要的解{a,|a-mid|Wb,aeA}：{30,

27,35}o

5.求有序数组A和B的中位数

设A[0：n-1]和B[0：n-1]为两个数组，每个数组中含有

n个已排好序的数。设计一个0(logn)时间复杂度的算法，找出A

和B的2n个数的中位数mediano

解析：

(1)算法设计思想。

考虑问题的一般性：设A[il：jl]和B[i2：j2]是A和B

的排序好的子数组，且长度同，即j『il=i2-j2。找出这两个子

数组中2(jbil+l)个数的中位数。

首先注意到，若A[il]WB[j2],则中位数median满足A

[il]WmedianWB[j2]o同理，若A[il]2B[j2],则B[j2]

WmedianWA[il]。

设ml=(il+jl)/2,m2=(i2+j2)/2,则

ml十m2=((il+jl)/2+(i2十j2)/2

=il+(jl—il)/2+i2+(j2—i2)/2

=il+i2+(jl—i1)/2+(j2—⑵/2。

由于jl—il=j2—i2,故

(jl-il)/2+(j2—i2)/2=jl—il=j2—i2。

因此，ml+m2=il+i2+jl-i1=i2+jl=i1+i2+j2—

i2=il+j20

当A[ml]=B[m2]时，median=A[ml]=B[m2]。

当A[ml]<B[m2]时，设medianl是A[ml：jl]和B[j2：

m2]的中位数，则median=Medianl。

当A[ml]>B[m2]时，设median2是A[il：ml]和B[i2：

j2]的中位数，类似地有median=median2o

通过以上的讨论，可以设计出查找两个子数组A和

B[i2:J2]的中位数median的算法。

(2)算法复杂性。

设在最坏情况下，算法所需的计算时间为T(2n)。由算法中

ml和m2的选取策略可知，在递归调用时，数组A和B的大小都减

少了一半。因此，T(2n)满足递归式：

7(2〃)=[°⑴，1<C

\T(n)+0(1)”2c

解此速归方程可得：T(2n)=0(logn)o

比如A={12,34,56,62,78,81,95},B={23,38,45,

67,89,103,120)o求数组A和B中位数。

解析：ml=(il+jl)/2=3,m2=(i2+j2)/2=3。

A[ml]=62,B[m2]=67,则根据

当A[ml]<B[m2]时，设medianl是A[ml：jl]

和B[i2：m2]的中位数，则median=Medianl。

有：

median=A[ml：jl]和B[i2：m2]的中位数

=A[3：6]和B[0：3]的中位数

={62,78,81,95}和{23,38,45,67}的中位数

=62

再比如A={12,34,56,62,78,81,95},B={23,38,45,

60,89,103,120}o求数组A和B中位数。

解析：ml=(il+jl)/2=3,m2=(i2+j2)/2=3。

A[ml]=62,B[m2]=60,则根据

当A[ml]>B[m2]时,设median2是A[i1：ml]

和B[m2：j2]的中位数，类似地有median=median2。

有：

median=A[0：3]和B[3：6]的中位数

=A[3：6]和B[0：3]的中位数

={12,34,56,62}和{60,89,103,120}的中位数

60

6.利用整数相乘算法3-7计算两个二进制数1011和1101及

两个十进制数3141和5327的乘积。

解答：

(1)x=1011,y=1101

Mui(1011,1101,4)//整数相乘算法3.1

A=10,B=ll,C=ll,D=01

ml=Mul(A,C,n/2)=Mul(10,11,2)〃递归调用

-A=l,B=0,C=l,D=1

_ml=Mul(A,C,n/2)=Mul(1,1,2/2)=1〃递归调用并返回

Mul(l,1,2/2)

m2=Mul(A-B,D-C,n/2)=Mul(l,0,2/2)=0

m3=Mul(B,D,n/2)=Mui(0,l,2/2)=0

1*