四塔问题

--------------------------------------------------------------------------------

Time Limit:1s Memory limit:32M
Accepted Submit:2 Total Submit:5


--------------------------------------------------------------------------------

“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有4根柱子，而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？

为了编程方便，您只需要输出这个结果mod 10000的值。

Input
该题含有多组测试数据，每组一个正整数n。(0<n<=50000)

Output
一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。

Sample Input

15

Sample Output

129


个人代码(C++描述),写出的不是最优解
move为用普通3个塔
move_1为用4个塔,个人验证后认为是正确的,但不是最优解(及移动的总步数最少)
move_2也为用4个塔,但是验证后是错的

#include<iostream>
using namespace std;
void move(int n,int n1,int n2,char a,char b,char c,int & count);
void move_1(int n,char a,char b,char c,char d,int & count);
void move_2(int n,int n1,int n2,char a,char b,char c,char d,int & count);
int main()
{

int n;
do {
cout<<endl<<endl<<"n=";
cin>>n;
int count=0;
cout<<endl<<"Method 1:"<<endl;
move(n,1,n,''A'',''B'',''C'',count);
cout<<"Using Method 1,Total Steps:"<<(count%10000)<<endl;
count=0;
cout<<endl<<"Method 2:"<<endl;
move_1(n,''A'',''B'',''C'',''D'',count);
cout<<"Using Method 2,Total Steps:"<<(count%10000)<<endl;
count=0;
cout<<endl<<"Method 3:"<<endl;
move_2(n,1,n,''A'',''B'',''C'',''D'',count);
cout<<"Using Method 3,Total Steps:"<<(count%10000)<<endl;
}while(n>=0);
return 0;
}
void move(int n,int n1,int n2,char a,char b,char c,int & count)
{
    if (1==n)  {
         cout<<"Step "<<++count<<"\t"<<n<<":"<<a<<"->"<<c<<endl;
         return ;
    }
    if (0==n)  {
         return ;
    }
    move(n-1,1,n-1,a,c,b,count);
    //cout<<"Step "<<++count<<"\t"<<n-1<<":"<<a<<"->"<<b<<endl;
    cout<<"Step "<<++count<<"\t"<<n<<":"<<a<<"->"<<c<<endl;
    //cout<<"Step "<<++count<<"\t"<<n-1<<":"<<b<<"->"<<d<<endl;
    move(n-1,1,n-1,b,a,c,count);
    return ;
}
void move_1(int n,char a,char b,char c,char d,int & count)
{
     if (1==n)  {
         cout<<"Step "<<++count<<"\t"<<n<<":"<<a<<"->"<<d<<endl;
         return ;
     }
     if (0==n)  {
         return ;
     }
    move_1(n-2,a,b,d,c,count);
    cout<<"Step "<<++count<<"\t"<<n-1<<":"<<a<<"->"<<b<<endl;
    cout<<"Step "<<++count<<"\t"<<n<<":"<<a<<"->"<<d<<endl;
    cout<<"Step "<<++count<<"\t"<<n-1<<":"<<b<<"->"<<d<<endl;
    move_1(n-2,c,a,b,d,count);
    return ;
}
void move_2(int n,int n1,int n2,char a,char b,char c,char d,int & count)
{
     if (1==n)  {
         cout<<"Step "<<++count<<"\t"<<n<<":"<<a<<"->"<<d<<endl;
         return ;
     }
     if (0==n)  {
         return ;
     }
    move_2(n/2,1,n/2,a,b,d,c,count);
    move(n/2,n/2+1,n-1,a,d,b,count);
    //cout<<"Step "<<++count<<"\t"<<n-1<<":"<<a<<"->"<<b<<endl;
    cout<<"Step "<<++count<<"\t"<<n<<":"<<a<<"->"<<d<<endl;
    //cout<<"Step "<<++count<<"\t"<<n-1<<":"<<b<<"->"<<d<<endl;
    move(n/2,n/2+1,n-1,b,a,d,count);
    move_2(n/2,1,n/2,c,a,b,d,count);
    return ;
}