梵天塔问题
4617
4617
528
18685
14643
汉诺塔玩法如下:
有三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,现在把所有盘子一个一个移动到柱子B上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方
拓展内容:
汉诺塔
一、简介
汉诺塔是由三根杆子A,B,C组成的。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:每次只能移动一个圆盘;大盘不能叠在小盘上面。提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。问:如何移?最少要移动多少次?汉诺塔是根据一个传说形成的一个问题:
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
每次只能移动一个圆盘;
大盘不能叠在小盘上面。
提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。
问:如何移?最少要移动多少次?
二、公式
现在有三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,现在把所有盘子一个一个移动到柱子B上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方,请问至少需要多少次移动,设移动次数为H(n)。
首先我们肯定是把上面n-1个盘子移动到柱子C上,然后把最大的一块放在B上,最后把C上的所有盘子移动到B上,由此我们得出表达式:
H⑴ = 1
H(n) = 2*H(n-1)+1 (n>1)
那么我们很快就能得到H(n)的一般式:
H(n) = 2^n - 1 (n>0)
并且这种方法的确是最少次数的,证明非常简单,可以尝试从2个盘子的移动开始证,你可以试试。
进一步加深问题(解法原创*_*):
假如现在每种大小的盘子都有两个,并且是相邻的,设盘子个数为2n,问:⑴假如不考虑相同大小盘子的上下要多少次移动,设移动次数为J(n);⑵只要保证到最后B上的相同大小盘子顺序与A上时相同,需要多少次移动,设移动次数为K(n)。
⑴中的移动相当于是把前一个问题中的每个盘子多移动一次,也就是:
J(n) = 2*H(n) = 2*(2^n - 1) = 2^(n+1)-2
10623
6627