首页 > 编程语言 >深度优先算法

深度优先算法

时间:2023-10-22 16:24:18浏览次数:40  
标签:优先 扑克牌 int 算法 dfs step book 小盒子 深度

一、引例

提问:输入一个数字n,输出1~n的全排列。

首先,将全排列比作小盒子和扑克牌

将数字比作扑克牌,我们有1号,2号,3号扑克牌和1号2号3号3个盒子。每个盒子只能放置一个扑克牌,实现全排列。那我们如何往小盒子中放入扑克牌。每个小盒子都可能放1号、2号或者3号扑克牌,这都需要一一尝试,这里一个for循环就可以解决问题

for ( i = 1; i < n; i++)
{
    a[step] = i; // 将i号扑克牌放入到第step个盒子中
}

其次,需要一个数组book来标记哪些牌已经使用了

数组a是用来表示小盒子的,变量step是用来表示房钱正处在第step个小盒子面前。
a[step] = i;就是将第i号扑克牌放入到第step个盒子中。

for (i = 1; i < n; i++)
{
    if (book[i] == 0)
    {

        a[step] = i; // 将i号扑克牌放入到第step个盒子中
        book[i] = 1; // 将book[i]设为1,表示i号扑克牌已经不在手上了
    }
}

之后,包装递归dfs函数

目前,已经处理完第step个小盒子。
现在需要将这个包装成一个dfs函数,应用递归处理第step+1个小盒子。
如下:

void dfs(int step) // step表示现在站在第几个盒子面前
{
    for (i = 1; i <= n; i++)
    {
        if (book[i] == 0)
        {

            a[step] = i; // 将i号扑克牌放入到第step个盒子中
            book[i] = 1; // 将book[i]设为1,表示i号扑克牌已经不在手上了
        }
    }
    return;
}

还有,将此过程写成函数,处理完step + 1个盒子后,递归dfs(step+1)。

下面的book[i]=0;非常重要,作用是将刚才尝试的扑克牌收回,才能进行下一次尝试

void dfs(int step)
{
    if (step == n + 1)
    {
        // 当step等于n+1时,表示找到了一个全排列,打印结果
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", a[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (book[i] == 0)
        {
            a[step] = i;   // 将第i个数放入排列中
            book[i] = 1;   // 标记数字i已经被使用
            dfs(step + 1); // 递归进入下一步
            book[i] = 0;   // 回溯,将数字i标记为未使用
        }
    }
}

最后放一个,完整代码

#include <stdio.h>

#define MAXN 10

int a[MAXN], book[MAXN], n;

// 深度优先搜索函数,用于生成全排列
void dfs(int step)
{
    if (step == n + 1)
    {
        // 当step等于n+1时,表示找到了一个全排列,打印结果
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", a[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (book[i] == 0)
        {
            a[step] = i;   // 将第i个数放入排列中
            book[i] = 1;   // 标记数字i已经被使用
            dfs(step + 1); // 递归进入下一步
            book[i] = 0;   // 回溯,将数字i标记为未使用
        }
    }
}

int main()
{
    printf("请输入n的值:");
    scanf("%d", &n);
    if (n <= 0 || n > MAXN)
    {
        printf("无效的输入。请在1和%d之间输入一个值。\n", MAXN);
        return 1;
    }
    dfs(1); // 从第一个位置开始深度优先搜索
    return 0;
}

放一个运行截图吧

总结:

以上是一个简单的例子,核心代码不过20行,却包含深度优先搜索的基本模型。
理解深度优先搜索的关键在于解决“当下如何做”。至于“下一步如何做”则与“当下如何做”是一样的。
下面的代码就是深度优先搜索的基本模型。

void dfs(int step)
{
    判断边界
    尝试每一种可能 for (i = 1; i <= n; i++)
    {
        /* code */
        继续进行下一步dfs(step + 1)
    }
    返回
}

每一种尝试就是一种“扩展”。每次站在一个盒子面前的时候,其实都有n种扩展方法,但是并不是每种扩展都能够扩展成功。


练习,使用深度优先搜索写一个1~n的数字全排列C语言代码

#include <stdio.h>
#include <stdbool.h>

// 定义一个全局数组,用于存储当前排列
int result[10];
// 定义一个数组来标记数字是否已经被使用
bool used[10];
int n; // 1 到 n 的数字

// 递归生成排列
void generatePermutations(int pos) {
    // 如果已经生成了一个完整的排列,打印它
    if (pos == n) {
        for (int i = 0; i < n; i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
        return;
    }

    // 尝试每个数字
    for (int i = 1; i <= n; i++) {
        // 如果数字未被使用,将其添加到排列中
        if (!used[i]) {
            result[pos] = i;
            used[i] = true;
            generatePermutations(pos + 1);
            used[i] = false; // 回溯,将数字标记为未使用
        }
    }
}

int main() {
    printf("请输入一个1~9的数字: ");
    scanf("%d", &n);

    if (n >= 1 && n <= 9) {
        for (int i = 1; i <= n; i++) {
            used[i] = false; // 初始化used数组
        }
        generatePermutations(0);
    } else {
        printf("请输入1~9的数字\n");
    }

    return 0;
}

标签:优先,扑克牌,int,算法,dfs,step,book,小盒子,深度
From: https://www.cnblogs.com/yzx-sir/p/17780536.html

相关文章

  • Web3.0热门领域NFT项目实战-深度掌握Solidity合约开发,助力Web3.0工程师
    Web3.0热门领域NFT项目实战-深度掌握Solidity合约开发,助力Web3.0工程师免费自动批量生成NFT图片和批量部署NFT一、环境准备1.注意:需合理上网2.准备素材:准备一套多个属性元素的不一样的图层素材,比如10张背景图、10张face图、10张眼睛图层、10张头发图层等,每张图特性不一样,像......
  • 牛牛小数输出的算法
    背景 输入一些内容,要求输出格式为两位随机数。最开始思路:1.读进来字符串,判断是否有'.'2.根据'.'判断是否需要补0或者异常处理3.以'.'为中心分为左右两段,在处理完成后进行拼接  总结:1.python应该用python的思维模式去编程,不应该重复造轮子或用C++的编程思维2.写方法......
  • 深度学习驱动的图像场景分类:窥探视觉智能的未来【图像场景实战】
    图像场景分类是计算机视觉领域的重要任务之一,它涉及将图像分为不同的场景类别,如城市街景、山脉风景、海滩等。本文将介绍基于深度学习的图像场景分类方法,并提供相应的代码实例,展示了深度学习在图像场景分类中的技术深度和应用前景。图像场景分类是计算机视觉中的一项关键任务,对于图......
  • 算法笔试题:有效的括号字符串,常规栈思路
    题:给定一个只包含三种字符的字符串:(,)和*,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:任何左括号(必须有相应的右括号)。任何右括号)必须有相应的左括号(。左括号(必须在对应的右括号之前)。*可以被视为单个右括号),或单个左括号(,或一......
  • 深度学习设置随机数种子
    seed=2023torch.manual_seed(seed)#torch的CPU随机性,为CPU设置随机种子torch.cuda.manual_seed(seed)#torch的GPU随机性,为当前GPU设置随机种子torch.cuda.manual_seed_all(seed)#torch的GPU随机性,为所有GPU设置随机种子......
  • 10.22算法
    有效的括号给定一个只包括'(',')','{','}','[',']' 的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例1:输入:s="()"输出:true示例 2:输入:s="()[]{}"输出:tru......
  • 深度学习环境搭建(Windows11)
    深度学习环境的搭建(Windows11)偶然重装了系统,在此记录下环境的恢复基本深度学习环境的搭建,包括Anaconda+CUDA+cuDNN+Pytorch+TensorRT的安装与配置。ps:显卡为RTX4060LaptopGPU1.安装Python前往Python官网https://www.python.org/getit/,下载最新版Python并安装即可。2.......
  • 提高组算法-图论学习笔记
    ##2023-10-21第一节基本概念      一、什么是图:点用边连起来就叫做图,是一种数据结构。二、图的一些定义和概念1、有向图:图的边有方向,只能按箭头方向从一点到另一点。  2、无向图:图的边没有方向,可以双向。3、结点的度:无向......
  • 动手学深度学习--第三方库的学习
    frompixivPandasCreating,ReadingandWritingpandas中有两类实体类:theDataFrameandtheSeries.DataFrameADataFrameisatable.SeriesASeries,bycontrast,isasequenceofdatavalues.一般我们在读取的时候都是用DataFrame类进行装载数据ind......
  • windows下的深度学习环境软件版本(cuda/cudnn/pytorch)
    为了方便多个深度学习框架的环境配置,推荐使用anoconda进行搭建。1.anaconda/miniconda下载地址anacoonda官方下载地址:FreeDownload|Anacondaminiconda官方下载地址: LatestMinicondainstallerlinksbyPythonversion—minicondadocumentation清华镜像源的下载地......