八皇后递归算法无法实现递归
发布网友
发布时间:2024-04-14 10:24
我来回答
共1个回答
热心网友
时间:2024-04-29 01:59
你的思路有问题,递归算法是不需要你重置的,你只要搞清楚递归关系就行了。
你会全排列算法吗,这个问题其实就是8个数的全排列问题,每一行只选一个数,012。。。7,8行全排列有多少?
如果我求得固定第一位后的排列,那么全部排列就可以求出,固定第一位有8种可能,可以循环求得。
如果我求得固定第二位后的排列,固定第一位后的排列就可以求出,固定第二位有7种可能,可以循环求得。
。。。
如果我求得固定第8位后的排列,固定第7位后的排列就可以求出,固定第8位有1种可能,可以循环求得。
这很明显是递归的算法。
#include <stdio.h>
#include <stdlib.h>
#define max 8
intqueen[max],sum=0;/* max为棋盘最大坐标 */
voidshow()/* 输出所有皇后的坐标 */
{
inti;
for(i =0;i <max;i++)
{
printf("(%d,%d) ",i,queen[i]);
}
printf("\n");
sum++;
}
intcheck(intn)/* 检查当前列能否放置皇后 */
{
inti;
for(i =0;i <n;i++)/* 检查横排和对角线上是否可以放置皇后 */
{
if(queen[i]==queen[n]||abs(queen[i]-queen[n])==(n -i))
{
return1;
}
}
return0;
}
voidput(intn)/* 回溯尝试皇后位置,n为横坐标 */
{
inti;
for(i =0;i <max;i++)
{queen[n]=i;/* 将皇后摆到当前循环到的位置 */
if(!check(n))
{
if(n ==max -1)
{
show();/* 如果全部摆好,则输出所有皇后的坐标 */
}
else
{
put(n +1);/* 否则继续摆放下一个皇后 */
}
}
}
}
intmain()
{
put(0);/* 从横坐标为0开始依次尝试 */
printf("%d",sum);
system("pause");
return0;
}
八皇后递归算法无法实现递归
如果我求得固定第8位后的排列,固定第7位后的排列就可以求出,固定第8位有1种可能,可以循环求得。这很明显是递归的算法。include <stdio.h> include <stdlib.h> define max 8 intqueen[max],sum=0;/* max为棋盘...
关于八皇后递归转化为非递归问题
给你个用递归与非递归算法解决八皇后的问题的程序把 代码如下:include<iostream> using namespace std;static int count;class huanghou { private:int *path;int p[8];public:huanghou();~huanghou();bool place(int...
递归回溯算法解决八皇后问题
说明:理论上应该创建一个二维数组来表示棋盘,但是实际上可以通过算法,用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行,即第几个皇后,arr[i] = val , ...
求PASCAL递归八皇后程序,加解析,要在FREE PASCAL上过了的,事后给分_百...
这样如果我们在第i行第j列上放置了皇后,则只要设置:a[j]=False;c[i-j]=False;b[i+j]=False;就可以解决是否被攻击的问题。为了方便起见我们把数组a、b、c的下标说明为子界类型-n+1..2*n。数组x记录每组解...
八皇后问题
八皇后问题最简单的串行解法为如下的递归算法: (2.1)深度递归函数: go(int step,int column) {int i,j,place; row[step]=column; if (step==8) outputresult( ); /*结束递归打印结果*/ else /*继续递归*/ {for(place=1...
关于PASCAL的经典题目
一、回溯算法 回溯算法是所有搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头”思想作为其控制结构,其相当于采用了先根遍历的方法来构造解答树,可用于找解或所有解以及最优解。具体的算法描述如下:[非递归算法]<Type> ...
八皇后问题求解方法分类
try(1);{从第1个皇后开始放置} end.“八皇后”问题递归法求解 (C语言)#i nclude "stdio.h"static char Queen[8][8];static int a[8];static int b[15];static int c[15];static int iQueenNum=0; //...
八皇后递归算法 求解空间复杂度
因为每递归一层,只是增加一个形式变量的空间,以及递归返回地址的开销。而且在八皇后问题来说,递归深度最大为9层。若是N皇后问题,则空间复杂度也仅是O(N),且系数挺小的。所以说,在这里空间复杂度不是一个大的问题...
【八皇后问题】我自己写的,感觉能通,检查没有语句错误,但运行后直接...
你可以使用调试看看自己代码运行的过程,八皇后是关于深度优先的递归算法(DFS)。include <stdio.h> include <math.h> define QUEEN 8 int count=0;int queen[QUEEN]; // 存放每一列的列数 void Output(int queen[...
八皇后c++源码讲解
回溯法在理论上来说,就是在一棵搜索树中从根结点出发,找到一条达到满足某条件的子结点的路径.在搜索过程中,对于每一个中间结点,他的位置以及向下搜索过程是相似的,因此完全可以用递归来处理.典型的例子就是著名的"八皇后问题". "八...