求汗诺塔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并不重要，要记住的是函数第二个参数代表的柱上的一个盘被搬到第四个参数代表的柱上。为方便，将这个动作记为： one =》three 再看hanoi(2, one, two, three)的情况。考虑到hanoi(1)的情况已经分析过了，可知这时实际上将产生三个动作，分别是： one =》two one =》three two =》three 很显然，这实际上相当于将one柱上的两个盘直接搬到three柱上。 再看hanoi(3, one, two, three)的情况。分析 hanoi(2, one , three, two) one =》three hanoi(2, two, one, three) 即：先将one柱上的两个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的两个盘搬到three柱上。这不就等于将one柱上的三个盘直接搬到three柱上吗？ 运用归纳法可知，对任意n， hanoi(n-1, one , three, two) one =》three hanoi(n-1, two, one, three) 就是先将one柱上的n-1个盘搬到two柱上，再将one柱上的一个盘搬到three柱上，最后再将two柱上的n-1个盘搬到three柱上。这就是我们所需要的结果！ 回答者：wuchenghua121 - 经理 四级 12-5 11:51 汉诺塔 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。 后来，这个传说就演变为汉诺塔游戏: 1.有三根杆子A,B,C。A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上 经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片： 如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 此外，汉诺塔问题也是程序设计中的经典递归问题。 补充：汉诺塔的算法实现（c++） #include
