하노이 사원의 탑 Hanoi Tower(C++)

Hanoi Tower라는 유명한 문제가 있다.
하노이 사원에는 3개의 막대가 있고 그중 하나의 막대에 3게의 크기가 서로 다른 n개의 둥근 원반이 끼워져 있다.
한 막대에 n개의 원반이 전부 꽃아져있고 각각의 원반은 자신보다 작은 원반 위에 있을 수 없다고 할때 n개의 원반을 다른 막대로 옮기는데 거리는 횟수를 구하는 문제다.



#include <iostream>
#include <windows.h>
#include <vector>

using namespace std;

int n,c;
vector<int> a[3];
void print_stacks_state();

void movestack(int h, bool isRight,int i){
     //i에 있는h높이의 탑을 오른쪽 또는 왼쪽으로 옮기는 것을
     //h-1높이의 탑을 옮기는 것으로 표현.
     //i칸에서 윗부분 h-1높이의 탑을 다른 칸으로 옯긴후 밑의 h번째 블락을 원하는
     //칸으로 옮긴후 그 칸으로 다른곳이 임시로 옮겨놓은h-1높이의 칸을 다시 옮긴다.
     //n 높이의탑을 옮길때 (n-1높이의 탑을 옮길때 움직인 횟수)*2+1만큼 든다.
     //따라서, 높이 1의 탑을 옮길 때 1의 횟수가 필요하므로 n일때는
     //2^(n-1)+2^(n-2)+...4+2+1이다
     //=등비가 2인 n개의 등비수열의 합=1*(2^n-1)/(2-1)=(2^n)-1
    
     if(h==1){
              (isRight)?a[(i+1)%3].push_back(a[i].back()):a[(i+2)%3].push_back(a[i].back());
              a[i].pop_back();
              c++;
              print_stacks_state();
              return;
     }                               
    
     movestack(h-1, !isRight, i);//옮기는 방향 반대로 움직인다.
    
     (isRight)?a[(i+1)%3].push_back(a[i].back()):a[(i+2)%3].push_back(a[i].back());
     a[i].pop_back();
     c++;
     print_stacks_state();    
    
    
     movestack(h-1, !isRight, (isRight)? ((i+2)%3):((i+1)%3));
     //n-1탑은 옮기는 방향 반대로 움직였다.
}

int main(){
    int i;
   
    while(true){
                cin>>n;
                if(1<=n&&n<=15)break;
                cout<<"1이상 15이하의 자연수를 입력"<<endl;
    }//이하의 자연수로 제한한것은 그 이상이 되면(2^15) 계산 시간이 너무 걸리기 때문이다.
   
    for(i=0;i<n;i++)a[0].push_back(n-i);
   
    print_stacks_state();
   
    movestack(n,true,0);
   
   
    system("PAUSE");
    return 0;
}
void print_stacks_state(){
     cout<<c<<"번째시도"<<endl;
     int i,j;
     for(j=0;j<3;j++){
                     for(i=0;i<30;i++)cout<<"-";
                     cout<<"\r";
                     for(i=0;i<a[j].size();i++){
                                                printf("%2d",a[j].at(i));
                     }
                     cout<<endl;
    }
}

실행결과

4
0번째시도
 4 3 2 1----------------------
------------------------------
------------------------------
1번째시도
 4 3 2------------------------
------------------------------
 1----------------------------
2번째시도
 4 3--------------------------
 2----------------------------
 1----------------------------
3번째시도
 4 3--------------------------
 2 1--------------------------
------------------------------
4번째시도
 4----------------------------
 2 1--------------------------
 3----------------------------
5번째시도
 4 1--------------------------
 2----------------------------
 3----------------------------
6번째시도
 4 1--------------------------
------------------------------
 3 2--------------------------
7번째시도
 4----------------------------
------------------------------
 3 2 1------------------------
8번째시도
------------------------------
 4----------------------------
 3 2 1------------------------
9번째시도
------------------------------
 4 1--------------------------
 3 2--------------------------
10번째시도
 2----------------------------
 4 1--------------------------
 3----------------------------
11번째시도
 2 1--------------------------
 4----------------------------
 3----------------------------
12번째시도
 2 1--------------------------
 4 3--------------------------
------------------------------
13번째시도
 2----------------------------
 4 3--------------------------
 1----------------------------
14번째시도
------------------------------
 4 3 2------------------------
 1----------------------------
15번째시도
------------------------------
 4 3 2 1----------------------
------------------------------
Press any key to continue . . .