汉诺塔VIII、汉诺塔IX、汉诺塔X。"/>
汉若塔系列续:汉诺塔VIII、汉诺塔IX、汉诺塔X。
汉诺塔VIII,在经典汉若塔问题上,问n个盘子的情况下,移动m次以后,是什么状态。(与第七代互为逆命题)我的思路:本质还是dfs,但是用m的值来指引方向,每搜一层确定第i个盘子在哪个塔,o(n)的算法,看图说明:
#include<iostream>
#include<vector>
using namespace std;
char get[65]; //记录I号盘子在哪个塔
long long f[65]; //2^i次的值
void got() //预处理的f[i]; 注意点:用1<<i会爆int。
{f[1]=2;for(int i=2;i<65;i++)f[i]=f[i-1]*2;
}
void dfs(char fl,char fr,char now,int lev,long long x) //同汉若塔第七代理,LVE是层数,x是目前的值
{get[lev]=now;if(lev==1)return; //出口char temp;if(fl=='A'&&fr=='B'||fl=='B'&&fr=='A')temp='C';else if(fl=='A'&&fr=='C'||fl=='C'&&fr=='A')temp='B';else temp='A'; lev--;long long tx=(f[lev]-1)/2; if(x<=tx) //小于它的{if(now==fl) //左边的下来dfs(fl,temp,fl,lev,x);elsedfs(temp,fr,temp,lev,x);}else{if(now==fl)dfs(fl,temp,temp,lev,x-tx-1); //减一,那一步是最下面的塔的移动elsedfs(temp,fr,fr,lev,x-tx-1);}
}
int main()
{got();int T;cin>>T;while(T--){long long n,m;cin>>n>>m;if(m<=(f[n]-1)/2)dfs('A','C','A',n,m);elsedfs('A','C','C',n,m-(f[n]-1)/2);vector<int>a,b,c;for(int i=n;i>=1;i--){if(get[i]=='A')a.push_back(i);else if(get[i]=='B')b.push_back(i);else c.push_back(i);}cout<<a.size();for(int i=0;i<a.size();i++)cout<<" "<<a[i];cout<<endl;cout<<b.size();for(int i=0;i<b.size();i++)cout<<" "<<b[i];cout<<endl;cout<<c.size();for(int i=0;i<c.size();i++)cout<<" "<<c[i];cout<<endl;}return 0;
}
汉若塔IX hdu2175,经典汉若塔问题上问第M次移动的是几号盘。
思路:同理,第n个盘之前,必先移动前n-1个,再移动第n号,再移动前n-1个,依次。所以二分法查找,在“中间”那个移动的酒在那一个盘了。
#include<iostream>
using namespace std;
long long f[65]; //2^i次的值
void got() //预处理的f[i]; 注意点:用1<<i会爆int。
{f[0]=1;f[1]=2;for(int i=2;i<65;i++)f[i]=f[i-1]*2;
}
int main()
{got();long long n,m;while(cin>>n>>m&&(n||m)){while(m!=f[n-1]){if(m<=f[n-1]-1);elsem=m-f[n-1];n--;}cout<<n<<endl;}return 0;
}
汉若塔X hdu2511 求第m次移动是把几号盘从哪个塔到哪个塔移动。第九代的扩展。
思路:做到这里,每步的移动已经一清二楚了,还是那颗树,“左中右”遍历序列便是所有状态。由于一共就6种可能移动法。每次移动后知道下一步的移动。
依旧采用二分寻根法,详见代码:
#include<iostream>
#include<string>
using namespace std;
long long f[65]; //2^i次的值
void got() //预处理的f[i]; 注意点:用1<<i会爆int。
{f[0]=1;f[1]=2;for(int i=2;i<65;i++)f[i]=f[i-1]*2;
}
string getnext(string s,int id) //状态转移
{if(s=="AC"){if(id==0)return "AB";else return "BC";}else if(s=="AB"){if(id==0)return "AC";else return "CB";}else if(s=="CB"){if(id==0)return "CA";else return "AB";}else if(s=="CA"){if(id==0)return "CB";else return "BA";}else if(s=="BA"){if(id==0)return "BC";else return "CA";}else if(s=="BC"){if(id==0)return "BA";else return "AC";}
}
int main()
{got();int T;cin>>T;long long n,m;while(T--){cin>>n>>m;string s="AC";while(m!=f[n-1]){if(m<=f[n-1]-1) {s=getnext(s,0);}else{s=getnext(s,1);m=m-f[n-1];}n--;}if(s=="AB")cout<<n<<" 1 2"<<endl;if(s=="BA")cout<<n<<" 2 1"<<endl;if(s=="AC")cout<<n<<" 1 3"<<endl;if(s=="CA")cout<<n<<" 3 1"<<endl;if(s=="BC")cout<<n<<" 2 3"<<endl;if(s=="CB")cout<<n<<" 3 2"<<endl;}return 0;
}
转载于:.html
更多推荐
汉若塔系列续:汉诺塔VIII、汉诺塔IX、汉诺塔X。
发布评论