c语言实现全排列并存储,C语言实现全排列和回溯法总结

分手后的思念是犯贱 2022-10-14 05:43 160阅读 0赞

一、递归实现全排列

\#include"cstdio"

int A\[\];

void print\_permutation(int n,int \*A,int cur)\{

if(cur==n)\{

for(int i=;i

printf("%d",A\[i\]);

printf("\\n");

else for(int j=;j

int ok=;

for(int k=;k

if(A\[k\]==j)

ok=;

if(ok)\{

A\[cur\]=j;

print\_permutation(n,A,cur+);

int main()\{

int n;

scanf("%d",&n);

print\_permutation(n,A,);

return ;

二、解答树

\#include

using namespace std;

const int N = ; //输入排序的个数的最大值

int record\[N\]; //记录每次排序的序列

int visited\[N\]; //标记节点是否被访问过

int n; //输入节点的数目

int totalSize = ;

void DFS(int start)\{

if(start>=n)\{ //递归出口

for(int i=;i

cout<

totalSize++;

cout<

return;

for(int i=;i<=n;i++)\{ //深度遍历节点，并标记已经访问过的节点

if(visited\[i\]==)\{

visited\[i\] = ;

record\[start\] = i;

DFS(start+); //递归遍历

visited\[i\] = ; //回退时标记回退的节点为未被访问节点

int main()

cin>>n;

memset(visited,,n);

DFS();

cout<

return ;

三、

调用next\_permutation()方法

四、回溯法总结

1、八皇后问题代码

\#include

using namespace std;

int n=8; int rows\[\];//存储n行的第几列

int j=;

bool Is(int row)\{

for(int i=;i

if(rows\[row-i\]==rows\[row\]-i||rows\[row-i\]==rows\[row\]+i||rows\[row\]==rows\[row-i\])

return false;

return true;

void start(int row)\{

if(row==n)

j++;

else \{

for(int col=;col

rows\[row\]=col;

if(Is(row))\{

printf("%d %d\\n",row,rows\[row\]);

start(row+);

int main()\{

start();

printf("%d\\n",j);

return ;

总结：在全排列和八皇后问题中，均使用了递归回溯。其格式大致为

void f()\{

If()\{//符合要求的一组解求出后

count++

\}else\{

For(int ....)\{

f();//递归调用

Leetcode之回溯法专题-47&period; 全排列 II(Permutations II)

Leetcode之回溯法专题-47. 全排列 II(Permutations II) 给定一个可包含重复数字的序列,返回所有不重复的全排列. 示例: 输入: \[1,1,2\] 输出: \[ \[1,1,2\] ...

Leetcode之回溯法专题-46&period; 全排列(Permutations)

Leetcode之回溯法专题-46. 全排列(Permutations) 给定一个没有重复数字的序列,返回其所有可能的全排列. 示例: 输入: \[1,2,3\] 输出: \[ \[1,2,3\], \[1,3, ...

C语言递归回溯法迷宫求解

本例将随机产生一个10\*10的迷宫输出后,在下面输出此迷宫的解法. 解法为从坐标(1,1)处进入,从(8,8,)出去,优先线路为先右后下再上最后为左. 不少人求解此题时运用的栈的相关知识,本例寻找线路 ...

uva216 c&plus;&plus;回溯法

因为题目要求最多8台电脑,所以可以枚举全排列,然后依次计算距离进行比较,枚举量8!=40320并不大,但这种方法不如回溯法好,当数据再大一些枚举就显得笨拙了,所以这个题我用回溯法做的,回溯有一个好处是 ...

使用回溯法求所有从n个元素中取m个元素的组合

不多说了,直接上代码,代码中有注释,应该不难看懂. \#include \#include typedef char ELE\_TYPE; ...

python 回溯法 子集树模板 系列 —— 13、最佳作业调度问题

问题 给定 n 个作业,每一个作业都有两项子任务需要分别在两台机器上完成.每一个作业必须先由机器1 处理,然后由机器2处理. 试设计一个算法找出完成这n个任务的最佳调度,使其机器2完成各作业时间之和达 ...

python 回溯法 记录

一直不是太理解回溯法,这几天集中学习了一下,记录如下. 回溯法有"通用的解题法"之称. 1.定义:  也叫试探法,它是一种系统地搜索问题的解的方法. 2.基本思想:  从一条路往前 ...

USACO 1&period;5&period;4 Checker Challenge跳棋的挑战&lpar;回溯法求解N皇后问题&plus;八皇后问题说明&rpar;

Description 检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行,每列,每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子. 列号 0 1 2 3 4 5 6 ...

回溯法、DFS

回溯法 为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一旦发现原来的选择是错误的,就退回上一步重新选择条件,继续向前探索,如此反复进行,直至得到解或证明无解. DFS DFS模板 vo ...

随机推荐

大叔也学Xamarin系列

回到占占推荐博客索引 我就是我,请叫我仓储大叔 大叔听很多客户说,xamarin的资料网上太少了,是的,大叔也相信,因为大叔在学xamarin里确实很费劲,只能看看androd for java了,呵 ...

关于 htonl 和 ntohl 的实现

因为需要直接处理一个网络字节序的 32 位 int,所以,考虑用自己写的还是系统函数效率更高.然后又了下面的了解. 首先是系统函数 htonl ,我在 kernel 源码 netinet/in.h 找 ...

C&num; checkboxlist的使用

最近做项目,需要用到checklistbox这一控件,由于对这一控件并不是很熟悉,导致在此浪费了一点时间. http://www.cnblogs.com/hongfei/archive/2012/12 ...

Nodejs新建博客练习&lpar;一&rpar;安装express并新建项目

安装express npm install -g express-generator 新建工程 express blog //新建项目 cd blog && npm install / ...

IPv6 tutorial 4 IPv6 address syntax

https://4sysops.com/archives/ipv6-tutorial-part-4-ipv6-address-syntax/ Now that you know about the n ...

关于SetCapture&lpar;&rpar; 和 ReleaseCapture&lpar;&rpar;的使用方法

查MSND,对SetCapture()函数的说明为:“该函数在属于当前线程的指定窗体里设置鼠标捕获.一旦窗体捕获了鼠标,全部鼠标输入都针对该窗体,不管光标是否在窗体的边界内.同一时刻仅仅能有一个窗体捕 ...

只查看tomcat进程，不包括grep

ps aux | grep tomcat  | grep -v "grep" | awk '\{print $2\}'

Java基础学习笔记二十一 多线程

多线程介绍 学习多线程之前,我们先要了解几个关于多线程有关的概念.进程:进程指正在运行的程序.确切的来说,当一个程序进入内存运行,即变成一个进程,进程是处于运行过程中的程序,并且具有一定独立功能. 线 ...

IP地址字符串与int整数之间的无损转化

今天鹅厂店面,最后问了一个ip地址字符串和整数间无损转化的问题,晚上有时间了手撸了一下代码. public class IPstr \{ public static void main(String a ...

CentOS6&period;4下Mysql数据库的安装与配置

原文连接:http://www.cnblogs.com/xiaoluo501395377/archive/2013/04/07/3003278.html 说到数据库,我们大多想到的是关系型数据库,比如 ...

c语言实现全排列并存储,C语言实现全排列和回溯法总结

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 Permutations(C++全排列)

相关数组全排列递归算法C语言,C++全排列递归算法

相关 c语言实现全排列并存储,C语言实现全排列和回溯法总结

相关回溯法解决全排列问题总结

相关 418-回溯算法-基于穷举法的全排列实现

相关全排列，回溯

相关 C语言全排列

相关字符串全排列的问题 python和c语言实现

相关全排列的递归算法(C语言)

相关 C++全排列和组合