我在学习python编程,讲到用递归函数实现汉诺塔的移动

前提:请编写move(n, a, b, c)函数,参数n表第1个柱子A从下到上按金字塔状叠放着的圆盘数量,要把所有盘子一个一个移动到柱子B上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方,请问至少需要多少次移动,设移动次数为H(n),然后打印出把所有盘子从A借助B移动到C的方法。

 

我搜索到了很多解法,已经知道公式了,但是网上的解法过程中有一点不太明白:
H(1) = 1
H(n) = 2*H(n-1)+1 (n>1)
那么我们很快就能得到H(n)的一般式:H(n) = 2^n – 1 (n>0)
 
从结论来讲,我能理解盘子和次数之间的关系是:H(n) = 2^n – 1,但是不能理解网上解法中的【那么我们很快就能得到H(n)的一般式】。
 
从 = 2*H(n-1)+1  (n>1)这个不是文字解释一样的公式吗,怎么就可以变到= 2^n – 1这样一个数学公式了?还是”很快就能得到”?
 
事实上应该是先把 H(1) = 1,H(2) = 3, H(3) =7,H(4) = 15 ….这些先各自计算出结果,然后对比结果的数学规律后,得出 H(n)= 2^n – 1这个结论的吧?
 
还是说从【H(n) = 2 *(n-1)个圆盘重新摞在一起的次数 + 1次】,不靠各自计算出结果后对比结果的数学规律,就可以得出【H(n) = 2^n – 1】?只是我还没有理解到?
 
有一点钻牛角尖,但是很疑惑,所以上来请教一下大家~
 
谢谢!
1 收藏


直接登录
最新评论
  • demoZ   2016/08/29

    H(n)+1=2(H(n-1)+1)

    那么H(n)+1是个等比数列,就可以求通项公式了。

  • 画梦 iOS工程师 2016/08/29

    那应该是数学的范围了。

    • littlel   2016/08/29

      是的,是等比数列。一个数列从第2项起,每一项与它的前一项的比等于同一个常数。

      H(n)+1=2(H(n-1)+1)

      an = 2 an-1

      2 = an/an-1

      所以 H(n)+1 公比是2。

      H(n)+1 = (H(1) + 1) * 2 ^(n-1)   H(1)=1

      H(n)+1 = (1+1)* 2 ^(n-1)

                   = 2*2(n-1)
                   = 2^n
          H(n) = 2^n – 1                            (n>0)

      成功理解~~~~~~~~~谢谢!~~