递归（全排列andN皇后）

全排列

分治与递归

递归是实现分治的一种方法

思想思路

题目：

全排列i

我这样直接输出会多输出一个空行（最后一个\n）

#include<stdio.h>

using namespace std;
const int maxn=10;
int an[maxn];
int n;
bool hash[maxn]={0};
int c=0;
void pl(int index)
{
	if (index>n-1)
{
	for (int i=0;i<n-1;i++)
	printf("%d ",an[i]);
	printf("%d",an[n-1]);
	 printf("\n");
	return;
	}		 
	for(int i=1;i<=n;i++)
	{
		if (!hash[i])
		{
			an[index]=i;
			hash[i]=1;
			pl(index+1);
			c++;
			hash[i]=0;
		}
	}
 } 
 int main()
 {
 	scanf("%d",&n);pl(0);
 }

使用vector存储，在最后一格时不输出

 参考解答

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 8 + 1;
vector<vector<int> > result;
vector<int> temp;
int n;
bool used[MAXN] = {false};

void DFS(int idx) {
    if (idx == n + 1) {
        result.push_back(temp);
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            temp.push_back(i);
            used[i] = true;
            DFS(idx + 1);
            used[i] = false;
            temp.pop_back();
        }
    }
}

int main() {
    scanf("%d", &n);
    DFS(1);
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            printf("%d", result[i][j]);
            printf(j + 1 < result[i].size() ? " " : "\n");
        }
    }
    return 0;
}

 我也改好了

#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=10;
//int an[maxn];
vector<vector<int> > ans;
vector<int> temp;
int n;
bool hasha[maxn]={0};
int c=0;
void pl(int index)
{
	if (index>n-1)
{
//for(int j=0;j<temp.size();j++)printf("%d ",temp[j]);
	ans.push_back(temp);
//	for (int i=0;i<n-1;i++)
//	printf("%d ",an[i]);
//	printf("%d",an[n-1]);
//	 printf("\n");
//	return;
	}		 
	for(int i=1;i<=n;i++)
	{
		if (!hasha[i])
		{
			temp.push_back(i);
			hasha[i]=1;
			pl(index+1);
			hasha[i]=0;
			temp.pop_back();
//			an[index]=i;
//			hash[i]=1;
//			pl(index+1);
//			c++;
//			hash[i]=0;
		}
	}
 } 
 int main()
 {
 	scanf("%d",&n);pl(0);
 	for(int i=0;i<ans.size();i++)
 	{
 		for(int j=0;j<n;j++)
 		{
 			printf("%d",ans[i][j]);
             if (j<n-1)printf(" ");
		 }
		if(i<ans.size()-1)printf("\n");
	 }
	
 	
 }

N皇后

判断8皇后

弃用数组，研究vector的用法搞了半天关于vector的一些菜鸟吐槽-CSDN博客

首先弄明白bool

true是1，false是0

用了二维vector，加上各种边界条件总算搞出来了

可是时间复杂度on3

#include<stdio.h>
#include<vector>
#include<iostream>
using namespace std;
int n=8;
vector<vector<int> > a=vector<vector<int> >(8, vector<int>(8, 0));;
// vector<vector<int> > board = vector<vector<int> >(8, vector<int>(8, 0));

int jud(int n,vector<vector<int> > a)//??
{int sum1=0,sum2=0;

	for(int i=0;i<n;i++)
	{sum1=0;sum2=0;
		for(int j=0;j<n;j++)
		{sum1+=a[i][j];sum2+=a[j][i];
//行和为1，列和为1

//		printf("##??--%d%d%dn%dj%d-\n",i,sum1,sum2,n,j)	;
			if(a[i][j]==1)
			{
			
			for(int k=0;k<n;k++)
			{
			
					if(i+j-k<n&&i+j-k>=0&&i+j-k!=i)
				{
					if(a[i+j-k][j]==a[i][j])
					{return false;}
				}
				if(k+j-i<n&&k+j-i>=0&&k!=i)
				{
					if(a[k][k+j-i]==a[i][j])
					{return false;}
				}
			}
			}
			else if (a[i][j]!=0) 					{return false;}

//		printf("#--%d%d%d-\n",i,sum1,sum2)	;
		}
		
	
if(sum1!=1||sum2!=1) 					{return false;}

}
return true;}
int main()
{
int n1=8;
int ins;
int b[n1][n1];
//printf("%d %d",bool(true),bool(false));
		for(int i=0;i<n1;i++)
		for(int j=0;j<n1;j++)
		{scanf("%d",&ins);a[i][j]=ins;}
//printf("%d",jud(n1,a));
if(jud(n1,a))printf("YES"); else printf("NO");
}

事实上答案只用了1-D数组（1的单坐标），并且遍历比我少一半（j>i）即可，减少重复

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

bool isValidQueenPlacement(const vector<vector<int>>& board) {
    int n = board.size();
    vector<int> positions(n, -1); // positions[i] 表示第 i 行的皇后所在的列

    // 遍历棋盘，找出所有皇后的位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 1) {
                positions[i] = j;
            }
        }
    }

    // 检查皇后之间的冲突
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 检查是否有两个皇后在同一列
            if (positions[i] == positions[j]) {
                return false;
            }
            // 检查是否有两个皇后在同一对角线上
            if (abs(positions[i] - positions[j]) == abs(i - j)) {
                return false;
            }
        }
    }

    return true;
}

int main() {
    vector<vector<int>> board = vector<vector<int>>(8, vector<int>(8, 0));

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cin >> board[i][j];
        }
    }

    cout << (isValidQueenPlacement(board) ? "YES" : "NO") << endl;

判断这里也巧用绝对值

 不过他没有判断皇后同行，似乎是包含在这两个之中了。？

N皇后

·和全排列一样，需要使用hashtable记录某个数字是否被使用

这个错代码看了好多遍了，愣是没发现错在哪

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int N=9;
vector<vector<int> > a;
vector<int> temp;
int hashe1[N+2]={0};
void  p(int index,int n)
{
	if (index==n)
	{printf("?");
		a.push_back(temp);
	}
	for(int i=1;i<n;i++)
	{
		if(hashe1[i]==0)
			for (int j=0;j<index;j++)
			{
			temp.push_back(i);
			hashe1[i]=1;
			p(index+1,n);
			hashe1[i]=0;
			temp.pop_back();		
			}

			}
	}
			
			

	

//}
int main()
{int n=8;
p(0,n);printf("%d",a.size());
}

，对比我自己上次写的全排列，才发现是循环多套了一层。构造排列之后直接判断+pushback还原现场一系列操作即可，但是你却多搞了个j从1-n？

改了还是错

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int N=9;
vector<vector<int> > a;
vector<int> temp;
int hashe1[N+2]={0};
void  p(int index,int n)
{
	if (index==n)
	{printf("?");
		a.push_back(temp);
	}
	for(int i=1;i<n;i++)
	{
		if(hashe1[i]==0)
		
			{
			temp.push_back(i);
			hashe1[i]=1;
			p(index+1,n);
			hashe1[i]=0;
			temp.pop_back();		
			}

			
	}
}
			
			

	

//}
int main()
{int n=8;
p(0,n);printf("%d",a.size());
}

艹！少了个等于！i从1~n，我写的i<n...

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int N=9;
vector<vector<int> > a;
vector<int> temp;
int hashe1[N+2]={0};
void  p(int index,int n)
{
	if (index>n-1)
	{printf("?");
		a.push_back(temp);
	}
	for(int i=1;i<=n;i++)
	{
		if(hashe1[i]==0)
		
			{
			temp.push_back(i);
			hashe1[i]=1;
			p(index+1,n);
			hashe1[i]=0;
			temp.pop_back();		
			}

			
	}
}
			
			

	

//}
int main()
{int n=8;
p(0,n);printf("%d",a.size());
}

 这下至少构造排列部分对了

 然后输出还是0，崩了

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int N=9;
vector<vector<int> > a;
vector<int> temp;
int hashe1[N+2]={0};
bool flag=0;
//bool j(vector<int> a)
//{
//	for(int i=0;i<a.size();i++)
//	{//不用判断同行同列，因为造出了是排列
//	for(int j=i+1;i<a.size();j++)
//	{
//		if(abs(a[j]-a[i])==j-i) return false;
//	 } 
//	}
//	return true;
// } 
void  p(int index,int n)
{
	if (index==n)
	{
		a.push_back(temp);return;
	}
	for(int i=1;i<=n;i++)
	{
		if(hashe1[i]==0)
	
		{
		if(index==0)
		{
			temp.push_back(i);
			hashe1[i]=1;
			
			p(index+1,n);
		
			hashe1[i]=0;
			temp.pop_back();
		}
		else{
			//printf("?");
//			flag=0;
			for(int k=0;k<index;k++)
			{//printf("**%d %d %d %d.\n",k,index,temp[k],i);
					if(abs(i-temp[k])==abs(index-k)) 
				{//printf("*%d %d %d %d.\n",k,index,temp[k],i);
				flag=1;break;}
			}
				if(!flag)
				{//printf("**");
			temp.push_back(i);
			hashe1[i]=1;
			p(index+1,n);
			hashe1[i]=0;
			temp.pop_back();
					
				}
					
				

			}
	}
			
			
		}
	}
	

//}
int main()
{int n=8;
p(0,n);printf("%d",a.size());
}

竟是因为少了个flag归零。蹦

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int N=9;
vector<vector<int> > a;
vector<int> temp;
int hashe1[N+2]={0};
bool flag=0;
//bool j(vector<int> a)
//{
//	for(int i=0;i<a.size();i++)
//	{//不用判断同行同列，因为造出了是排列
//	for(int j=i+1;i<a.size();j++)
//	{
//		if(abs(a[j]-a[i])==j-i) return false;
//	 } 
//	}
//	return true;
// } 
void  p(int index,int n)
{
	if (index==n)
	{
		a.push_back(temp);return;
	}
	for(int i=1;i<=n;i++)
	{
		if(hashe1[i]==0)
	
		{
		if(index==0)
		{
			temp.push_back(i);
			hashe1[i]=1;
			
			p(index+1,n);
		
			hashe1[i]=0;
			temp.pop_back();
		}
		else{
			//printf("?");
			flag=0;//这句话害我浪费一个晚上
			for(int k=0;k<index;k++)
			{//printf("**%d %d %d %d.\n",k,index,temp[k],i);
					if(abs(i-temp[k])==abs(index-k)) 
				{//printf("*%d %d %d %d.\n",k,index,temp[k],i);
				flag=1;break;}
			}
				if(!flag)
				{//printf("**");
			temp.push_back(i);
			hashe1[i]=1;
			p(index+1,n);
			hashe1[i]=0;
			temp.pop_back();
					
				}
					
				

			}
	}
			
			
		}
	}
	

//}
int main()
{int n=8;
p(0,n);printf("%d",a.size());
}

 

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/689324.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

IP SSL使用率增长有利于网络安全防护！

IP SSL使用率增长有利于网络安全防护！

目录 IP的特殊性 IP证书的作用原理&#xff1a; 申请IP证书的基本条件&#xff1a; 申请IP SSL证书&#xff1a; 对于SSL证书来说&#xff0c;很多朋友应该并不陌生&#xff0c;目前SSL证书广泛应用在域名服务器上&#xff0c;所以大家最熟悉的证书类型可能就是单域名SSL证…
阅读更多...
MeiliSearch-轻量级且美丽的搜索引擎

MeiliSearch-轻量级且美丽的搜索引擎

MeiliSearch-轻量级且美丽的搜索引擎 MeiliSearch 是一个功能强大、快速、开源、易于使用和部署的搜索引擎。它具有以下特点&#xff1a; 支持中文搜索&#xff1a;MeiliSearch 对中文有良好的支持&#xff0c;不需要额外的配置。高度可定制&#xff1a;搜索和索引都可以高度…
阅读更多...
UE4获取动画序列资产的动画时长

UE4获取动画序列资产的动画时长

谢谢”朝闻道“大佬的指点~
阅读更多...
数据脱敏技术方案选择（word）

数据脱敏技术方案选择（word）

1 概述 1.1 数据脱敏定义 1.2 数据脱敏原则 1.2.1基本原则 1.2.2技术原则 1.2.3管理原则 1.3 数据脱敏常用方法 3.1.1泛化技术 3.1.2抑制技术 3.1.3扰乱技术 3.1.4有损技术 1.4 数据脱敏全生命周期 2 制定数据脱敏规程 3 发现敏感数据 4 定义脱敏规则 5 执…
阅读更多...
SpringCache和SpringTask

SpringCache和SpringTask

SpringCache 在启动类上加EnableCaching注解 我们只要在Controller上写一个SpringCache相应的注解 我们就能实现缓存了 简化缓存操作代码&#xff0c;提高我们的效率 我们默认是我们的spring做缓存 但我们还可以替换我们的缓存技术 例如 EhCache Google Redis 来作为…
阅读更多...
three.js指南

three.js指南

threejs 相关资料 threejs 官网threejs 案例 安装&#xff08;Installation&#xff09; 使用 NPM 和构建工具进行安装 对于大多数用户而已&#xff0c;从 npm 包注册表中心 安装并使用 构建工具 会是一个更推荐的方案。因为项目需要的依赖越多&#xff0c;就越有可能遇到静…
阅读更多...
1.vue2.x-初识及环境搭建

1.vue2.x-初识及环境搭建

目录 1.下载nodejs v16.x 2.设置淘宝镜像源 3.安装脚手架 4.创建一个项目 5.项目修改 代码地址&#xff1a;source-code: 源码笔记 1.下载nodejs v16.x 下载地址&#xff1a;Node.js — Download Node.js 2.设置淘宝镜像源 npm config set registry https://registry.…
阅读更多...
【PyTorch】PyTorch深度学习框架实战（二）：torchrun

【PyTorch】PyTorch深度学习框架实战（二）：torchrun

一、引言 PyTorch由facebook人工智能研究院研发&#xff0c;2017年1月被提出&#xff0c;是一个开源的Python机器学习库&#xff0c;基于Torch&#xff0c;用于自然语言处理等应用程序。PyTorch既可以看作加入了GPU支持的numpy&#xff0c;同时也可以看成一个拥有自动求导功能的…
阅读更多...
【iOS】MRC下的单例模式批量创建单例

【iOS】MRC下的单例模式批量创建单例

单例模式的介绍和ARC下的单例请见这篇&#xff1a;【iOS】单例模式 目录 关闭ARC环境MRC下的单例ARC下的单例批量创建单例Demo 关闭ARC环境 首先关闭ARC环境&#xff0c;即打开MRC&#xff1a; 或是指定某特定目标文件为非ARC环境&#xff1a; 双击某个类文件&#xff0c;指定…
阅读更多...
python的最小二乘法(OLS)函数

python的最小二乘法(OLS)函数

1、作用 pandas提供了一些很方便的功能&#xff0c;比如最小二乘法(OLS)&#xff0c;可以用来计算回归方程式的各个参数。 2、Python导出的OLS模型的结果 下面是如何解读Python导出的OLS模型的结果。 1. 回归系数&#xff1a; 代表每个自变量对因变量的影响程度&#xff0c…
阅读更多...
软件质量保障与测试 Lab2

软件质量保障与测试 Lab2

Lab2 12修改代码执行结果问题解决 3修改代码执行结果问题解决 1 klee 对 symbolic.c 生成文件的执行结果&#xff1a; 2 修改代码 头文件引用添加&#xff1a; #include <klee/klee.h>执行部分&#xff1a; 将原先的读入&#xff1a; int main() {maze[y][x] X;re…
阅读更多...
Wakeup Source框架设计与实现

Wakeup Source框架设计与实现

Wakeup Source 为系统组件提供了投票机制&#xff0c;以便低功耗子系统判断当前是否可以进入休眠。 Wakeup Source(后简称&#xff1a;WS) 模块可与内核中的其他模块或者上层服务交互&#xff0c;并最终体现在对睡眠锁的控制上。 1. 模块功能说明 WS的处理逻辑基本上是围绕 com…
阅读更多...
Python初步使用教程

Python初步使用教程

1.基本输出print函数 a10 b20 print(a)#输出结束后会自动换行 print(b) print(a,b,猪猪侠)#print中sep决定三者之间会存在空格#连接方法一 print(猪猪,end) print(侠) #连接方法二&#xff08;只能是字符串和字符串连&#xff09; print(超级无敌)print(chr(67)) print(ord(猪…
阅读更多...
内存经验分享

内存经验分享

目录 内存统计工具 /proc/meminfo Buddy ​​​​​​​​​​​​​​Slub ​​​​​​​Procrank /proc/pid/smaps ​​​​​​​Dumpsys meminfo 内存评估 内存泄漏 Lmk 水位调整 内存统计工具 /proc/meminfo 可以提供整体内存信息&#xff0c;各字段表示的意思如…
阅读更多...
Ant Design Pro

Ant Design Pro

一&#xff1a;Ant Design pro是什么&#xff1a; Ant Design Pro 是基于 Ant Design 和 umi 的封装的一整套企业级中后台前端/设计解决方案&#xff0c;致力于在设计规范和基础组件的基础上&#xff0c;继续向上构建&#xff0c;提炼出典型模板/业务组件/配套设计资源&#x…
阅读更多...
[linux] 上手新ubuntu机器的初始化工作(自用侵删)

[linux] 上手新ubuntu机器的初始化工作(自用侵删)

文章目录 环境类Vimzshother 应用类Typora激活环境准备解包替换文件app.asar激活Typora VsCodeextension.vscode乱码 WattToolkitQQWPS输入法:FcitxDeepin-wine : Wechat 环境类 Vim 直接贴配置 vim-Plug: let mapleader "," let g:mapleader "," le…
阅读更多...
攻防世界---misc---小小的PDF

攻防世界---misc---小小的PDF

1、题目描述&#xff0c;下载附件是一个PDF&#xff0c;打开之后是这样&#xff0c;有两页PDF 2、用winhex分析&#xff0c;没有发现奇怪的地方 3、在kali中binwalk发现有多张照片 4、接着使用foremost将图片分离出来&#xff0c; 5、得到3张图片&#xff0c;打开第3张图片&am…
阅读更多...
【TB作品】MSP430F5529 单片机，智能温控系统，DS18B20

【TB作品】MSP430F5529 单片机，智能温控系统，DS18B20

作品功能 本项目设计并实现了一个基于MSP430单片机的智能温控系统。系统可以实时显示当前温度&#xff0c;并且可以根据设置的临界值对环境进行加热或降温。主要功能如下&#xff1a; 实时显示当前温度。显示并调整温度临界值&#xff0c;临界值可在20~35摄氏度之间调节。当前…
阅读更多...
STM32-呼吸灯仿真

STM32-呼吸灯仿真

目录 前言: 一.呼吸灯 二.跑马灯 三. 总结 前言: 本篇的主要内容是关于STM32-呼吸灯的仿真,包括呼吸灯,跑马灯的实现与完整代码,欢迎大家的点赞,评论和关注. 接上http://t.csdnimg.cn/mvWR4 既然已经点亮了一盏灯,接下来就可以做更多实验了, 一.呼吸灯 在上一个的基础上…
阅读更多...
力扣560. 和为 K 的子数组

力扣560. 和为 K 的子数组

Problem: 560. 和为 K 的子数组 文章目录 题目描述思路复杂度Code 题目描述 思路 1.初始化一个哈希表preSum&#xff0c;用于记录前缀和及其出现次数,ans记录和为k的子数组数量、sum_i记录当前前缀和&#xff1b; 2.将前缀和为 0 的情况存入哈希表&#xff0c;表示前缀和为 0 出…
阅读更多...
最新文章

Copyright @ 2022~2023