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语言全排列算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2022-01-12

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

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

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

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

浅谈C语言的字符串分割

说起来很有意思,自认为对C语言理解得还是比较深刻的.但居然到今天才知道有个strtok函数,试用了一下突然感慨以前做了多少重复劳动.每次需要解析配置文件,每次需要分割字符串,居然都是自己去分割字符串,既累人又容易出错.感概技术学得不够全面啊!这里引用一段strtok用法: The strtok() function returns a pointer to the next "token" in str1, where str2 contains the delimiters that

Go语言实现字符串切片赋值的方法小结

前言 在所有编程语言中都涉及到大量的字符串操作,可见熟悉对字符串的操作是何等重要.本文通过示例详细介绍了Go语言实现字符串切片赋值的方法,感兴趣的朋友们跟着小编一起来看看吧. 1. 在for循环的range中 func StrRangeTest() { str := []string{"str1", "str2", "str3"} for i, v := range str { fmt.Println(i, v) v = "test&q

Go语言常用字符串处理方法实例汇总

本文实例汇总了Go语言常用字符串处理方法.分享给大家供大家参考.具体如下: 复制代码 代码如下: package main import (     "fmt"     "strings"     //"unicode/utf8" ) func main() {     fmt.Println("查找子串是否在指定的字符串中")     fmt.Println(" Contains 函数的用法")    

Go语言对字符串进行MD5加密的方法

本文实例讲述了Go语言对字符串进行MD5加密的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package main import (     "crypto/md5"     "fmt"     "io" ) func main() {     h := md5.New()     io.WriteString(h, "welcome to jb51.net")     fmt.Printf(&quo

Go语言对字符串进行SHA1哈希运算的方法

本文实例讲述了Go语言对字符串进行SHA1哈希运算的方法.分享给大家供大家参考.具体如下: 复制代码 代码如下: package main import (  "fmt"  "crypto/md5"  "crypto/sha1"  "io" ) //对字符串进行MD5哈希 func a(data string) string {  t := md5.New();  io.WriteString(t,data);  return

Go语言写入字符串到文件的方法

本文实例讲述了Go语言写入字符串到文件的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package  main import "fmt" import "os" func main() {     fileName := "test.dat"     dstFile,err := os.Create(fileName)     if err!=nil{         fmt.Println(err.Error())  

Go语言截取字符串函数用法

本文实例讲述了Go语言截取字符串函数用法.分享给大家供大家参考.具体如下: 复制代码 代码如下: func Substr(str string, start, length int) string {     rs := []rune(str)     rl := len(rs)     end := 0             if start < 0 {         start = rl - 1 + start     }     end = start + length        

Go语言使用字符串的几个技巧分享

一.字符串底层就是一个字节数组 这真的非常重要,而且影响着下面的其他几个技巧.当你创建一个字符串时,其本质就是一个字节的数组.这意味着你可以像访问数组一样的访问单独的某个字节.例如,下面的代码逐个打印字符串中的每个字节以及对应字节数组中的每个字节: package main import "fmt" func main() { str := "hello" for i := 0; i < len(str); i++ { fmt.Printf("%b

C语言实现字符串操作函数的实例

C语言实现字符串操作函数的实例 在编写程序的过程中,我们经常使用到一些字符串函数,例如求字符串长度,拷贝字符串--,这些函数都在C标准库中存在,我们可以直接使用.但我们还需要掌握这些函数的实现方法,今天来看看一些常用的字符串操作函数的实现方法. 1.strlen strlen是用来求字符串长度的函数,字符串长度就是它所包含的字符个数. 今天给大家介绍三种实现strlen函数的方法 (1)定义一个计数器count //方式一:定义一个计数器 size_t my_strlen(const char