12-Instances-of-recursion

Hanoi 问题

描述：法国数学家 Edouard Lucas 于 1883 提出的 Hanoi 塔问题，可形象地描述如下：

有 n 个中心带孔的圆盘贯穿在直立于地面的一根柱子上，各圆盘的半径自底而上不断缩小；
需要利用另一根柱子将它们转运至第三根柱子，但在整个转运的过程中，游离于这些柱子之外的圆盘不得超过一个 (即每次只能取一个)，且每根柱子上圆盘半径都须保持上小下大。试将上述转运过程描述为递归形式，并而实现一个递归算法。

递归版

将三根柱子分别记作 X、Y 和 Z，则整个转运过程可递归描述为：

为将 X 上的 n 个盘子借助 Y 转运至 Z，只需（递归地）
- 将 X 上的 n - 1 个盘子借助 Z 转运至 Y
- 再将 X 上最后一个盘子直接转移到 Z
- 最后再将 Y 上的 n - 1 个盘子借助 X 转运至 Z

按照这一理解，即可如下所示实现对应的递归算法：

// 按照Hanoi规则，将柱子Sx上的n只盘子，借助柱子Sy中转，移到柱子Sz上

void hanoi ( int n, Stack<Disk>& Sx, Stack<Disk>& Sy, Stack<Disk>& Sz ) {
	if ( n > 0 ) { //没有盘子剩余时，不再递归
		hanoi ( n - 1, Sx, Sz, Sy ); //递归：将Sx上的n - 1只盘子，借助Sz中转，移到Sy上
		move ( Sx, Sz ); //直接：将Sx上最后一只盘子，移到Sz上
		hanoi ( n - 1, Sy, Sx, Sz ); //递归：将Sy上的n - 1只盘子，借助Sx中转，移到Sz上
	}
}

关于时间复杂度，该算法对应的边界条件和递推式为： T(1) = O(1) T(n) = 2T(n - 1) + O(1)

若令: S(n) = T(n) + O(1) 则有: S(1) = O(2) S(n) = 2∙S (n - 1) = 2^2 ∙ S(n - 2) = 2^3 ∙ S(n - 3) = … = 2^(n-1) ∙ S(1) = 2n

故有： T(n) = O(2^n)

迭代版

// Iterative Algorithm
1. Calculate the total number of moves required 
	i.e."pow(2, n)- 1" here n is number of disks.

2. If number of disks (i.e. n) is even then interchange destination pole and auxiliary pole.

3. for i = 1 to total number of moves:
    if i%3 == 1:
	    legal movement of top disk between source pole and destination pole
    if i%3 == 2:
	    legal movement top disk between source pole and auxiliary pole    
    if i%3 == 0:
        legal movement top disk between auxiliary pole and destination pole

Let us understand with a simple example with 3 disks: So, total number of moves required = 2^3-1 = 7
When i=1, (i % 3 == 1) legal movement between ‘A’ and ‘C’
When i=2, (i % 3 == 2) legal movement between ‘A’ and ‘B’
When i=3, (i % 3 == 0) legal movement between ‘B’ and ‘C’
When i=4, (i % 3 == 1) legal movement between ‘A’ and ‘C’
When i=5, (i % 3 == 2) legal movement between ‘A’ and ‘B’
When i=6, (i % 3 == 0) legal movement between ‘B’ and ‘C’
When i=7, (i % 3 == 1) legal movement between ‘A’ and ‘C’
So, after all these destination poles contains all the in order of size.
After observing above iterations, we can think that after a disk other than the smallest disk is moved, the next disk to be moved must be the smallest disk because it is the top disk resting on the spare pole and there are no other choices to move a disk.

// C++ Program for Iterative Tower of Hanoi using STL

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

char rod[]={'S', 'A', 'D'};
vector<stack<int>> stacks(3); // 3 stacks for 3 rods

void moveDisk(int a, int b)
{
	if (stacks[b].empty() || (!stacks[a].empty() && stacks[a].top() < stacks[b].top()))
	{
		cout << "Move disk " << stacks[a].top() << " from rod " << rod[a] << " to rod " << rod[b] << "\n";
		stacks[b].push(stacks[a].top());
		stacks[a].pop();
	}
	else
		moveDisk(b, a);
}

void towerOfHanoi(int n)
{
	cout << "Tower of Hanoi for " << n << " disks:\n";

	int src = 0, aux = 1, dest = 2;
	for (int i = n; i > 0; i--)
		stacks[src].push(i);

	int totalMoves = (1 << n) - 1;
	if (n % 2 == 0)
		swap(aux, dest);

	for (int i = 1; i <= totalMoves; i++)
	{
		if (i % 3 == 0)
			moveDisk(aux, dest);
		else if (i % 3 == 1)
			moveDisk(src, dest);
		else
			moveDisk(src, aux);
	}
}

int main()
{
	int n = 3; // number of disks
	towerOfHanoi(n);
	return 0;
}

References

Related Articles

References:
http://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution

八皇后问题

八皇后问题

问题描述

国际象棋中皇后的势力范围覆盖其所在的水平线、垂直线以及两条对角线。现考查如下问题：在 n x n 的棋盘上放置 n 个皇后，如何使得她们彼此互不攻击——此时称她们构成一个可行的棋局。对于任何整数 n >= 4，这就是 n 皇后问题。由鸽巢原理可知，在 n 行 n 列的棋盘上至多只能放置 n 个皇后。反之，n 个皇后在 n x n 棋盘上的可行棋局通常也存在，比如图 b 即为在 8 x 8 棋盘上，由 8 个皇后构成的一个可行棋局。

皇后的实现
struct Queen { //皇后类
	int x, y; //皇后在棋盘上的位置坐标
	Queen ( int xx = 0, int yy = 0 ) : x ( xx ), y ( yy ) {};
	bool operator== ( Queen const& q ) const { //重载判等操作符，以检测不同皇后之间可能的冲突
	return ( x == q.x ) //行冲突（这一情况其实并不会发生，可省略）
			|| ( y == q.y ) //列冲突
			|| ( x + y == q.x + q.y ) //沿正对角线冲突
			|| ( x - y == q.x - q.y ); //沿反对角线冲突
}

bool operator!= ( Queen const& q ) const { 
	return ! ( *this == q ); } //重载不等操作符
};
算法实现

基于试探回溯策略，可如代码所示，实现通用的 N 皇后算法：
void placeQueens ( int N ) { //N皇后算法（迭代版）：采用试探/回溯策略，借助栈记录查找的结果
	Stack<Queen> solu; //存放（部分）解的栈
	Queen q ( 0, 0 ); //从原点位置出发
	do { //反复试探、回溯
		if ( N <= solu.size() || N <= q.y ) { //若已出界，则
			q = solu.pop(); q.y++; //回溯一行，并继续试探下一列
		} else { //否则，试探下一行
			while ( ( q.y < N ) && ( 0 <= solu.find ( q ) ) ) //通过与已有皇后的比对
			{ q.y++; nCheck++; } //尝试找到可摆放下一皇后的列
			if ( N > q.y ) { //若存在可摆放的列，则
				solu.push ( q ); //摆上当前皁后，并
				if ( N <= solu.size() ) nSolu++; //若部分解已成为全局解，则通过全局变量nSolu计数
				q.x++; q.y = 0; //转入下一行，从第0列开始，试探下一皇后
			}
		}
	} while ( ( 0 < q.x ) || ( q.y < N ) ); //所有分支均已或穷举或剪枝后，算法结束
}
既然每行能且仅能放置一个皇后，故不妨首先将各皇后分配至每一行。然后，从空棋盘开始，逐个尝试着将她们放置到无冲突的某列。每放置好一个皇后，才继续试探下一个。若当前皇后在任何列都会造成冲突，则后续皇后的试探都必将是徒劳的，故此时应该回溯到上一皇后。

这里借助栈 solu 来动态地记录各皇后的列号。当该栈的规模增至 N 时，即得到全局解。该栈即可依次给出各皇后在可行棋局中所处的位置。

实例

首先试探第一行皇后，如图 (a)所示将其暂置于第 0 列，同时列号入栈。接下来试探再第二行皇后，如图 (b)所示在排除前两列后，将其暂置于第 2 列，同时列号入栈。然而此后试探第三行皇后时，如图 (c)所示发现所有列均有冲突。于是回溯到第二行，并如图 (d)所示将第二行皇后调整到第 3 列，同时更新栈顶列号。后续各步原理相同，直至图 (l)栈满时得到一个全局解。

如此不断地试探和回溯，即可得到所有可行棋局。可见，通过剪枝我们对原规模为 4! = 24 的搜索空间实现了有效的筛选。随着问题规模的增加，这一技巧的优化效果将更为明显。
指向原始笔记的链接

迷宫问题

Circular transclusion detected: 1-Theory/1-Algorithm/02-DataStruct/dsa-cpp-deng/C-Stack+Queue/43-Probing-backtracking

🌰Senjl's Digital Garden🐉

探索

12-Instances-of-recursion

Hanoi 问题

递归版

迭代版

References

八皇后问题

八皇后问题

问题描述

皇后的实现

算法实现

实例

迷宫问题

关系图谱

目录

反向链接