| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 汉诺塔游戏 | ★☆☆☆☆ | 答案正确 | 100 | {{{time}}} | 40（暴搜） |
有A、B、C三个柱子，A柱子上有n个盘子（下大上小），要求在维持上大下小的情况下，把A柱上的所有盘子移动到C柱子，一次只能移动一个盘子。
当然暴搜是一个办法，顺便写了个OOP的暴搜，当然不可避免的TLE+MLE，40分（没优化，优化也好不到哪儿去。纯粹是为了复习STL和OOP，要不纯粹暴搜代码量也不会这么大）。
汉诺塔毕竟还是个经典数学问题，由于很久没碰真的已经完全不记得了，于是度娘了一下。
大致是这样的：
对于初始状态，要想把A整个移走，最后一个盘子必须先移走放到C。要能够做这一步，此时其余盘子则都在B，才可以把A的最后一个大盘子移到C。
所以最优步骤应该是：
其中第1、3步和n-1的情况移动方法都一样，所以可以通过简单的递归实现。
感觉好神奇，真是十分经典。
n层的步数也十分容易计算：
根据以上分析，容易知道两层的步数
整理后容易求得：
(n为正整数)
std::ios::sync_with_stdio(0);
CloudLunar//建议使用
void f(const type&a){...};
//而不是
void f(type a){...};
| 3145bfs.cpp代码已折叠（40分）
展开折叠内容
|
|---|
#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;
}
|
| 3145递归.cpp代码已折叠
展开折叠内容
|
|---|
#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;
}
|