# 汉诺塔题目总结

1.四柱汉诺塔问题和n柱汉诺塔问题

``````#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double f[70];

void init() {
f[1] = 1;
f[2] = 3;

for(int i = 3; i <= 65; i++) {
double Max = f[i - 2] * 2 + 3;
for(int j = 1; j < i; j++)
Max = min(Max, 2 * f[i - j] + pow(2,j) - 1);
f[i] = Max;
}
}

int main() {
init();
int n;
while(scanf("%d", &n) == 1) {
printf("%d\n", (int)f[n]);
}
return 0;
}
``````

2.计算某个盘子被移动的次数

``````#include<cstdio>
long long ans[65];
int main() {
ans[1] = 1;
for(int i = 2; i <= 60; i++)
ans[i] = ans[i - 1] * 2;
int test, x, y;
scanf("%d", &test);
while(test--) {
scanf("%d%d", &x, &y);
printf("%I64d\n", ans[x - y + 1]);
}
return 0;
}
``````

3.无规则汉诺塔

``````#include<cstdio>

int main() {
long long ans[31];
int test, n;
ans[1] = 3;
for(int i = 2; i <= 30; i++)
ans[i] = ans[i-1] * 3;
scanf("%d", &test);
while(test--) {
scanf("%d", &n);
printf("%I64d\n",ans[n]);
}
return 0;
}
``````

4.状态查询

``````#include<cstdio>
#include<cstring>
#define maxn 70
int num[3][maxn];
bool solve(int n, int *one, int *two, int *three) {
if(two[0] == n)
return 0;
else if(one[0] == n)
return solve(n - 1, one + 1, three, two);
else if(three[0] == n)
return solve(n - 1, two, one, three + 1);
return 1;
}

int main() {
int test, n;
scanf("%d", &test);
while(test--) {
int n, m;
scanf("%d", &n);
for(int i = 0; i < 3; i++) {
scanf("%d", &m);
for(int j = 0; j < m; j++)
scanf("%d", &num[i][j]);
num[i][m] = -1;
}
printf("%s\n", solve(n,num[0],num[1],num[2]) ? "true" :"false");
}
return 0;
}
``````

5.不规则移动

A.

``````#include<cstdio>

int main() {
long long ans[40];
int n;
ans[1] = 2;
for(int i = 2; i <= 35; i++)
ans[i] = ans[i - 1] * 3 + 2;
while(scanf("%d", &n) == 1) {
printf("%I64d\n", ans[n]);
}
return 0;
}
``````

B.

``````#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 25

int main() {
long long f[maxn], g[maxn], d[maxn], e[maxn];
f[1] = 2;
for(int i = 2; i <= 20; i++)
f[i] = 3 * f[i - 1] + 2;

d[1] = 1, d[2] = 4;
for(int i = 3; i <= 20; i++)
d[i] = f[i - 1] + f[i - 2] + 2 + d[i - 2];
e[1] = 1, e[2] = 4;

for(int i = 3; i <= 20; i++)
e[i] = e[i - 2] + 2 + f[i - 2] + f[i - 1];
g[1] = 2, g[2] = 4, g[3] = 10;
for(int i = 4; i <= 20; i++) {
g[i] = 2 * f[i - 2] + 2 * f[i - 3] + 6 + d[i - 3] + e[i - 3];
g[i] = min(g[i],f[i]);
}
int test, n;
scanf("%d", &test);
while(test--) {
scanf("%d", &n);
printf("%lld\n", g[n]);

}
return 0;
}
``````