摘要

总结递归问题框架的使用，通过三个题来掌握递归的构造和解决问题的思路。

递归使用核心框架总结：
Dfs（） 传递参数 一般问题规模n，和根据问题进行变动的(x,y)或者当前值yIf（）满足任务终止时最后一刻的状态，用来输出解{}For（）用来遍历下一步状态的全部可能值或者方向If（） 是否满足条件继续深入dfsDfs通过核心框架面对使用任何的dfs问题或者其他类似回溯问题可能以这个模板去套入

问题一 n皇后问题

皇后之前不能相互在同一行同一列或者对角线上，通过问题输入规模n确定多少只皇后在n*n的棋盘上输出不会互相攻击的摆放方式

实现方法；
使用dfs遍历所有的可能，如果不满足则回退，
首先是实现判断条件，判断某个皇后与之前的皇后是否发生冲突，如果发生，则这个位置不能摆
放，使用一个一维数组，x[depth]=col,如果在不同行上同一列的值一样则是冲突，且在遍历的时
候一行放一个皇后如果不冲突直接跳到下一行，另一个判断条件是不能对角线冲突，使用
abs(x[i]-x[depth])==abs(i-depth)    depth是当前深度，遍历之前全部n皇后的位置，也就
是i，计算是否在对角线上。第二个是for训练遍历，表示尝试第几列，一维数组记录当前第几行
放入了第几列 a[depth]=col 满足条件继续深入dfs（）整体框架Dfs（）If(是否走到了最后一行){输出}For(遍历尝试每一列)X[depth]=i 进行标记当前行n皇后存储在第i列If(不影响之前的n-1个皇后继续深入遍历)Dfs()

代码

#include 
#include 
#include 
#include 
using namespace std;//用一维数组存储，解决行冲突，数组下标为行数，数组值为列数
int x[10] = {0};
bool found=false;
int res=0;
int map[10][10] =           
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
bool judge(int depth) //判断第k行某个皇后是否发生冲突 ，发生冲突就跳过
{	int i = 1;while (i < depth) //循环i到k-1之前的皇后；{if (x[i] == x[depth] || abs(x[i] - x[depth]) == abs(i - depth)) //存在列冲突或者存在对角线冲突（实际上就是一种剪枝）return false;i++;}return true;
}void dfs(int n, int depth)
{	if (depth > n) //找到一组解{found = true;res++;if(res==1){for (int i = 1; i <= n; i++){map[i-1][x[i]-1]=1;}}return;}for (int i = 1; i <= n; i++) //尝试放置在第depth行的第i列{x[depth] = i;if (judge(depth))dfs(n, depth + 1);}}
void showmap(int n)
{for (int i = 0; i < n; i++)  {for (int j = 0; j < n; j++)cout <<' '<int n;cout << "请输入你的n皇后";cin >> n; dfs(n, 1);if(found)showmap(n);elsecout<<"无解";system("pause");
}

问题总结

n皇后问题与走迷宫这种问题是不同的，走迷宫始终是一个点在地图上走动，不考虑之前点带来的影响(只有访问和未访问的点)，所以在遍历阶段n皇后是先判断满足条件继续深入遍历，迷宫等其他问题是先深度遍历在判断走的点是否越界。主要是因为n皇后主要考虑n-1个皇后之前的影响在决定位置，

n皇后在存储皇后过程中使用一维数组存储，利用一维数组x[depth]=col的特性可以进行问题优化，无论是判断列冲突还是对角线冲突都十分方便。不需要用二维数据存储n皇后位置。

由于使用for循环遍历每一列，通过dfs深入遍历每一行，使得不需要设置是否访问过的存储矩阵，是不同于其他dfs问题的操作。

在dfs过程中只需要传递二个参数，一个是问题规模n，另一个是depth代表当前第几行，通过在传递参数中使用depth+1的操作，整个递归函数中不需要有return和在代码中dfs下面有任何的撤回操作

问题二 相邻和素数问题

素数问题，在nn的方格里，填充1~nn个数，使得每一行和每一列中任意一对相邻元素之和为素数

实现方法；
首先实现判断条件，需要考虑四种情况，在二维矩阵中，第一种情况是最初的(0,0)点，是合规
的，第二种情况就是第一行判断素数只需要与左边的元素相加是素数就可以，第三种情况是在第一
列的时候只需要判断与上面的元素相加为素数，第四种情况是需要判断与左边元素相加和上一个元
素相加都为素数。在dfs结构中用一个for循环尝试1~n*n种值在一个位置上全部的可能指，在循环的过程中也需要标
记那些数已经使用过了，这个数不在使用，在for循环内部用y=y+1,一次向右移动一个位置，并且
如果移动到最右边则下一位移动为下一行的第一个位置上，这样就能遍历全部的位置。利用dfs遍
历就可以组合出在n*n的网格上每一个位置上都有n种值的可能组合了，搜索到合适的组合就快速
退出。整体框架Dfs（）If(找到合适的最后一种情况，是在超出行的第一列的位置上){输出}For(遍历每一种值)If(检查这个数是否使用过){用二维矩阵记录当前位置上的值If(判断这个点与前一个位置相加是否为素数有四种情况)位置向右移动，加上判断如果移动最右列则下一次移动为下一行的第一列标记此数已使用Dfs（）撤回此点已使用位置撤回一步
}

代码

#include 
#include 
#include 
#include 
using namespace std;#define N 10int isp[N * N * 2];
int isu[N];
int a[N][N];
int solve=0;
int map[10][10] =           
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
int is_prime(int n)  
{int i;int flag = 0;for (i = 2; i <= (int)sqrt(n) + 1;i++){if (n%i == 0){return 0;}}return 1;
}bool judge(int x,int y,int n)
{if(x==0&&y==0)return true; else if(x==0&&y!=0){return isp[a[x][y-1] + a[x][y]]==1;}else if(x!=0&&y==0){return isp[a[x-1][y] + a[x][y]]==1;}else{return (isp[a[x-1][y] + a[x][y]]==1)&&(isp[a[x][y-1] + a[x][y]]==1);}
}void show(int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cout << a[i][j] << " ";}cout << endl;}cout<if (x == n && y == 0){solve++;if(solve==1){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){map[i][j]=a[i][j];}cout << endl;}cout << endl;}return;}else{	if(solve==1)return;cout<if(isu[i]==0){a[x][y] = i;show(n);if (judge(x,y,n)){y=y+1;if(y==n){y=y%n;x=x+1;}isu[i]=1;dfs(n, x, y);isu[i]=0;		a[x][y] = 0;y=y-1;if(y<0){y=y+n;x=x-1;}}}}}}
void showmap(int n)
{for (int i = 0; i < n; i++)  {for (int j = 0; j < n; j++)cout <<' '<int n;cout << "请输入你的矩阵大小"<> n;for (int i = 2; i <= 2 * n * n; i++)isp[i] = is_prime(i);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){a[i][j] = 0;}}cout<<"输出中间过程"<

实现方法；
使用dfs的方式能够遍历骑士的八个方向，从0,0点出发，判断条件是判断是否越界和是否被访问过，判断出界只需要检查当前(x,y)坐标是否小于0或者大
于最长边的n来判断，是否访问通过设置一个二维矩阵0代表为未访问其他代表访问过，通过判断当
前位置是否出界和访问来决定是否要继续深入遍历，使用depth记录当前所在步数，每走一步，
depth加一和在地图上标记此时的(x,y)所在的点标记访问过，chess[x][y]=depth，然后再遍历
骑士的八个方向整体框架Dfs()If(满足条件退出){}If(判断当前点是否出界){进行标记和步数加一For(遍历八个方向){Dfs()}}

#include 
#include 
#include 
#include 
#include 
using namespace std;
int depth = 0; //统计走的顺序
bool found=false;
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};//棋盘初始化为0做标记
int chress[10][10] =           
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
bool ifOut(int x, int y, int n)  //判断是否出界
{if (x >= 0 && x <= n-1 && y >= 0 && y <= n-1)return false;elsereturn true;
}
bool ifVisited(int x, int y) //判断是否已经被访问
{if (chress[x][y] != 0)return true;elsereturn false;
}void dfs(int x,int y, int n)
{if (depth >= n*n) //找到一组解{found = true;return;}if (!ifVisited(x, y) && !ifOut(x, y, n)){depth++;chress[x][y] = depth;for (int i = 0; i < 8; i++){dfs(x + dx[i], y + dy[i], n);}}}
void showmap(int n)
{for (int i = 0; i < n; i++)  //输出打印测试{for (int j = 0; j < n; j++)cout << setw(2)<	int n;cout<<"请输入骑士地图n"<>n; int x=0, y=0;dfs(x,y,n);if (found){showmap(n);}elsecout<<"无解"; system("pause");
}