汉诺塔问题

刺骨的言语ヽ痛彻心扉 2021-09-23 23:26 337阅读 0赞

# 汉诺塔问题 #

--------------------

### 文章目录 ###

*  汉诺塔问题
 *   *  1. 问题描述
     *  2. 问题分析
     *  3. 代码实现

--------------------

## 1. 问题描述 ##

> 有三根针 A，B，C。A 针上有  n n n 个盘子，盘子大小不等，大的在下，小的在上。要求把这  n n n 个盘子从 A 针移到 C 针，在移动过程中可以借助 B 针，每次只允许移动一个盘，且在移动过程中三根针上都保持大盘在下，小盘在上。

## 2. 问题分析 ##

> 将  n n n 个盘子从 A 针移到 C 针可以分解为下面 3 个步骤。
> 
> 1.  将 A 上  n − 1 n-1 n−1 个盘子移到 B 针上（借助 C 针）。
> 2.  把 A 针上剩下的一个盘子移到 C 针上。
> 3.  将  n − 1 n-1 n−1 个盘子从 B 针移到 C 针上（借助 A 针）。

> 事实上，上面 3 个步骤包含下面两种操作。
> 
> 1.  将多个盘子从一个针移到另一个针，这是一个递归过程。
> 2.  将 1 个盘子从一个针上移到另一个针上。

于是用两个函数分别实现上面两种操作，用 hanoi 函数实现第 (1) 种操作，用 move 函数实现第 (2) 种操作。

--------------------

## 3. 代码实现 ##

C++ 代码

#include <iostream>
    using namespace std;
    
    // 把 source 针的最上面一个盘子移动到 destination 针上
    void move(char source, char destination)
    { 
    	cout << source << " --> " << destination << endl;
    }
    
    // 把 n 个盘子从 source 针移动到 destination 针，以 medium 针作为中介
    void hanoi(int n, char source, char medium, char destination)
    { 
    	if (1 == n)
    	{ 
    		move(source, destination);
    	}
    	else
    	{ 
    		// 将 source 针上 n-1 个盘子，先借助于 destination 针，移动到 medium 针上.
    		// 这样过后， source 针上就只剩下一个最大（最下面）的那个盘子.
    		hanoi(n - 1, source, destination, medium);
    		// 将 source 针上最后一个盘子，直接移动到 destination 针上.
    		move(source, destination);
    		// medium 针上的 n-1 个盘子，其实就是原来 source 针上的 上面 n-1 个盘子.
    		// 借助于 source 针，最后移动到 destination 针上.
    		hanoi(n - 1, medium, source, destination);
    	}
    }
    
    int main(int argc, char* argv[])
    { 
    	int m;
    	cout << "Enter the number of disks: ";
    	cin >> m;
    	cout << "the steps to moving " << m << " disks:" << endl;
    	hanoi(m, 'A', 'B', 'C');
    	return 0;
    }

--------------------