算法----回溯(附录---剪枝)
回溯相信大家都已经了解了所以这章我将见但介绍下回溯剪枝
为什要剪枝
在《算法----回溯(正文)》中我提到过回溯就是暴力,为什么那些题能过,因为数据范围小
那如果数据范围大了,就不行了,这时剪枝的作用就出来了,去除重复多余,不符合的把时间复杂度降下来
什么是剪枝
将不需要的删除,不考虑
回溯剪枝模板
void dfs(变量){if(终止条件){存放结果return ;} 判断(剪枝)(1.如果这都不符合了那么后面肯定不符合2.重复的东西有了就可以不要了) for(.....){判断标记dfs();回溯 }
}
回溯剪枝例题
1318:【例5.3】自然数的拆分
【题目描述】
任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。
当n=7共14种拆分方法:
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14
【输入】
输入n。
【输出】
按字典序输出具体的方案。
【输入样例】
7
【输出样例】
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
#include<bits/stdc++.h>
using namespace std;
int n;
int ab[350];
void print(int cnt){cout<<n<<"=";bool f=false;for(int i=1;i<=cnt;i++){if(f){cout<<"+";}cout<<ab[i];f=true;} cout<<"\n";
}
void dfs(int cnt,int s,int last){for(int i=last;i<n;i++){if(s-i==0){ab[cnt]=i;print(cnt);return ;}else if(s-i>0){ab[cnt]=i;dfs(cnt+1,s-i,i);}}
}
int main()
{
cin>>n;
dfs(1,n,1);return 0;
}
//不减枝
#include<bits/stdc++.h>
using namespace std;
int n;
int ab[350];
void print(int cnt){cout<<n<<"=";bool f=false;for(int i=1;i<=cnt;i++){if(f){cout<<"+";}cout<<ab[i];f=true;} cout<<"\n";
}
void dfs(int cnt,int s,int last){for(int i=last;i<n;i++){if(s-i==0){ab[cnt]=i;print(cnt);return ;}else if(s-i>0){ab[cnt]=i;dfs(cnt+1,s-i,i);}else{break;}}
}
int main()
{
cin>>n;
dfs(1,n,1);return 0;
}
//剪枝
总结:剪枝对于小数据来说不算啥,但对于大数据就很重要了
相关文章:
算法----回溯(附录---剪枝)
回溯相信大家都已经了解了所以这章我将见但介绍下回溯剪枝 为什要剪枝 在《算法----回溯(正文)》中我提到过回溯就是暴力,为什么那些题能过,因为数据范围小 那如果数据范围大了,就不行了,这时剪枝的作用就…...
从Unity到Three.js(模型文件加载)
模型加载功能探索,用blender导出了个glb格式的cube进行的测试。 初接触js语法,回调注册的地方直接使用匿名函数总感觉脑子跟不上,反应不过来,就把加载后的回调简单封装了下, 官方文档是直接使用的匿名函数。 另外看官方…...
Webshell一句话木马
一、webshell介绍(网页木马) 分类: 大马:体积大、隐蔽性差、功能多 小马:体积小,隐蔽强,功能少 一句话木马:代码简短,灵活多样 二、一句话木马: :…...
【Web】Spring rce CVE-2022-22965漏洞复现学习笔记
目录 原理概览 漏洞简述 Tomcat AccessLogValve 和 access_log 例题: 原理概览 spring框架在传参的时候会与对应实体类自动参数绑定,通过“.”还可以访问对应实体类的引用类型变量。使用getClass方法,通过反射机制最终获取tomcat的日志配置成员属性…...
springboot/ssm大学生选修选课系统高校选课排课成绩管理系统Java系统
springboot/ssm大学生选修选课系统高校选课排课成绩管理系统Java系统 开发语言:Java 框架:springboot(可改ssm) vue JDK版本:JDK1.8(或11) 服务器:tomcat 数据库:my…...
【芯片设计- RTL 数字逻辑设计入门 14 -- 使用子模块实现三输入数的大小比较】
文章目录 三输入数的大小比较问题分析verilog codeTestBench Code综合图仿真波形图 三输入数的大小比较 在数字芯片设计中,通常把完成特定功能且相对独立的代码编写成子模块,在需要的时候再在主模块中例化使用,以提高代码的可复用性和设计的层…...
Xilinx FPGA——在线升级
同以前单片机在线升级的做法一样,本质就是通信Flash操作跳转。 一、通信驱动 我使用的是UDP有线传输, 二、Flash芯片驱动 规划Flash芯片的区域,一般bootloader放在起始位置,APP放在bootloader之后的空白区域。 2.1 Flash擦除 我…...
电商小程序02数据源设计
上一篇我们讲解了电商小程序的需求分析,分析了需要具备的功能并且绘制了系统原型。有了原型之后下一步的事情就是根据原型来设计数据源。 数据源就像盖房子打地基一样,地基打不好,楼可能就盖不高,盖起来要再想调整就比较困难。 …...
Leetcode 3033. Modify the Matrix
Leetcode 3033. Modify the Matrix 1. 解题思路2. 代码实现 题目链接:3033. Modify the Matrix 1. 解题思路 这一题是一道easy的题目,整体思路上没啥难度,就是按照题目翻译一下即可,先遍历一下找到每一列的最大元素,…...
蓝桥杯刷题--python-4
0成绩分析 - 蓝桥云课 (lanqiao.cn) import os import sys # 请在此输入您的代码 n=int(input()) max_=float(-inf) min_=float(inf) res=0 for _ in range(n): score=int(input()) # 最高分 max_=max(max_,score) # 最低分 min_=min(min_,score) # 总分 res+=sc…...
openJudge | 距离排序
总时间限制: 1000ms 内存限制: 65536kB 描述 给出三维空间中的n个点(不超过10个),求出n个点两两之间的距离,并按距离由大到小依次输出两个点的坐标及它们之间的距离。 输入 输入包括两行,第一行包含一个整数n表示点的个数,第二…...
【算法】排序详解(快速排序,堆排序,归并排序,插入排序,希尔排序,选择排序,冒泡排序)
目录 排序的概念: 排序算法的实现: 插入排序: 希尔排序: 选择排序: 堆排序: 冒泡排序: 快速排序: 快速排序的基本框架: 1.Hoare法 2. 挖坑法 3.前后指针法 快…...
LeetCode Python -8.字符串转整数
文章目录 题目答案运行结果 题目 请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C 中的 atoi 函数)。 函数 myAtoi(string s) 的算法如下: 读入字符串并丢弃无用的前导空格检查下一个…...
【java】笔记10:类与对象——本章练习
题目1: 代码如下: import java.util.Scanner; public class Input{public static void main(String[]args){Circle cnew Circle();PassObject yuannew PassObject();System.out.println("r""\t""times");yuan.printAreas…...
《UE5_C++多人TPS完整教程》学习笔记8 ——《P9 访问 Steam(Acessing Steam)》
本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P9 访问 Steam(Acessing Steam)》 的学习笔记,该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版,UP主(也是译者&…...
缓存穿透问题与解决方案
引言 在分布式系统中,缓存技术被广泛应用以提高系统性能和响应速度。然而,缓存穿透是一个常见而严重的问题,特别是在面对大规模请求时。本文将深入探讨缓存穿透的原因、影响以及一些有效的解决方案,以确保系统在面对这一问…...
《Git 简易速速上手小册》第1章:Git 基础(2024 最新版)
文章目录 1.1 Git 简介:版本控制的演变1.1.1 基础知识讲解1.1.2 重点案例:协作开发流程优化案例:功能开发与分支策略 1.1.3 拓展案例 1:代码审查与合并1.1.4 拓展案例 2:冲突解决 1.2 安装和配置 Git:首次设…...
交易中的胜率和盈亏比估算
交易中的胜率和盈亏比估算 1.定义 胜率是指交易者在一定时间内成功交易的次数占总交易次数的比例。例如,如果交易者在10次交易中成功了6次,那么他的胜率就是60%。 盈亏比是指交易者每笔成功交易的盈利与每笔失败交易的亏损之间的比例。例如࿰…...
mysql RR、RC隔离级别实现原理
事务隔离级别实现过程 快照读(select语句) 获取事务自己版本号,即事务 ID获取 Read View 查询得到数据,然后 Read View 中事务版本号进行比较。如果不符合 Read View 可见性规则(看最新数据还是副本里的数据…...
c语言--指针数组(详解)
目录 一、什么是指针数组?二、指针数组模拟二维数组 一、什么是指针数组? 指针数组是指针还是数组? 我们类比一下,整型数组,是存放整型的数组,字符数组是存放字符的数组。 那指针数组呢?是存放…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
