Dqs1u. 汉诺塔问题(移动方向记数)
时间限制:1.0s 内存限制:256.0MB 代码提交间隔:3分钟(现在可以提交)
试题来源:蓝桥杯2018国际赛 中文版 Lanqiao 第四题
问题描述
汉诺塔问题是一个经典的数学问题。
给定三根柱子A、B、C,柱子A上按大小顺序放着 n 个大小不同的盘子,最下面的盘子最大,最上面的盘子最小。现在要将所有盘子从柱子A移动到柱子C上,问最少要移动多少次。
答案是最少 2n−1 次。而且要以最少的次数完成移动,只存在一种方案。
比如,当 n=3 时,总共要移动 23−1=7 步:
第1步:最小的盘子从A移到C,记为A→C;
第2步:第2小的盘子从A移到B,记为A→B;
第3步:最小的盘子从C移到B,记为C→B;
第4步:第3小的盘子从A移到C,记为A→C;
第5步:最小的盘子从B移到A,记为B→A;
第6步:第2小的盘子从B移到C,记为B→C;
第7步:最小的盘子从A移到C,记为A→C。
请问,总共有多少次A→B,多少次A→C,多少次B→A,多少次B→C,多少次C→A,多少次C→B?
输入格式
输入的第一行包含一个整数 n。
输出格式
输出六行,每行一个整数。分别表示以上六个问题的答案。
样例输入
3
样例输出
1
3
1
1
0
1
评测用例规模与约定
对于30%的评测用例,1≤n≤10。
对于60%的评测用例,1≤n≤30。
对于所有评测用例,1≤n≤60。
#include<bits/stdc++.h>
using namespace std;
void tmp(int n,char a,char b,char c,int &ab,int &ac,int &ba,int &bc,int &ca,int &cb)
{
if(n == 1)
{
if(a == 'A' && c == 'B') ab++;
else if(a == 'A' && c == 'C') ac++;
else if(a == 'B' && c == 'A') ba++;
else if(a == 'B' && c == 'C') bc++;
else if(a == 'C' && c == 'A') ca++;
else if(a == 'C' && c == 'B') cb++;
return ;
}
tmp(n - 1,a,c,b,ab,ac,ba,bc,ca,cb);
if (a == 'A' && c == 'B') ab++;
else if (a == 'A' && c == 'C') ac++;
else if (a == 'B' && c == 'A') ba++;
else if (a == 'B' && c == 'C') bc++;
else if (a == 'C' && c == 'A') ca++;
else if (a == 'C' && c == 'B') cb++;
tmp(n - 1,b,a,c,ab,ac,ba,bc,ca,cb);
}
int main()
{
int n;
scanf("%d",&n);
int ab = 0,ac = 0,ba = 0,bc = 0,ca = 0,cb = 0;
tmp(n,'A','B','C',ab,ac,ba,bc,ca,cb);
printf("%d\n%d\n%d\n%d\n%d\n%d",ab,ac,ba,bc,ca,cb);
return 0;
}
帮帮我把