n皇后问题c语言代码_求n的阶乘java代码

n皇后问题c语言代码_求n的阶乘java代码问题描述:有一个n*n的棋盘,在这个棋盘中放n个皇后,使得这n个皇后,任意两个皇后不在同一行,同一列,同一条对角线。例如,当n等于4时,有两种摆法。输入只有一个整数n。思路如果我们是从这个n*n这个棋盘中选取n个方格放皇后,再去判断是否满足条件的话,则效率会非常低,这是一个组合数∁\complement∁nn∗nn\atopn*nn∗nn​,当n等于8时,就要枚举54502232次…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

问题描述:

有一个n*n的棋盘,在这个棋盘中放n个皇后,使得这n个皇后,任意两个皇后不在同一行,同一列,同一条对角线。例如,当n等于4时,有两种摆法。
图
输入只有一个整数n。

思路

如果我们是从这个n*n的棋盘中选取n个方格放皇后,再去判断是否满足条件的话,则效率会非常低,这是一个组合数 ∁ \complement n n ∗ n n \atop n*n nnn,当n等于8时,就要枚举54502232次

方法一:递归暴力法

做这个题之前,我们回想一下字符串全排列,这个和它相似,可以枚举每一行的列数,枚举完一个棋盘后,判断任意两个皇后是否在同一条线上,例如上面的摆法1(2413).这个方法的复杂度为n!

代码
#include<stdio.h>
#include<math.h>
int rank[15];//pos列i行 
bool vis[15];//标记第i行是否走过
int n,cnt=0;
void dfs(int pos){ 
   
	if(pos==n+1){ 
   
		bool flag=true;
		for(int i=1;i<=n;i++){ 
   
			bool flag2=true;
			for(int j=i+1;j<=n;j++){ 
   //枚举任意两个皇后 
				if(abs(i-j)==abs(rank[i]-rank[j])){ 
   //两个皇后处于一条对角线 
					flag=false;
					flag2=false;
					break;
				}
			}
			if(flag2==false)	break;//如果一个填满情况对角线有两个或以上,则直接跳出循环 
		}
		if(flag)	cnt++;
		return;
	}
	for(int i=1;i<=n;i++){ 
   //枚举每一行 
		if(vis[i]==false){ 
   //第i行没走过 
			rank[pos]=i;//pos列在i行 
			vis[i]=true;
			dfs(pos+1);//递归下一列 
			vis[i]=false;
		}
	}
}
int main(){ 
   
	scanf("%d",&n);
	dfs(1);//从第一列开始枚举 
	printf("%d",cnt);
	return 0;
}
方法二:递归回溯法

上面的方法一是当形成一个n*n的棋盘时,才去判断是否满足条件。
而我们在递归时,可以提前判断是否满足条件,如果不满足,则不用递归下去,返回上一层进行处理,这种方法称为回溯法。这个题是当我们递归的时候就去判断当前的皇后是否和前面的皇后在一条对角线上,如果在一条直线上,就不需要递归下去了,返回上一层;如果不在,就继续递归,下一个继续进行判断,直到满足条件为止。

代码
#include<stdio.h>
#include<math.h>
int rank[20];
bool vis[20];
int n,cnt=0;
void dfs(int pos){ 
   
	if(pos==n+1){ 
   //递归边界条件 
		cnt++;
		return;
	}
	for(int i=1;i<=n;i++){ 
   //枚举每行 
		if(vis[i]==false){ 
   
			bool flag=true;
			for(int j=1;j<pos;j++){ 
   //枚举pos之前的皇后 
				if(abs(pos-j)==abs(i-rank[j])){ 
   
					flag=false;
					break;
				}
			}
			if(flag){ 
   
				rank[pos]=i;//pos列在i行 
				vis[i]=true;
				dfs(pos+1); 
				vis[i]=false;
			}
		}
	}
}
int main(){ 
   
	scanf("%d",&n);
	dfs(1);
	printf("%d",cnt);
	return 0;
} 
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187628.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • python中fillna_python – 使用groupby的Pandas fillna

    python中fillna_python – 使用groupby的Pandas fillna我试图使用具有相似列值的行来估算值.例如,我有这个数据帧one|two|three111011nan11nan12nan122012nan13nan13nan我想使用列[‘one’]和[‘two’]的键,这是相似的,…

  • shuffle洗牌算法java_洗牌算法shuffle[通俗易懂]

    洗牌算法1.背景阿里的面试的时候做的一道笔试题:题目:写一个方法,入参为自然数n(n>0),返回一个自然数数组,数组长度为n,元素为[1,n]之间,且每个元素不重复,数组中各元素顺序要求随机;实例1:输入:N=3输出:132实例2:输入:N=5输出:32514当时我的解法(写了两种方法):写的好烂,面完和面试官交流的时候面试官让我看下Collect…

  • 【python实战】不让我复制?看我自制个带文字识别的截屏工具

    【python实战】不让我复制?看我自制个带文字识别的截屏工具人生苦短,我用python

  • 简单介绍T检验和卡方检验「建议收藏」

    简单介绍T检验和卡方检验「建议收藏」最近在看统计学方面的知识,正好有个学妹问我一些检验方面的东西,以前读书那会的统计学知识早已忘记,经过半天的努力,又把知识给拾起来了,下面简单介绍下T检验和卡方检验。1. T检验适用范围:主要用于样本含量较小(例如n总体标准差σ未知的正态分布。其中最常用的是单总体t检验,单总体t检验是检验一个样本平均数与一个已知的总体平均数的差异是否显著。当总体分布是正态分布,如总体标准差未知

  • Weblogic SSRF漏洞[通俗易懂]

    Weblogic SSRF漏洞[通俗易懂]1.漏洞描述weblogic中存在SSRF漏洞,利用该漏洞可以发送任意HTTP请求,进而攻击内网中redis、fastcgi等脆弱组件。2.影响版本weblogic10.0.2–10.3.6版本3.POChttp://192.168.42.145:7001/uddiexplorer/SearchPublicRegistries.jsp?rdoSearch=name&txtSearchname=sdf&txtSearchkey=&txtSear…

  • 汇编语言转换成C语言软件_archlinux

    汇编语言转换成C语言软件_archlinux从ARMv8-A开始出现了64位的ARM指令集:Aarch64。

    2022年10月16日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号