链接：https://www.nowcoder.net/acm/contest/67/D 来源：牛客网 相信大家都知道汉诺塔问题。那么现在对汉诺塔问题做一些限制，成为一个新的玩法。 在一个底座上，从左到右有三个分别命名为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的情况。 示例1 输入 3 5 4 10 输出 3 1 2 0 4 3 1 2 备注: 10000组数据。 对于100%的数据， 1 <= n < 40; 1 <= k < (3^n)。
汉诺塔移动是一个递归的过程
比如说 把 n 个 圆盘从第一根柱子移到第三根柱子的过程就是：
1、将第一根柱子上 n-1 个圆盘移到第三根柱子
2、将第一根柱子上的 n 号圆盘移到第二根柱子
3、将第三根柱子上 n-1 个圆盘移回第一根柱子
4、将 n 号圆盘从第二根柱子移到第三根柱子
5、重复步骤 1
可以得到递推式 F(n) = F(n-1) + 1 + F(n-1) + 1 + F(n-1)
根据k可以判断n号圆盘放置的位置，然后不断递推上去，可以得到所有圆盘放置的位置
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define LL long long
LL n,k,a[50],ans[10][50],sz[10];
void slove(int n,int pos){
if(n==0) return;
if(k<=a[n-1]) {
ans[pos][sz[pos]++] = n;
slove(n-1, pos);
}else if(k==a[n-1]+1){
ans[2][sz[2]++] = n;
while(--n) ans[4-pos][sz[4-pos]++] = n;
}else if(k<=2*a[n-1]+1){
ans[2][sz[2]++] = n;
k -= a[n-1]+1;
slove(n-1, 4-pos);
}else if(k==2*a[n-1]+2){
ans[4-pos][sz[4-pos]++] = n;
while(--n) ans[pos][sz[pos]++] = n;
}else{
ans[4-pos][sz[4-pos]++] = n;
k -= 2*a[n-1]+2;
slove(n-1, pos);
}
}
int main()
{
a[0] = 0; a[1] = 2;
for(int i=2;i<40;i++) a[i] = 3 * a[i-1] + 2;
while(scanf("%lld%lld",&n,&k)!=EOF){
memset(sz,0,sizeof sz);
for(int i=1;i<=n;i++){
if(a[i]>=k){
while(n>i) ans[1][sz[1]++] = n--;
slove(i, 1);
break;
}
}
for(int i=1;i<=3;i++){
for(int j=0;j<sz[i];j++){
printf("%lld%c",ans[i][j],(j==sz[i]-1)?'\n':' ');
}
if(sz[i]==0) printf("0\n");
}
}
return 0;
}