当前位置: 首页 > news >正文

算法----回溯(附录---剪枝)

回溯相信大家都已经了解了所以这章我将见但介绍下回溯剪枝

为什要剪枝

在《算法----回溯(正文)》中我提到过回溯就是暴力,为什么那些题能过,因为数据范围小
那如果数据范围大了,就不行了,这时剪枝的作用就出来了,去除重复多余,不符合的把时间复杂度降下来

什么是剪枝

将不需要的删除,不考虑

回溯剪枝模板

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;
}
//剪枝

总结:剪枝对于小数据来说不算啥,但对于大数据就很重要了

相关文章:

算法----回溯(附录---剪枝)

回溯相信大家都已经了解了所以这章我将见但介绍下回溯剪枝 为什要剪枝 在《算法----回溯&#xff08;正文&#xff09;》中我提到过回溯就是暴力&#xff0c;为什么那些题能过&#xff0c;因为数据范围小 那如果数据范围大了&#xff0c;就不行了&#xff0c;这时剪枝的作用就…...

从Unity到Three.js(模型文件加载)

模型加载功能探索&#xff0c;用blender导出了个glb格式的cube进行的测试。 初接触js语法&#xff0c;回调注册的地方直接使用匿名函数总感觉脑子跟不上&#xff0c;反应不过来&#xff0c;就把加载后的回调简单封装了下&#xff0c; 官方文档是直接使用的匿名函数。 另外看官方…...

Webshell一句话木马

一、webshell介绍&#xff08;网页木马&#xff09; 分类&#xff1a; 大马&#xff1a;体积大、隐蔽性差、功能多 小马&#xff1a;体积小&#xff0c;隐蔽强&#xff0c;功能少 一句话木马&#xff1a;代码简短&#xff0c;灵活多样 二、一句话木马&#xff1a; &#xff1a;…...

【Web】Spring rce CVE-2022-22965漏洞复现学习笔记

目录 原理概览 漏洞简述 Tomcat AccessLogValve 和 access_log 例题: 原理概览 spring框架在传参的时候会与对应实体类自动参数绑定&#xff0c;通过“.”还可以访问对应实体类的引用类型变量。使用getClass方法&#xff0c;通过反射机制最终获取tomcat的日志配置成员属性…...

springboot/ssm大学生选修选课系统高校选课排课成绩管理系统Java系统

springboot/ssm大学生选修选课系统高校选课排课成绩管理系统Java系统 开发语言&#xff1a;Java 框架&#xff1a;springboot&#xff08;可改ssm&#xff09; vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&#xff1a;my…...

【芯片设计- RTL 数字逻辑设计入门 14 -- 使用子模块实现三输入数的大小比较】

文章目录 三输入数的大小比较问题分析verilog codeTestBench Code综合图仿真波形图 三输入数的大小比较 在数字芯片设计中&#xff0c;通常把完成特定功能且相对独立的代码编写成子模块&#xff0c;在需要的时候再在主模块中例化使用&#xff0c;以提高代码的可复用性和设计的层…...

Xilinx FPGA——在线升级

同以前单片机在线升级的做法一样&#xff0c;本质就是通信Flash操作跳转。 一、通信驱动 我使用的是UDP有线传输&#xff0c; 二、Flash芯片驱动 规划Flash芯片的区域&#xff0c;一般bootloader放在起始位置&#xff0c;APP放在bootloader之后的空白区域。 2.1 Flash擦除 我…...

电商小程序02数据源设计

上一篇我们讲解了电商小程序的需求分析&#xff0c;分析了需要具备的功能并且绘制了系统原型。有了原型之后下一步的事情就是根据原型来设计数据源。 数据源就像盖房子打地基一样&#xff0c;地基打不好&#xff0c;楼可能就盖不高&#xff0c;盖起来要再想调整就比较困难。 …...

Leetcode 3033. Modify the Matrix

Leetcode 3033. Modify the Matrix 1. 解题思路2. 代码实现 题目链接&#xff1a;3033. Modify the Matrix 1. 解题思路 这一题是一道easy的题目&#xff0c;整体思路上没啥难度&#xff0c;就是按照题目翻译一下即可&#xff0c;先遍历一下找到每一列的最大元素&#xff0c…...

蓝桥杯刷题--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个点&#xff08;不超过10个&#xff09;,求出n个点两两之间的距离,并按距离由大到小依次输出两个点的坐标及它们之间的距离。 输入 输入包括两行&#xff0c;第一行包含一个整数n表示点的个数&#xff0c;第二…...

【算法】排序详解(快速排序,堆排序,归并排序,插入排序,希尔排序,选择排序,冒泡排序)

目录 排序的概念&#xff1a; 排序算法的实现&#xff1a; 插入排序&#xff1a; 希尔排序&#xff1a; 选择排序&#xff1a; 堆排序&#xff1a; 冒泡排序&#xff1a; 快速排序&#xff1a; 快速排序的基本框架&#xff1a; 1.Hoare法 2. 挖坑法 3.前后指针法 快…...

LeetCode Python -8.字符串转整数

文章目录 题目答案运行结果 题目 请你来实现一个 myAtoi(string s) 函数&#xff0c;使其能将字符串转换成一个 32 位有符号整数&#xff08;类似 C/C 中的 atoi 函数&#xff09;。 函数 myAtoi(string s) 的算法如下&#xff1a; 读入字符串并丢弃无用的前导空格检查下一个…...

【java】笔记10:类与对象——本章练习

题目1&#xff1a; 代码如下&#xff1a; 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&#xff08;Acessing Steam&#xff09;》 的学习笔记&#xff0c;该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版&#xff0c;UP主&#xff08;也是译者&…...

缓存穿透问题与解决方案

引言 在分布式系统中&#xff0c;缓存技术被广泛应用以提高系统性能和响应速度。然而&#xff0c;缓存穿透是一个常见而严重的问题&#xff0c;特别是在面对大规模请求时。本文将深入探讨缓存穿透的原因、影响以及一些有效的解决方案&#xff0c;以确保系统在面对这一问…...

《Git 简易速速上手小册》第1章:Git 基础(2024 最新版)

文章目录 1.1 Git 简介&#xff1a;版本控制的演变1.1.1 基础知识讲解1.1.2 重点案例&#xff1a;协作开发流程优化案例&#xff1a;功能开发与分支策略 1.1.3 拓展案例 1&#xff1a;代码审查与合并1.1.4 拓展案例 2&#xff1a;冲突解决 1.2 安装和配置 Git&#xff1a;首次设…...

交易中的胜率和盈亏比估算

交易中的胜率和盈亏比估算 1.定义 胜率是指交易者在一定时间内成功交易的次数占总交易次数的比例。例如&#xff0c;如果交易者在10次交易中成功了6次&#xff0c;那么他的胜率就是60%。 盈亏比是指交易者每笔成功交易的盈利与每笔失败交易的亏损之间的比例。例如&#xff0…...

mysql RR、RC隔离级别实现原理

事务隔离级别实现过程 快照读&#xff08;select语句&#xff09; 获取事务自己版本号&#xff0c;即事务 ID获取 Read View 查询得到数据&#xff0c;然后 Read View 中事务版本号进行比较。如果不符合 Read View 可见性规则&#xff08;看最新数据还是副本里的数据&#xf…...

c语言--指针数组(详解)

目录 一、什么是指针数组&#xff1f;二、指针数组模拟二维数组 一、什么是指针数组&#xff1f; 指针数组是指针还是数组&#xff1f; 我们类比一下&#xff0c;整型数组&#xff0c;是存放整型的数组&#xff0c;字符数组是存放字符的数组。 那指针数组呢&#xff1f;是存放…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...