首页 > 其他分享 >11918 骰子|| 深搜 递归

11918 骰子|| 深搜 递归

时间:2024-09-30 17:45:23浏览次数:10  
标签:骰子 递归 int sum DFS 点数 11918

解决思路

 
  • 深度优先搜索 (DFS):使用 DFS 枚举所有可能的骰子点数组合。
 
  • 剪枝:在 DFS 过程中,如果当前点数和已经超过 sum 或者剩余骰子无法达到 sum,则剪枝。
 
  • 字典序输出:由于 DFS 的递归顺序,天然保证了字典序输出。
    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N = 1e3+10; // 定义常量N,表示数组的最大长度
    int n, sum; // n表示骰子的个数,sum表示目标点数和
    int a[N], k; // a数组用于存储当前的骰子点数组合,k表示当前已经选择的骰子个数
    
    // 打印当前组合
    void print() {
        for(int i = 1; i <= k; i++) cout << a[i]; // 输出当前组合的每个骰子点数
        cout << endl; // 换行
    }
    
    // 深度优先搜索函数
    void dfs(int cnt, int s) {
        if(k == n) { // 如果已经选择了n个骰子
            if(s == sum) print(); // 如果当前点数和等于目标点数和,则打印当前组合
            return; // 返回上层调用
        }
        for(int i = 1; i <= 6; i++) { // 枚举当前骰子的点数,从1到6
            a[++k] = i; // 将当前点数加入组合
            dfs(cnt + 1, s + i); // 递归调用,继续选择下一个骰子
            k--; // 回溯,移除当前点数
        }
    }
    
    int main() {
        cin >> n >> sum; // 读取骰子的个数和目标点数和
        dfs(0, 0); // 从第0个骰子开始,当前点数和为0,开始深度优先搜索
        return 0; // 返回0,表示程序正常结束
    }

     

标签:骰子,递归,int,sum,DFS,点数,11918
From: https://www.cnblogs.com/jyssh/p/18442261

相关文章

  • 初学Java基础Day08 方法,方法的递归,方法的重载
    一,方法1.概念:        特定功能的代码块2.好处:        减少代码的冗余3.分类:1.无参数无返回值的方法2.带参数的方法3.带返回的方法4.理解:        参数是方法调用时传入的数据,返回值是方法执行完毕后返回的数据1.无参数无返回的方法//语法结......
  • 华为OD机试2024年E卷-转骰子[200分]( Java | Python3 | C++ | C语言 | JsNode | Go )实
    题目描述骰子是一个立方体,每个面一个数字,初始为左1,右2,前3(观察者方向),后4,上5,下6,用123456表示这个状态,放置在平面上,可以向左翻转(用L表示向左翻转1次),可以向右翻转(用R表示向右翻转1次),可以向前翻转(用F表示向前翻转1次),可以向后翻转(用B表示向后翻转1次),可以逆时针旋转(......
  • 基于递归下降解析器的四则运算题生成器
    结对项目本次项目的GitHub位置:https://github.com/EIiasK/Eliask/tree/main/3122004566/Exercise_Generator项目成员及github地址郭人诵github地址:https://github.com/EIiasK/Eliask何其浚github地址:https://github.com/hugh143/hugh143这个作业属于哪个课程......
  • 基于SpringBoot 应用Stream流+递归 实现多级分类
    SpringBoot->Stream流实现步骤:先查询所有级联的数据,然后通过Java8 Stream 流来比较和判断,最终生成有顺序的级联数据实体类:@DatapublicclassAddr{/***主键id*/privateLongaddrId;/***名称*/privateStringaddrNam......
  • 非递归快速构建树-注解版
    importcom.fasterxml.jackson.core.JsonProcessingException;importcom.fasterxml.jackson.databind.ObjectMapper;importjava.lang.reflect.Field;importjava.util.ArrayList;importjava.util.LinkedHashMap;importjava.util.List;importjava.util.Map;/**......
  • python 递归锁、信号量、事件、线程队列、进程池和线程池、回调函数、定时器
    一、python线程死锁与递归锁死锁现象所谓死锁:是指两个或两个以上的进程或线程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程代码示例:fromthreadingimport......
  • 9.26递归函数
    递归函数的定义和格式递归是一种常用的解决问题的方法,特别适用于解决可以被分解为类似子问题//递归函数:在函数内部再次调用自己//解决可以被分解为类似子问题的问题//组成://1.基本情况最小问题的答案//2.递归情况调用自己去解决子问题objectTestFucRecursive{//......
  • 时序预测 | Matlab实现SSA-TCN麻雀搜索算法优化时间卷积网络时序预测-递归预测未来数
    时序预测|Matlab实现SSA-TCN麻雀搜索算法优化时间卷积网络时序预测-递归预测未来数据(单输入单输出)目录时序预测|Matlab实现SSA-TCN麻雀搜索算法优化时间卷积网络时序预测-递归预测未来数据(单输入单输出)预测效果基本介绍程序设计参考资料预测效果基本介绍1.Matlab实现SSA-TCN......
  • 递归的统计目录下所有代码的总行数
    小明刷题一年多了。看着leetcode上密密麻麻的提交记录,小明有点小自豪的同时,刷题后遗症又有点犯了:刷了那么多题,相当于多少行代码呢?1万行?10万行??怎么才能快速的统计出到底写了多少行代码呢?好在本地所有的代码都在一个目录下面,只需要统计目录下面所有源代码文件的行数的总和即可,当然......
  • 排序----归并排序(非递归版)
    如图代码为11归并的示例,用for循环来解决。每一次往前递归的前一小部分内部已经是有序的了。但是我们测试的时候会发现这样一个问题,begin和end的值会存在越界的问题,而且只有begin1不会越界,因为begin1是受for循环中i的控制的。所以当我们遇到begin越界了就不用管了,遇到end越......