（以“分类:递归 ==摘要== {{信息题|汉诺塔游戏|http://www.codevs.cn/problem/3145/|1|100|40|暴搜|time2014-10-11 00:08:36}} ==题意== 有A、B、C三个...”为内容创建页面） |
小 （修改错误的摘要格式，修改数学表达式错误） |
||
| 第1行： | 第1行： | ||
[[分类:递归]] | [[分类:递归]] | ||
==摘要== | ==摘要== | ||
| − | {{信息题|汉诺塔游戏|http://www.codevs.cn/problem/3145/| | + | {{信息题|汉诺塔游戏|http://www.codevs.cn/problem/3145/|2|100|暴搜|40|time=2014-10-11 00:08:36}} |
==题意== | ==题意== | ||
有A、B、C三个柱子，A柱子上有n个盘子（下大上小），要求在维持上大下小的情况下，把A柱上的所有盘子移动到C柱子，一次只能移动一个盘子。 | 有A、B、C三个柱子，A柱子上有n个盘子（下大上小），要求在维持上大下小的情况下，把A柱上的所有盘子移动到C柱子，一次只能移动一个盘子。 | ||
| 第28行： | 第28行： | ||
n层的步数也十分容易计算： | n层的步数也十分容易计算： | ||
| − | 根据以上分析，容易知道两层的步数 | + | 根据以上分析，容易知道两层的步数: |
| − | * | + | *A[n]=2*A[n-1]+1(n为正整数,n>1) |
| − | * | + | *A[n]=1(n=1) |
整理后容易求得： | 整理后容易求得： | ||
| − | <m> | + | A[n]=<m>2^n-1</m>(n为正整数) |
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 汉诺塔游戏 | ★★☆☆☆ | 答案正确 | 100 | 2014-10-11 00:08:36 | 暴搜（40） |
有A、B、C三个柱子，A柱子上有n个盘子（下大上小），要求在维持上大下小的情况下，把A柱上的所有盘子移动到C柱子，一次只能移动一个盘子。
当然暴搜是一个办法，顺便写了个OOP的暴搜，当然不可避免的TLE+MLE，40分（没优化，优化也好不到哪儿去。纯粹是为了复习STL和OOP，要不纯粹暴搜代码量也不会这么大）。
汉诺塔毕竟还是个经典数学问题，由于很久没碰真的已经完全不记得了，于是度娘了一下。
大致是这样的：
对于初始状态，要想把A整个移走，最后一个盘子必须先移走放到C。要能够做这一步，此时其余盘子则都在B，才可以把A的最后一个大盘子移到C。
所以最优步骤应该是：
其中第1、3步和n-1的情况移动方法都一样，所以可以通过简单的递归实现。
感觉好神奇，真是十分经典。
n层的步数也十分容易计算：
根据以上分析，容易知道两层的步数:
整理后容易求得：
A[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;
}
|