浅析 NC14585 大吉大利，今晚吃鸡 （汉诺塔加强版）

题目链接：

https://ac.nowcoder.com/acm/problem/14585

题面：

糖和抖m在玩个游戏，规定谁输了就要请谁吃顿大餐：抖m给糖a b c三个驻， 并在a柱上放置了数量为n的圆盘，圆盘的大小从上到下依次增大，现在要做的事就是把a柱的圆盘全部移到c柱，移动的过程中保持小盘在上，大盘在下，且限定圆盘只能够移动到相邻的柱子，即a柱子上的圆盘只能够移动到b，b柱子上的圆盘只能够移动到a或者c，c同理。现在请你设计一个程序，计算所需移动的最小步数， 帮助糖赢得大餐！

输入描述:
每一行输出有一个整数n(0<=n<26), 直至文件末尾。
输出描述:
对于每一组数据，输出一行，输出移动的最小步数M。


input: 1 
output: 2

input: 2
output: 8

input: 3
output: 26

分析：

汉诺塔问题的加强版。可以先用问题归约图理解原版汉诺塔问题的递归层数和遍历顺序。

参考题解：

https://www.cnblogs.com/BlankYang/p/16403783.html

与普通的汉诺塔不同的是，此汉诺塔的 f(n) 表示的 A 到 C 的两步而不是一步。过程如下：

把 n−1 个圆盘从 A 移到 B 再移到 C 走了 f(n−1) 步
把第 n 个盘子从 A 移到 B 走了一步
把 n−1 个圆盘从 C 移到 B 再移到 A 走了 f(n−1) 步
把第 n 个盘子从 B 移到 C 走了一步
把 n−1 个圆盘从 A 移到 B 再移到 C 走了 f(n−1) 步
于是有递推公式 f(n)=3f(n−1)+2 。

解得 f(n)=3^n−1 。

时间复杂度 O(logn)

空间复杂度 O(1)

我也可以一步步地计算，假设 $f(n)f(n)$ 表示：把 n 个圆盘从一个柱子转移到相邻的柱子需要的步数。
n个圆盘的移动过程如下：

1. 把 n-1 个圆盘从 A 移动到 B 需要 $f(n-1)f(n-1)$ 步；
2. 把 n-1 个圆盘从 B 移动到 C 需要 $f(n-1)f(n-1)$ 步；
3. 把第 n 个圆盘从 A 移动到 B 需要 1 步；
4. 把 n-1 个圆盘从 C 移动到 B 需要 $f(n-1)f(n-1)$ 步；
5. 把 n-1 个圆盘从 B 移动到 A 需要 $f(n-1)f(n-1)$ 步；
6. 把第 n 个圆盘从 B 移动到 C 需要 1 步；
7. 把 n-1 个圆盘从 A 移动到 B 需要 $f(n-1)f(n-1)$ 步；
8. 把 n-1 个圆盘从 B 移动到 C 需要 $f(n-1)f(n-1)$ 步；

上面的步骤等价于下面的步骤：

1. 把 n 个圆盘从 A 移动到 B 需要 $f(n)f(n)$ 步；
2. 把 n 个圆盘从 B 移动到 C 需要 $f(n)f(n)$ 步；

由上述可得： $2f(n)=6f(n-1)+22f(n)\; =\; 6f(n-1)\; +\; 2$

再假设一个完整的n个圆盘的移动总步数为 $T(n)T(n)$，
易得：$T(n)=2f(n)=3T(n-1)+2T(n)\; =\; 2\; f(n)\; =\; 3\; T(n-1)\; +\; 2$

然后计算 $T(n)T(n)$ 的递推式即可：

代码：

数学：

#include<iostream>
#include<math.h>
using namespace std;
typedef long long ll;

ll quick_pow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)
			ans = (ans * a);
		b >>= 1;
		a = (a*a);
	
	}
	return ans;
}

int main () {
	
	ll n;
	while (cin >> n) {
		if (n == 0) {
			cout << 0;
			return 0;
		}
		cout << (ll)pow(3, n) - 1 << endl;
//		cout << quick_pow(3, n) - 1 << endl;
	}

	return 0;
}

递归：

#include<iostream>
#include<math.h>
using namespace std;

int deep = 0;
int cnt = 0;

void hanoi(int n, char a, char b, char c);

void move(char a, char b) {
	cnt++;
//	cout << a << " -> " << b << endl;
}


// 基于问题归约图
// 在第n层子问题的深度下， 把a柱最上面的盘子经过b柱中转到达c柱
void hanoi(int n, char a, char b, char c) {  
	if (n == 0) return ;

	// 把a柱的前n-1个盘子经过b柱中转到达c柱 （在n-1层走2步）
	hanoi(n-1, a, b, c);
	
	// 把最大的盘子从a柱移动到b柱 （走1步）
	move(a, b);  
	
	// 把c柱的前n-1个盘子经过b柱中转到达a柱 （在n-1层走2步）
	hanoi(n-1, c, b, a);
	
	// 把最大的盘子从a柱移动到c柱 （走1步）
	move(b, c);

	// 把a柱的前n-1个盘子经过b柱中转到达c柱 （在n-1层走2步）
	hanoi(n-1, a, b, c);
}

int main () {
	while (cin >> deep) {
        cnt = 0;
        hanoi(deep, 'A', 'B', 'C');
        cout << cnt << endl;
    }
		
//	cout << "cnt : " << cnt;

}