数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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-