递归-汉罗塔及其变种

0x00 原生汉罗塔

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

分析

思路：

        A上的N-1个盘借助C移动到B

        A最底下那个盘移动到C

        B上的N-1个盘子借助A移动到C

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
void move(char A, char B) {
	cout << A << "->" << B << endl;
}
 
 
 
void hanoi(int n, char a, char b, char c)
{
	if (n == 1)
	{
		move(a, c);
	}
	else
	{
		hanoi(n - 1, a, c, b);//将A座上的n-1个盘子借助C座移向B座
		move(a, c);//将A座上最后一个盘子移向C座
		hanoi(n - 1, b, a, c);//将B座上的n-1个盘子借助A座移向C座
	}
}
 
 
int main() {
	int n = 0;
	cin >> n;
	hanoi(n,'A','B','C');
	return 0;
}

0x01 变种汉罗塔

        相较于原始汉罗塔，现在我们改变这个游戏的玩法:不允许直接从最左(右)边移动到最右()边(每次移动一定是移到中间杆或从中间杆移出)，也不允许大圆盘放到小圆盘的上面。Daisy 已经做过原来的汉诺塔问题和汉诺塔I问题，但碰到这个问题时，她想了很久都无法解决。请你帮助她。现在有 N个圆盘，和A、B、C三根柱子，她至少需要多少次移动才能把这些圆盘从最左边移到最右边,并且打印出移动的路径。

分析：

        由于不能直接由A到C，因此：

        A上的N-1先借助B到C。(需要F(n-1)次移动)

        A最底下的到B。          (需要1次移动)

        C上的N-1借助B到A。(需要F(n-1)次移动)

        B最底下的到C。        (需要1次移动)

        A的N-1借助B到C。(需要F(n-1)次移动)

因此F(n)=3F(n-1)+2。

只统计次数

long long hani(int n) {
	if (n == 1) {
		return 2;
	}
	else {
		return 3 * hani(n - 1) + 2;
	}
}

打印路径 

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
void move(char A, char B) {
	cout << A << "->" << B << endl;
}
 
void hani(int n,char a,char b,char c) {
	if (n == 1) {
		move(a,b);
		move(b, c);
	}
	else {
		hani(n - 1,a,b,c);
		move(a,b);
		hani(n - 1,c,b,a);
		move(b, c);
		hani(n - 1,a,b,c);
	}
}
int main() {
	int n = 0;
	cin >> n;
	hani(n,'A','B','C');
 
	return 0;
}