具体数学-汉诺塔问题

, , , ,

题目

设$T_n$：将$n$个圆盘从一根桩移动到另一根桩所需最少移动次数。

思路：先把$n-1$个小的圆盘移动到另一个桩上（需要$T_{n-1}$次），再移动最大的圆盘（需要$1$次），最后将$n-1$个小圆盘移到最大圆盘上（需要$T_{n-1}$次）。

$$
T_n=2T_{n-1}+1,n>0
$$

$$
T_n = 2^n-1, n \geqslant 0
$$

关键词： 数学归纳法（mathematical induction）

C++实现显示汉诺塔的移动步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
int g_cnt = 0;

void Move(char src, char dst)
{
    cout << src << "->" << dst << endl;
    ++g_cnt;
}

void Hanoi(int n, char src, char tmp, char dst)
{
	if (n == 1)
	{
		Move(src, dst);
		return;
	}
	Hanoi(n-1, src, dst, tmp);
	Move(src, dst);
	Hanoi(n-1, tmp, src, dst);
}

int main()
{
	int n;
	cin >> n;
    Hanoi(n, 'A', 'B', 'C');
    cout << g_cnt;
    return 0;
}