PAT-递归

递归

一、分治

二、递归

其中重要的是①递归边界：用来返回最简单底层的结果②递归式：用来减少数据规模并向下一层递归

三、例

1.全排列

#include <iostream>
#include<cstdio>
using namespace std;
const int maxn = 11;

//P为当前排列,hashtable记录整数是否已经在P中
int n, P[maxn], hashTable[maxn] = { false };

//当前处理排列的第index位
void generateP(int index)
{
	//递归边界，已经处理完排列的1~n位
	if (index == n + 1)
	{
		for (int i = 1;i <= n;i++)
		{
			//输出当前排列
			printf("%d", P[i]);
		}
		printf("
");
		return;
	}

	//枚举1~n，试图将x填入P[index]
	for (int x = 1;x <= n;x++)
	{
		//如果x不存在P[0]~P[index]中
		if (hashTable[x] == false)
		{
			//令P的第index位为x，即把x加入当前排列
			P[index] = x;
			//记x已在P中
			hashTable[x] = true;
			//处理排列的第index+1位
			generateP(index + 1);
			//已处理完P[index]为x的子问题，还原状态
			hashTable[x] = false;
		}
	}
}

int main()
{
	//欲输出1~3的全排列
	n = 3;
	//从P[1]开始填
	generateP(1);

	return 0;
}

2.n皇后问题

朴素算法(暴力法)：枚举所有情况，然后判断每一种情况是否合法的做法

//先采用全排列对皇后所在的行数进行排列
//再对排列数进行判断，记录合法的次数

#include <iostream>
#include<cstdio>
using namespace std;
const int maxn = 11;

//P为当前排列,hashtable记录整数是否已经在P中,count记录合法的方案数
int num = 0, n, P[maxn], hashTable[maxn] = { false };

//当前处理排列的第index位
void generateP(int index)
{
	//递归边界，生成一个排列
	if (index == n + 1)
	{
		//flag为true表示当前排列为一个合法方案
		bool flag = true;
		//遍历任意两个皇后
		for (int i = 1;i <= n;i++)
		{
			for (int j = i + 1;j <= n;j++)
			{
				//如果在一条对角线上，不合法
				if (abs(i - j) == abs(P[i] - P[j]))
				{
					flag = false;
				}
			}
		}
		//若当前方案合法，令num加1
		if (flag)num++;
		return;
	}

	for (int x = 1;x <= n;x++)
	{
		if (hashTable[x] == false)
		{
			P[index] = x;
			hashTable[x] = true;
			generateP(index + 1);
			hashTable[x] = false;
		}
	}
}

回溯法：在到达递归边界前的某一层，由于一些事实导致已经不需要往任何一个子问题递归，就可以直接返回到上一层

//先采用全排列对皇后所在的行数进行排列
//在进行排列时进行判断，不去枚举无效的方案
//对进行到最后的方案进行计数，即合法的方案数

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 11;

//P为当前排列,hashtable记录整数是否已经在P中,count记录合法的方案数
int num = 0, n, P[maxn], hashTable[maxn] = { false };

//当前处理排列的第index位
void generateP(int index)
{
	//递归边界，生成一个合法方案
	if (index == n + 1)
	{
		//能到达这里的一定是合法的
		num++;
		return;
	}

	//第x行
	for (int x = 1;x <= n;x++)
	{
		//第x行还没有皇后
		if (hashTable[x] == false)
		{
			//flag为true表示当前皇后不会和之前的皇后冲突
			bool flag = true;

			//遍历之前的皇后
			for (int pre = 1;pre < index;pre++)
			{
				//第index列皇后的行号为x，第pre列皇后的行号为P[pre]
				if (abs(index - pre) == abs(x - P[pre]))
				{
					//与之前的皇后在一条对角线上，冲突
					flag = false;
					break;
				}
			}

			//如果可以把皇后放在第x行
			if (flag)
			{
				//令第index列皇后的行号为x
				P[index] = x;
				//第x行已被占用
				hashTable[x] = true;
				//递归处理第index+1行皇后
				generateP(index + 1);
				//递归完毕，还原第x行为未占用
				hashTable[x] = false;
			}
		}
	}

}

参考-算法笔记-胡凡