题目描述

The Tower of Hanoi game consists of three stacks (left, middle and right) and n round disks of different sizes. Initially, the left stack has all the disks, in increasing order of size from top to bottom. 
The goal is to move all the disks to the right stack using the middle stack. On each move you can move the uppermost disk from a stack to another stack. In addition, it is not allowed to place a larger disk on a smaller disk.
Your task is to find a solution that minimizes the number of moves.

输入

The only input line has an integer n（1 ≤ n ≤ 16）: the number of disks.

输出

First print an integer k: the minimum number of moves.
After this, print k lines that describe the moves. Each line has two integers a and b: you move a disk from stack a to stack b.

样例输入

复制

2

样例输出

复制

3
1 2
1 3
2 3

1.递归

要解决汉诺塔问题，我们可以使用递归的方法，这是最经典且高效的解决方案。汉诺塔问题的最少移动次数是 2ⁿ-1，其中 n 是盘子的数量。

递归思路如下：

1. 将 n-1 个盘子从源柱移动到辅助柱

2. 将第 n 个盘子从源柱移动到目标柱

3. 将 n-1 个盘子从辅助柱移动到目标柱

2.移动次数

汉诺塔问题中，最少移动次数为 2n−1（n 为盘子数量），这是通过数学归纳法证明的结论，具体推导过程如下：

1. 基础情况（n=1）

当只有 1 个盘子时：

• 直接从源柱移到目标柱，只需 1 次 移动。

• 代入公式：21−1=1，成立。

2. 归纳假设（假设 n=k 时成立）

假设当有 k 个盘子时，最少移动次数为 2k−1。

3. 归纳推理（证明 n=k+1 时成立）

当有 k+1 个盘子时，移动过程分为 3 步：

1. 将 前 k 个盘子 从源柱移到辅助柱，需要 2k−1 次（根据归纳假设）。

2. 将 第 k+1 个盘子（最大的盘子）从源柱移到目标柱，需要 1 次。

3. 将 前 k 个盘子 从辅助柱移到目标柱，需要 2k−1 次（根据归纳假设）。

总移动次数为：(2k−1)+1+(2k−1)=2×2k−1=2k+1−1

因此，当 n=k+1 时公式也成立。

代码

#include<bits/stdc++.h>
using namespace std;int n;
vector<pair<int,int>>moves;void hanoi(int n,int from,int to,int aux){if(n==1){moves.push_back({from,to});return;}hanoi(n-1,from,aux,to);moves.push_back({from,to});hanoi(n-1,aux,to,from);	
}int main(){ios::sync_with_stdio(false);cin>>n;hanoi(n,1,3,2);cout<<moves.size()<<'\n';for(auto i:moves){cout<<i.first<<" "<<i.second<<'\n';}return 0;
}