汉诺塔

问题介绍

法国数学家 爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神 梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而 梵塔、庙宇和众生也都将同归于尽。

数学解法

有n个盘子，和柱子x、y、z
  设把n个盘子从x移动到z所需步数N=f(n)
  那么，把n-1个盘子从x移动到y所需的步数为f(n-1)，把n-1个盘子从y移动到z所需步数也为f(n-1)
  把n个盘子从x移动到z可以分解为：
     1）把n-1个盘子从x移动到y
     2）把1个盘子从x移动到z
     3）把n-1个盘子从y移动到z
  那么f(n)=f(n-1)+1+f(n-1)=2f(n-1)+1
  
  由f(n)=2f(n-1)+1
  得f(n)+1=2f(n-1)+2=2(f(n-1)+1)
  即
  f(n)+1=2(f(n-1)+1)
  同理
  f(n-1)+1=2(f(n-2)+1)
  f(n-2)+1=2(f(n-3)+1)
  ...
  f(3)+1=2(f(2)+1)
  f(2)+1=2(f(1)+1)
  将上面所有式子左右两边分别相乘得
  f(n)+1=2^(n-1)*2(f(1)+1)=2^n*(f(1)+1)=2^(n+1)
  f(n)=2^(n+1)-1
  即把n个盘子从x移动到z所需步数N=2^(n+1)-1

如果需要的是结果，那么通过数学分析就可以得到，如果需要知道执行步骤，那么就需要代码递归了

package com.zby;
  
 /**
  * @author zby
  * @title Hanoi
  * @date 2019年6月13日
  * @description 汉诺塔
  */
 public class Hanoi {
  
     private static int counter = 0;
  
     public static void main(String[] args) {
         remove(4, "X", "Y", "Z");
         System.out.printf("一共移动%d步", counter);
     }
  
     public static void remove(int floor, String source, String mid, String target) {
         if (floor == 1) {
             System.out.println("第" + ++counter + "次从" + source + "移动到" + target);
             return;
         }
         remove(floor - 1, source, target, mid);
         remove(1, source, mid, target);
         remove(floor - 1, mid, source, target);
     }
 }

 结果

第1次从X移动到Y
 第2次从X移动到Z
 第3次从Y移动到Z
 第4次从X移动到Y
 第5次从Z移动到X
 第6次从Z移动到Y
 第7次从X移动到Y
 第8次从X移动到Z
 第9次从Y移动到Z
 第10次从Y移动到X
 第11次从Z移动到X
 第12次从Y移动到Z
 第13次从X移动到Y
 第14次从X移动到Z
 第15次从Y移动到Z
 一共移动15步