数据结构 | 每日一练（93）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1. 当过程 P 递归调用自身时，过程 P 内部定义的局部变量在 P 的 2 次调用期间是否占用同一数据区？为什么？

2. 试推导出当总盘数为 n 的 Hanoi 塔的移动次数。

正确答案

PS：||代表注释

1、过程p递归调用自身时，过程p由内部定义的局部变量在p的2次调用期间，不占同一数据区。每次调用都保留其数据区，这是递归定义所决定，用“递归工作栈”来实现。

2、设H n 为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z，可借助钢针Y)

则 H n =2H n-1 +1 //先将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z

=2（2H n-2 +1）+1

=2 2 H n-2 +2+1

=2 2 （2H n-3 +1）+2+1

=2 3 H n-3 +2 2 +2+1

......

= 2 k H n-k +2 k-1 +2 k-2 +…+2 1 +2 0

=2 n-1 H 1 +2 n-2 +2 n-3 +…+2 1 +2 0

因为H 1 =1，所以原式H n =2 n-1 +2 n-2 +…+2 1 +2 0 =2 n -1

故总盘数为n的Hanoi塔的移动次数是2 n -1。

-end-