本文共 2058 字,大约阅读时间需要 6 分钟。
链接: 来源:牛客网
相信大家都知道汉诺塔问题。那么现在对汉诺塔问题做一些限制,成为一个新的玩法。
在一个底座上,从左到右有三个分别命名为A、B和C的塔座,有n个大小不一的圆盘。这些圆盘一开始,从小到大按顺序叠加在塔座A上,形成一座上小下大的塔,塔座B和C为空。我们将n个圆盘,从小到大编号为1~n。现要求将塔座A上的n个圆盘移至塔座C上并仍按照同样的顺序叠排,圆盘移动时必须遵循以下规则:
(1)每次只能将一个圆盘从一个塔座移动到相邻的塔座上 (2)所有圆盘可以叠在A、B和C中的任一塔座上(3)任何时刻都不能将一个较大的圆盘压在较小的圆盘上面
那么问题来了,对于一个n阶(阶数即是问题中圆盘的个数)的上述问题,用最少操作次数将圆盘塔从塔座A移动到塔座C的操作总是固定的。请问,n阶问题执行k步操作后,塔座A、B和C上圆盘的情况是怎样的?从大到小输出三个塔座上的圆盘的编号(如果该塔座上没有圆盘,请输出0)。
比如,塔座A上有圆盘1,3;塔座B上有圆盘2;塔座C上有圆盘4。我们将输出:
3 1
2
4
数据有多组,处理到文件结束。每组数据一行输入,有两个整数n和k,n代表问题的阶数,k代表执行的步数。
每组数据输出占三行。第一行描述塔座A的情况。第二行描述塔座B的情况。第三行描述塔座C的情况。
在纸上模拟一下可以找出规律
对于n阶汉罗塔,大致规律如下:
最大圆盘:当k<3^(n-1)时在位置1,当3^(n-1)<=k<2*3^(n-1)时在位置2,当k>=2*3^(n-1)时在位置3
第p(1<=p<n)大圆盘:他所在的位置是1,1,…,1,1,2,2,…,2,2,3,3,…,3,3,3,3,…,3,3,2,2,…,2,2,1,1,…,1,1然后继续循环
其中连续相同的数字(即"…")出现3^(p-1)次
#include#include using namespace std;#define LL long longLL san[45] = {1}, ans[5][33], A, B, C;int main(void){ LL n, m, i, now; for(i=1;i<=39;i++) san[i] = san[i-1]*3; while(scanf("%lld%lld", &n, &m)!=EOF) { A = B = C = 0; m += 1; for(i=n;i>=1;i--) { if(i==n) { now = (m-1)/san[i-1]+1; switch(now) { case 1: ans[1][++A] = i; break; case 2: ans[2][++B] = i; break; case 3: ans[3][++C] = i; } } else { now = m-m/(san[i]*2)*(san[i]*2); if(now==0) now = 6; else now = (now-1)/san[i-1]+1; switch(now) { case 1: ans[1][++A] = i; break; case 2: ans[2][++B] = i; break; case 3: ans[3][++C] = i; break; case 6: ans[1][++A] = i; break; case 5: ans[2][++B] = i; break; case 4: ans[3][++C] = i; } } } if(A==0) ans[1][++A] = 0; if(B==0) ans[2][++B] = 0; if(C==0) ans[3][++C] = 0; sort(ans[1]+1, ans[1]+A+1); sort(ans[2]+1, ans[2]+B+1); sort(ans[3]+1, ans[3]+C+1); printf("%lld", ans[1][A]); for(i=A-1;i>=1;i--) printf(" %lld", ans[1][i]); printf("\n"); printf("%lld", ans[2][B]); for(i=B-1;i>=1;i--) printf(" %lld", ans[2][i]); printf("\n"); printf("%lld", ans[3][C]); for(i=C-1;i>=1;i--) printf(" %lld", ans[3][i]); printf("\n"); } return 0;}
转载地址:http://wqmgf.baihongyu.com/