题目大意
汉诺塔， 伪代码为
Function Hanoi(n,a,b,c)
if n==1 then
print(a+'->'+c)
else
Hanoi(n-1,a,c,b)
print(a+'->'+c)
Hanoi(n-1,b,a,c)
end if
end Function 统计以下信息：A->B,A->C,B->A,B->C,C->A,C->B的次数，以及所有移动的总步数。
分析
一开始硬生生找规律， 呜呜呜呜呜， 找的心态爆炸最后终于找出来了。最后会贴出我自己找的规律的代码。
这里介绍另一种方法， 记忆化搜索。 当我看到题解有记忆化搜索的字样时， 突然间恍然大悟， 想尝试着自己写一下但是失败了， 呜呜，看着std才写出来的。
普通递归时间复杂度太高， 本质原因就是重复搜索了好多。记忆化搜索就是想办法让重复搜索的次数减少， 具体详见百度。
如果你明白记忆化搜索了， 那就直接看代码就行了， 不明白的话， 那就再去学！
代码
记忆化搜索
#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
inline ll read() {
ll res = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
return f ? (~ res + 1) : res;
}
inline int _(char a, char b){
if (a == 'a' && b == 'b') return 1;
if (a == 'a' && b == 'c') return 2;
if (a == 'b' && b == 'a') return 3;
if (a == 'b' && b == 'c') return 4;
if (a == 'c' && b == 'a') return 5;
if (a == 'c' && b == 'b') return 6;
}
struct node{
ll sum[7];
node(){ms(sum, 0);};
node operator + (const node & x)const{
node tmp;
for (int i = 1; i <= 6; ++i) tmp.sum[i] = sum[i] + x.sum[i];
return tmp;
}
ll getsum(){
ll tmp = 0;
for (int i = 1; i <= 6; ++i) tmp += sum[i];
return tmp;
}
}ans;
using tu = tuple<int, char, char, char>;
map<tu, int>vis; //表示这个 组合(int, char, char, char) 是否已经搜索到.
map<tu, node>ma; // 储存这个组合下的 node值是多少
node Hanoi(int n, char a, char b, char c){ // 注意返回值是node, 这个太妙了
tu p = make_tuple(n, a, b, c);
if (vis[p]) return ma[p]; // 如果访问过这个元组, 直接return这个元组的值就行
node tmp;
if (n == 1) {
tmp.sum[_(a, c)]++; // a c 这步++
return tmp;
}
tmp = tmp + Hanoi(n - 1, a, c, b);
tmp.sum[_(a, c)]++;
tmp = tmp + Hanoi(n - 1, b, a, c);
vis[p] = 1;
return ma[p] = tmp;
}
int main(){
int n = read();
ans = Hanoi(n, 'a', 'b', 'c');
printf("A->B:%lld\n",ans.sum[1]);
printf("A->C:%lld\n",ans.sum[2]);
printf("B->A:%lld\n",ans.sum[3]);
printf("B->C:%lld\n",ans.sum[4]);
printf("C->A:%lld\n",ans.sum[5]);
printf("C->B:%lld\n",ans.sum[6]);
printf("SUM:%lld\n", ans.getsum());
return 0;
} 我自己找的规律， 找了一个多小时， 心态在爆炸的边缘疯狂试探。不过没什么参考价值。
#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
inline ll read() {
ll res = 0;
bool f = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = 1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
res = (res << 3) + (res << 1) + ch - '0';
ch = getchar();
}
return f ? (~res + 1) : res;
}
ll sum[7][100];
int main() {
// B -> A C -> B
sum[3][1] = 0;
sum[3][2] = 0;
sum[3][3] = 1;
sum[3][5] = 6;
for (int i = 3; i <= 30; ++i) {
sum[3][2 * i + 1] = sum[3][2 * i - 1] * 4 + i;
}
for (int i = 1; i <= 30; ++i)
sum[3][i * 2] = sum[3][i * 2 - 1];
// A -> B B -> C
sum[1][1] = 0;
sum[1][2] = 1;
sum[1][3] = 1;
sum[1][4] = 4;
sum[1][6] = 15;
sum[1][8] = 58;
ll tmp = 4 * 4;
for (int i = 3; i <= 30; ++i) {
sum[1][2 * i] = tmp - sum[3][(i - 1) * 2];
tmp *= 4;
}
for (int i = 1; i <= 30; ++i)
sum[1][i * 2 + 1] = sum[1][i * 2];
// A -> C
sum[2][1] = 1;
sum[2][2] = 1;
sum[2][3] = 3;
for (int i = 2; i <= 30; ++i) {
sum[2][2 * i] = sum[2][2 * (i - 1)] * 4 - (2 * (i - 1) - 1);
}
for (int i = 2; i <= 30; ++i)
sum[2][2 * i - 1] = sum[2][2 * i];
// C -> A
sum[5][1] = sum[5][2] = sum[5][3] = 0;
sum[5][4] = sum[5][5] = 2;
for (int i = 3; i <= 30; ++i)
sum[5][i * 2] = sum[1][i * 2] - i;
for (int i = 1; i <= 30; ++i)
sum[5][2 * i + 1] = sum[5][2 * i];
// 总步数
sum[0][1] = 2;
for (int i = 2; i <= 60; ++i) sum[0][i] = sum[0][i - 1] * 2;
int n = read();
printf("A->B:%lld\n"
"A->C:%lld\n"
"B->A:%lld\n"
"B->C:%lld\n"
"C->A:%lld\n"
"C->B:%lld\n"
"SUM:%lld\n", sum[1][n], sum[2][n], sum[3][n], sum[1][n], sum[5][n], sum[3][n], sum[0][n] - 1);
return 0;
} 恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。 --mingfuyan 千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。
京公网安备 11010502036488号