java 實(shí)現(xiàn)漢諾塔詳解及實(shí)現(xiàn)代碼

漢諾塔問題：有三根柱子A,B,C，其中A上面有n個(gè)圓盤，從上至下圓盤逐漸增大，每次只能移動(dòng)一個(gè)圓盤，并且規(guī)定大的圓盤不能疊放在小的圓盤上面，現(xiàn)在想要把A上面的n個(gè)圓盤全部都移動(dòng)到C上面，輸出移動(dòng)的總步數(shù)以及移動(dòng)的過程

分析：

//先求出移動(dòng)的總步數(shù) 1，假設(shè)g（n）表示n個(gè)圓盤時(shí)的移動(dòng)總的步數(shù)，當(dāng)n=1時(shí)，g(1)=1; 2.現(xiàn)在可以把g(n)進(jìn)行細(xì)分為三步： 1>先將n-1個(gè)圓盤從A通過C移動(dòng)到B上面，相當(dāng)于將n-1個(gè)圓盤從A移動(dòng)到C，因此需要g(n-1)步； 2>然后將剩下的最大的圓盤從A移動(dòng)到C，需要1步； 3>最后再將n-1個(gè)圓盤從B通過A移動(dòng)到C上面，相當(dāng)于將n-1個(gè)圓盤從A移動(dòng)到C，因此也需要g(n-1)步； 因此可以得出遞歸關(guān)系式：g(n) = 2*g(n-1)+1; //現(xiàn)在我們?cè)趤砬蟪鲆苿?dòng)的過程 1.假設(shè)hm(m,a,b,c)表示將m個(gè)圓盤從a通過b移動(dòng)到c的過程，假設(shè)mv(a,c)輸出一次a到c的過程，即print a-->c 2.初始化hm，當(dāng)m=1時(shí)，hm(1,a,b,c)=mv(a,c); 2.可以把hm(m,a,b,c)進(jìn)行細(xì)分為三步： 1>先將n-1個(gè)圓盤從A通過C移動(dòng)到B，此時(shí)b和c進(jìn)行互換，也就是 hm(m-1,a,c,b); 2>然后將剩下的最大的圓盤從A移動(dòng)到C，也就是hm(1,a,b,c); 3>最后將n-1個(gè)圓盤從B通過A移動(dòng)到C，此時(shí)b和a進(jìn)行交換，也就是 hm(m-1,b,a,c); 最終得到過程的遞歸關(guān)系式：hm(m,a,b,c) = hm(m-1,a,c,b)+1+hm(m-1,b,a,c);

實(shí)現(xiàn)代碼：

public class test{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); test t = new test(); //獲取總的步數(shù) System.out.println("需要移動(dòng)的總步數(shù)為:" +t.getSum(n)); //獲取移動(dòng)的過程 t.hm(n,'a','b','c'); } //獲取總步數(shù) public int getSum(int n){ if(n == 1) return 1; return 2 * getSum(n-1) +1 ; } //獲取移動(dòng)的過程 public void hm(int m,char a,char b,char c){ if(m == 1) move(a,c); hm(m-1,a,c,b); move(a,c); hm(m-1,b,a,c); } //輸出一次移動(dòng)的過程 public void move(char a,char c){ System.out.print(a + "-->" + c + " "); } }