C语言全排列回溯算法介绍

目录
  • 前言
  • 算法思想
  • 完整代码
  • 实验效果
  • 总结

前言

本博文源于最近学习的递归算法，递归中遇到一个问题全排列的问题，我看见回溯特别神奇，特此记录一下。对比一下深度优先搜索与广度优先搜索，个人感觉这里的回溯像是一种递归树中的深度优先搜索的算法，他不断构造往下延伸的深度，使其达到完全编列

算法思想

比如3拿来举例，按照一般正常的话就是应该，

123 132 213 231 312 321

六种，先造出一个hashtable数组让其存储在各位是否使用，然后创建path的p数组将数字进行选填，递归树我花在文章下面。

完整代码

#include<cstdio>
const int maxn = 11;
//P 为当前排列 HashTable记录整个数x是否已经在P中
int n,P[maxn],hashTable[maxn] = {false};
//当前处理排列的第index位置
void generateP(int index) {
    if(index == n+1){
        for(int i=1;i<=n;i++){
            printf("%d",P[i]);
        }
        printf("\n");
        return ;
    }
    for(int x = 1;x<=n;x++) {
        if(hashTable[x] == false) {
            P[index] = x;
            hashTable[x] = true;
            generateP(index + 1);
            hashTable[x] = false;
        }
    }
}
int main()
{
    n = 3;
    generateP(1);
    return 0;

}

实验效果

总结

到此这篇关于C语言全排列回溯算法介绍的文章就介绍到这了,更多相关C语言全排列算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 使用C语言解决字符串全排列问题

    使用C语言解决字符串全排列问题

    问题 输入一个字符串,打印出该字符串中字符的所有排列.例如输入字符串abc,则输出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba 思路 这是典型的递归求解问题,递归算法有四个特性: 必须有可达到的终止条件,否则程序陷入死循环 子问题在规模上比原问题小 子问题可通过再次递归调用求解 子问题的解应能组合成整个问题的解 对于字符串的排列问题: 如果能生成n-1个元素的全排列,就能生成n个元素的全排列.对于只有一个元素的集合,可以直接生成全排列.所以全排列的递归终

  • C语言实现全排列算法模板的方法

    程序的主要思路是: 1.把第1个数换到最前面来(本来就在最前面),准备打印1xx,再对后两个数2和3做全排列. 2.把第2个数换到最前面来,准备打印2xx,再对后两个数1和3做全排列. 3.把第3个数换到最前面来,准备打印3xx,再对后两个数1和2做全排列. 可见这是一个递归的过程,把对整个序列做全排列的问题归结为对它的子序列做全排列的问题,注意我没有描述Base Case怎么处理,你需要自己想.你的程序要具有通用性,如果改变了N和数组a的定义(比如改成4个数的数组),其它代码不需要修改就可以做

  • C语言全排列回溯算法介绍

    C语言全排列回溯算法介绍

    目录 前言 算法思想 完整代码 实验效果 总结 前言 本博文源于最近学习的递归算法,递归中遇到一个问题全排列的问题,我看见回溯特别神奇,特此记录一下.对比一下深度优先搜索与广度优先搜索,个人感觉这里的回溯像是一种递归树中的深度优先搜索的算法,他不断构造往下延伸的深度,使其达到完全编列 算法思想 比如3拿来举例,按照一般正常的话就是应该, 123 132 213 231 312 321 六种,先造出一个hashtable数组让其存储在各位是否使用,然后创建path的p数组将数字进行选填,递归树我花

  • C语言基于回溯算法解决八皇后问题的方法

    C语言基于回溯算法解决八皇后问题的方法

    本文实例讲述了C语言基于回溯算法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 问题描述: 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 问题求解: 采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行:若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可

  • C语言直接插入排序算法介绍

    C语言直接插入排序算法介绍

    目录 前言 一.什么是直接插入排序 二.代码讲解 总结 前言 直接 插入排序 (Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表.. 废话不多说先看看代码 #define _CRT_SECURE_NO_WARNINGS 1 //直接插入排序法 #include <stdio.h> void Compare(int arr[], int len) { int i = 0; for (i =

  • C语言直接插入排序算法介绍及示例

    C语言直接插入排序算法介绍及示例

    目录 1. 直接插入排序介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度 1.4 空间复杂度 1.5 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 直接插入排序介绍 1.1 定义 直接插入排序是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表. 1.2 基本原理 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序. 第一趟比较前两个数,然后把第二个数按大小插入到有序表中: 第二趟把第三个

  • C语言顺序查找算法介绍及示例

    C语言顺序查找算法介绍及示例

    目录 1. 顺序查找介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度与空间复杂度 1.4 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 顺序查找介绍 1.1 定义 查找是指在指定数据组合中找出满足条件的元素个体.顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法. 顺序查找是最基础也是最简单的查找算法,在需要进行查找时,这是我们的首选方法,只有数据较多,结构复杂,耗时较多需要优化时,我们才会考虑使用其他查找方法. 1.2 基本原理 对于任意一个序列以及一个

  • python回溯算法实现全排列小练习分享

    python回溯算法实现全排列小练习分享

    问题:输入列表L(不含重复元素),输出L的全排列. 如输入:L=[1,2,3] 则输出:[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 全排列问题,可以用回溯法解决,详细分析请参考东哥公众号:labuladong,看了之后醍醐灌顶. 先帖一个正确解法: ''' 回溯算法模板: from: labuladong公众号 result = [] def backtrack(选择列表,路径):     if 满足结束条

  • C语言之快速排序算法（递归Hoare版）介绍

    C语言之快速排序算法（递归Hoare版）介绍

    废话不多说,先看代码 #define _CRT_SECURE_NO_WARNINGS 1 //快速排序算法,递归求解 #include <stdio.h> void swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; } void Compare(int arr[], int one, int end) { int first = one;//最左边数组下标 int last = end;//最右边数组下标 int key =

  • C语言之快速排序算法(递归Hoare版)介绍

    C语言之快速排序算法(递归Hoare版)介绍

    废话不多说,先看代码 #define _CRT_SECURE_NO_WARNINGS 1 //快速排序算法,递归求解 #include <stdio.h> void swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; } void Compare(int arr[], int one, int end) { int first = one;//最左边数组下标 int last = end;//最右边数组下标 int key =

  • C语言数据结构与算法之图的遍历

    C语言数据结构与算法之图的遍历

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • C++回溯算法深度优先搜索举例分析

    C++回溯算法深度优先搜索举例分析

    目录 扑克牌全排列 员工的重要性 图像渲染 被围绕的区域 岛屿数量 电话号码的字母组合 组合总数 活字印书 N皇后 扑克牌全排列 假如有编号为1~ 3的3张扑克牌和编号为1~3的3个盒子,现在需要将3张牌分别放到3个盒子中去,且每个盒子只能放一张牌,一共有多少种不同的放法. 解题思路:假定按照牌面值从小到大依次尝试,即将1号牌放入第一个盒子中.按此顺序继续向后走,放完第三个盒子时,手中的牌也已经用完,再继续往后则到了盒子的尽头.此时一种放法已经完成了,即这条路走到了尽头,需要折返,重新回到上一个

随机推荐