自分のプログラムを使ってハノイのアルゴリズムを理解しようとしています

Question

ハノイの塔のために、A - Bタワーからディスクを移動させ、余分なタワーをCとする次の作業プログラムがあります。 ：

A--B--C //fromTower, toTower,auxTower 
    A--C--B //fromTower, auxTower, toTower 
    C--B--A //auxTower, toTower, fromTower 

：あなたは私のプログラムでは再帰呼び出しから見ることができるように、私は三つの可能な電話を持っている

public static void moveDisks(
     int n, 
     char fromTower, 
     char toTower, 
     char auxTower) 
    { 
     if (n == 1) // Stopping condition 
      System.out.println(
       "Move disk " + n + " from " + fromTower + " to " + toTower); 
     else 
     { 
      moveDisks(n - 1, fromTower, auxTower, toTower); 
      System.out.println(
       "Move disk " + n + " from " + fromTower + " to " + toTower); 
      moveDisks(n - 1, auxTower, toTower, fromTower); 
     } 
    } 
} 

：moveDisks(n, 'A', 'B', 'C');

私は次のアルゴリズムを使用して行動を起こすたびに出力します

しかし、私は3ディスクに対して、次のプリントアウトを取得しています：

The moves are: 
Move disk 1 from A to B 
Move disk 2 from A to C 
Move disk 1 from B to C 
Move disk 3 from A to B 
Move disk 1 from C to A 
Move disk 2 from C to B 
Move disk 1 from A to B 

私は私のプログラムが正しいことを知っているが、私はこのような関数/メソッドを作ったことがないので、私は本当にそれがB--CとC--A呼び出しをやっているか届きませんあなたが私のA--B--C、fromTower, toTower,auxTowerモデルを使って、この再帰的な方法が3つのディスクに関してどのように動作しているかを見れば分かると思います。

Answer 1

は、それが驚くほど最初の左端の子を呼び出し、二分木構造を以下だと見ることができます（この場合は子供がprint文であります）を呼び出します。 moveDisks(2, 'A', 'C', 'B')：from-to-aux変数は、私がn=3とA= from,B=to, C= auxで起動したときに、私は次の呼び出しを取得throughout.So変更されているが

私は私の理解でいた間違いは、私はすべての再帰呼び出しのためのfrom-to-auxとしてA--B--Cを想定し、ということでしたそしてmoveDisks(2, 'C', 'B', 'A') .Nowこれらの再帰呼び出しのそれぞれは独立して自分の通話を開始しますが、最初の1、今A=from, C=to, and B=auxと私はmoveDisks(1,'A','B','C')とmoveDisks(1,'B','C','A')通話を得る最初のもののための二番目のC=from, B=to and A=aux。だから2つ目のために私はmoveDisks(1,'C','A','B')とmoveDisks(1,'A','B','C')のコールを取得します。反復は停止地点に達するまで続きます。

---

注：これはとても素晴らしいです、私は再帰を学ぶが、同様に、バイナリツリーを学んでしまいました！

Answer 2

あなたが最初の呼び出しの観点からだけmoveDisksに可能な呼び出しを検討している：

moveDisks(.., 'A', 'C', 'B') 
moveDisks(.., 'C', 'B', 'A') 

を呼び出しますが、再帰は、これらの呼び出しので、次のラウンドのために継続されます

moveDisks(.., 'A', 'B', 'C') 

を通話は

moveDisks(.., 'A', 'B', 'C') 
moveDisks(.., 'B', 'C', 'A') --> moving B to C 

とです私はlast.Iで、この自分自身を考え出した

moveDisks(.., 'C', 'A', 'B') 
moveDisks(.., 'A', 'B', 'C') 

...