題目描述

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;
}