汉若塔系列续：汉诺塔VIII、汉诺塔IX、汉诺塔X。

汉诺塔VIII、汉诺塔IX、汉诺塔X。"/>

汉若塔系列续：汉诺塔VIII、汉诺塔IX、汉诺塔X。

我的思路：本质还是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