解释清楚的加分!!关于汉罗塔的pascal程序

来源:百度知道 编辑:UC知道 时间:2024/06/16 07:11:16
谁可以解释一下关于汉罗塔的pascal程序
是用递归回溯的

求汗诺塔N个盘子须几次移动时得到了下面的递推公式:

a[1] = 1;
a[n] = a[n-1] * 2 + 1;

请教通项公式?

a[1] = 1;
a[n] = a[n-1] * 2 + 1;

可得a[i]= 2^i-1;

证明,采用数学归纳法:
1、猜想a[i]= 2^i-1
2、当i=1时,显然成立。
3、假设i=k时成立,即 a[k] = 2^k - 1;则:
由a[n] = a[n-1] * 2 - 1;得
a[k+1] = a[k] * 2 - 1
= 2^k * 2 - 1
= 2^(k-1) - 1
故得证。

同时::
汉诺塔问题(又称河内塔问题)是根据一个传说形成的一个问题:

有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:

1. 每次只能移动一个圆盘;
2. 大盘不能叠在小盘上面。

提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。

问:如何移?最少要移动多少次?
一般取N=64。这样,最少需移动264-1次。即如果一秒钟能移动一块圆盘,仍将需5845.54亿年。目前按照宇宙大爆炸理论的推测,宇宙的年龄仅为137亿年。

在真实玩具中,一般N=8;这将需移动255次。如果N=10,需移动1023次。如果N=15,需移动32767次;这就是说,如果一个人从3岁到99岁,每天移动一块圆盘,他仅能移动15块。如果N=20,需移动1048575次,即超过了一百万次。
先看hanoi(1, one, two, three)的情况。这时直接将one柱上的一个盘子搬到three柱上。注意,这里one柱或three柱到底是A、B还是C并不重要,要记住的是函数第二个参数代表的柱上的一个盘被搬到第四个参数代表的柱上。为方便,