Fundamental Algorithms Analysis(005)-Hanoi Tower【ハノタ】

Hanoi Tower
ハノタに関する問題の説明はすでによく知られているので、ここでは余計なことは言わない.ハノタ問題は古典的な再帰案列である.
Hanoi tower recursive method

void hanoi(int plates,vector<int> &A,vector<int> &B,vector<int> &C){
    //position:A->C,B is temporary state
    if(plates==1) (C.push_back(A.back()),A.pop_back());//A->C
    else{
        hanoi(plates-1,A,C,B);//move n-1 plates from to A to B
        hanoi(1,A,B,C);//move the surplus 1 plate(the bottom one) from A to C
        hanoi(plates-1,B,A,C);//move the n-1 plates from B to C
    }
}

Guys can try this version as well. I think they are the same. 別の境界判定だが、実は同じ理屈だ.

void hanoi(int plates,vector<int> &A,vector<int> &B,vector<int> &C){   
    if(plates>0){
    	hanoi(plates-1,A,C,B);//move n-1 plates from to A to B
    	(C.push_back(A.back()),A.pop_back());//move from A to C
    	hanoi(plates-1,B,A,C);//move the n-1 plates from B to C
    }
}

Main test
ここでは、アルゴリズムの手順を簡単に説明します.ポイントは1つだけで、一番下の皿を一度に処理しておきます.これは、上の残りの皿をどのように処理するかにかかわることは避けられないが、皿の積み重ねごとに、一番下の皿を先に処理しなければならない.このように推すと一連のサブプロセスが得られ,これらのサブプロセスは一歩一歩最後の真の問題の解に達することができる.

#include 
#include 
using namespace std;
struct tower{vector<int> A,B,C;};
void hanoi(int plates,vector<int> &A,vector<int> &B,vector<int> &C){
    //position:A->C,B is temporary state
    if(plates==1) (C.push_back(A.back()),A.pop_back());//A->C
    else{
        hanoi(plates-1,A,C,B);//move n-1 plates from to A to B
        hanoi(1,A,B,C);//move the surplus 1 plate(the bottom one) from A to C
        hanoi(plates-1,B,A,C);//move the n-1 plates from B to C
    }
}
int main()
{
    tower t;
    int plates=10,i=plates;
    fill_n(back_inserter(t.A),plates,0);
    while(i>0) t.A[plates-i]=i--;
    hanoi(plates,t.A,t.B,t.C);
    cout<<t.A.size()<<" "<<t.B.size()<<endl;
    for(int j=0;j<t.C.size();++j)cout<<t.C[j]<<" ";
}

パソコンがタイムリーに計算できない可能性があるので、あまり大きな数字を試さないことをお勧めします.