查看CodeVS/3145的源代码 ←CodeVS/3145

[[分类:递归]]
==摘要==
{{信息题|汉诺塔游戏|http://www.codevs.cn/problem/3145/|1|100|40|暴搜|time2014-10-11 00:08:36}}
==题意==
有A、B、C三个柱子，A柱子上有n个盘子（下大上小），要求在维持上大下小的情况下，把A柱上的所有盘子移动到C柱子，一次只能移动一个盘子。
==题解==
===解题步骤及其分析===
当然暴搜是一个办法，顺便写了个OOP的暴搜，当然不可避免的TLE+MLE，40分（没优化，优化也好不到哪儿去。纯粹是为了复习STL和OOP，要不纯粹暴搜代码量也不会这么大）。


汉诺塔毕竟还是个经典数学问题，由于很久没碰真的已经完全不记得了，于是度娘了一下。

大致是这样的：

对于初始状态，要想把A整个移走，最后一个盘子必须先移走放到C。要能够做这一步，此时其余盘子则都在B，才可以把A的最后一个大盘子移到C。

所以最优步骤应该是：

#A除了最下面的盘子，都移到B；
#A最下面的盘子放到C；
#B所有盘子移到C；

其中第1、3步和n-1的情况移动方法都一样，所以可以通过简单的递归实现。

感觉好神奇，真是十分经典。


n层的步数也十分容易计算：

根据以上分析，容易知道两层的步数
*<m>A_n=2A_(n-1)+1</m>(n为正整数,n>1)
*<m></m>A_n=1</m>(n=1)
整理后容易求得：
<m>A_n=2^n-1</m>(n为正整数)


===程序实现的几个细节===
*众所周知，输入输出时，cin、cout慢于scanf、printf很多，原因是cin、cout要与scanf、printf同步，如果不混用，加上以下代码可以加速很多：
<pre>std::ios::sync_with_stdio(0);</pre>
*求2的n次方可以用二进制左移(<<)的方式快速实现，即<m>2^n</m>等价于1<<n。
*另外，传递常量的时候，用pass-by-reference-to-const代替pass-by-value，可以降低内存占用和构造析构函数时间成本（特别是使用非基本数据类型时），因为pass-by-value实际上是把该值复制了一遍存储于新的变量。即：
<pre>//建议使用
void f(const type&a){...};
//而不是
void f(type a){...};
</pre>
==代码==
{{折叠|3145bfs.cpp代码已折叠（40分）
|<pre>
#include<iostream>
#include<queue>
#include<stack>
#include<string>
#include<sstream>
int n;
class state{
    private:
        int step; 
        std::string data;
    public:
        state():
            step(0)
        {
            for(int i=n+1;i>=1;--i)
                U[0].push(i);
            U[1].push(n+1);
            U[2].push(n+1);
        }
        void printData()
        {
            std::cout<<step<<std::endl<<data;
        }
        void addData(const int &item,const std::string &aData)
        {
            ++step;
            std::stringstream f;
            f<<item;
            data+=f.str()+aData+"\n";
        }
        bool finished()
        {
            return U[2].size()==n+1;
        }
        std::stack<int> U[3];
};
std::queue<state> q;
void bfs()
{
    state init;
    q.push(init);
    while(!q.empty())
    {
        for(int i=0;i<3;++i)
            for(int j=0;j<3;++j)
                if(i!=j&&q.front().U[i].top()<q.front().U[j].top())
                {
                    state newState(q.front());
                    newState.addData(newState.U[i].top()," from "+
                        std::string(1,'A'+i)+" to "+std::string(1,'A'+j));
                    newState.U[j].push(newState.U[i].top());
                    newState.U[i].pop();
                    if(newState.finished())
                    {
                        newState.printData();
                        return;
                    }
                    q.push(newState);
                }
        q.pop();
    }
} 
int main()
{
    std::ios::sync_with_stdio(0);
    std::cin>>n;
    bfs();
    return 0;
}
</pre>
|code3145dfs}}
{{折叠|3145递归.cpp代码已折叠
|<pre>
#include<iostream>
void printStep(const char &from,const char &to,const int &n)
{
    std::cout<<n<<" from "<<from<<" to "<<to<<std::endl;
}
void move(const char &from,const char &to,const char &via,const int &n)
{
    if(n==1)
    {
        printStep(from,to,n);
        return;
    }
    move(from,via,to,n-1);
    printStep(from,to,n);
    move(via,to,from,n-1);    
}
int main()
{
    int n;
    std::ios::sync_with_stdio(0);
    std::cin>>n;
    std::cout<<(1<<n)-1<<std::endl;
    move('A','C','B',n);
    return 0;
}
</pre>
|code3145}}