#include <iostream>

#include <vector>

using namespace std;

class Needle

{

public:

    Needle() { a.push_back(100); }//每一個柱子都有一個底座

    void push(int n) { a.push_back(n); }

    int top() { return a.back(); }

    int pop() { int n = a.back(); a.pop_back(); return n; }

    int movenum(int n) { int i = 1;while (a[i] > n) i++; return a.size() - i; }

    int size() { return a.size(); }

    int operator [] (int n) { return a[n]; }

private:

    vector<int> a;

};

void  Hanoi(int n)

{

    Needle needle[3], ns;//3個柱子，ns是轉換柱子時的保存棧，借用了Needle的棧結構

    int source = 0, target, target_m = 2, disk, m = n; 

    for (int i = n; i > 0; i--) needle[0].push(i);//在A柱上放n個盤子

    while (n)//問題規(guī)模為n，開始搬動

    {

       if (!m) { source = ns.pop(); target_m = ns.pop();

m = needle[source].movenum(ns.pop()); }//障礙盤子搬走后，回到原來的當前柱

       if (m % 2) target = target_m; else target = 3 - source - target_m;//規(guī)律1的實現(xiàn)

       if (needle[source].top() < needle[target].top())//當前柱頂端盤子可以搬動時，移動盤子

       {

           disk = needle[source].top();m--;

           cout << disk << " move " << (char)(source + 0x41) << " to "<< (char)(target + 0x41) << endl;//顯示搬動過程

           needle[target].push(needle[source].pop());//在目標柱上面放盤子

           if (disk == n) { source = 1 - source; target_m = 2; m = --n; }

       }

       else//規(guī)律2的實現(xiàn)

       {

           ns.push(needle[source][needle[source].size() - m]);

ns.push(target_m); ns.push(source);

           m = needle[target].movenum(needle[source].top());

           target_m = 3 - source - target; source = target;

       }

    }

    

}