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

[复健计划][紫书]Chapter 7 暴力求解法

7.1 简单枚举

例7-1 Division uva725
输入正整数n,按从小到大的顺序输出所有形如abcde/fghij = n的表达式,其中a~j恰好为数字0~9的一个排列(可以有前导0),2≤n≤79。

枚举fghij,验证abcde是否有重复数字

例7-2 Maximum Product uva11059
输入n个元素组成的序列S,你需要找出一个乘积最大的连续子序列。如果这个最大的乘积不是正数,应输出0(表示无解)。1≤n≤18,-10≤Si≤10。

枚举起点和终点

例7-3 Fractions Again?! uva10976
输入正整数k,找到所有的正整数x≥y,使得1/k=1/x+1/y。

在[1,2k]范围内枚举y

7.2 枚举排列

7.2.1 生成1~n的排列

递归

7.2.2 生成可重集的排列

递归

7.2.3 解答树

在这里插入图片描述
在这里插入图片描述

如果某问题的解可以由多个步骤得到,而每个步骤都有若干种选择(这些候选方案集可能会依赖于先前作出的选择),且可以用递归枚举法实现,则它的工作方式可以用解答树来描述。

7.2.4 下一个排列

在这里插入图片描述

7.3 子集生成

7.3.1 增量构造法

规定集合A中所有元素的编号从小到大排列,一次选出一个元素放到集合中

void get_subset(int n,int *A,int siz){for(int i=1;i<=siz;i++) printf("%d ",A[i]);printf("\n");int minn=siz?A[siz]+1:1;for(int i=minn;i<=n;i++){A[siz+1]=i;get_subset(n,A,siz+1);}
} 

解答树中,每个子集对应一个结点,一共有 2 n 2^n 2n个结点

7.3.2 位向量法

构造一个位向量B[i],而不是直接构造子集A本身,其中B[i]=1,当且仅当i在子集A中

void get_subset(int n,int *B,int p){if(p>n){for(int i=1;i<=n;i++)if(B[i]) printf("%d ",i);printf("\n");return;}B[p]=0;get_subset(n,B,p+1);B[p]=1;get_subset(n,B,p+1);
} 

解答树上有 1 + 2 + 4 + . . . + 2 n = 2 n + 1 − 1 1+2+4+...+2^{n}=2^{n+1}-1 1+2+4+...+2n=2n+11个结点,所有部分解(不完整的解)也对应着解答树上的结点,最后几层结点数占整棵树的绝大多数。

7.3.3 二进制法

以用二进制来表示{0, 1, 2,…,n-1}的子集S:从右往左第i位(各位从0开始编号)表示元素i是否在集合S中。
当用二进制表示子集时,位运算中的按位与、或、异或对应集合的交、并和对称差。

void print_set(int n,int s){for(int i=0;i<n;i++)if(s&(1<<i)) print("%d ",i);printf("\n");
}
for(int s=0;s<(1<<n);s++) //枚举子集 print_subset(n,s);

相关文章:

[复健计划][紫书]Chapter 7 暴力求解法

7.1 简单枚举 例7-1 Division uva725 输入正整数n&#xff0c;按从小到大的顺序输出所有形如abcde/fghij n的表达式&#xff0c;其中a&#xff5e;j恰好为数字0&#xff5e;9的一个排列&#xff08;可以有前导0&#xff09;&#xff0c;2≤n≤79。枚举fghij&#xff0c;验证a…...

基于SpringBoot的社区讯息服务小程序【附源码】

基于SpringBoot的社区讯息服务小程序 效果如下&#xff1a; 系统登陆页面 管理员主页面 用户管理页面 社区活动管理页面 设施报修管理页面 缴费信息管理页面 用户主页面 用户登录页面 社区活动页面 研究背景 随着移动互联网技术的飞速发展&#xff0c;社区生活日益依赖于数字…...

springboot图书管理系统(一个简单的单体架构项目,适合小白)

期末作业 为了水一水期末作业&#xff0c;打算写一个简易的单体架构图书管理系统。以下为后端主要技术栈(后期可能更新&#xff0c;打算一个星期左右写完吧)。 springbootredismysqlspringcachespringsecurity … 数据库设计 第一次从0开始搭建后续可能还会多更新一些表。 -- 角…...

《CLR via C#》读书笔记--CLR的执行模型

将源代码编译成托管模块将托管模块合并成程序集加载公共语言运行时执行程序集的代码本机代码生成器&#xff1a;NGen.exeFramework 类库入门通用类型系统公共语言规范&#xff08;CLS&#xff09;与非托管代码的互操作性 将源代码编译程托管模块 公共语言运行时&#xff08;Co…...

Javascript常见数据结构及其应用场景

Basic 以下是对JavaScript中常见数据结构及其应用场景的详细扩展&#xff1a; 数组&#xff08;Array&#xff09; 定义与特性&#xff1a;数组是由一组按顺序排列的值组成&#xff0c;每个值都有一个对应的索引&#xff08;下标&#xff09;&#xff0c;可以通过索引访问和修…...

简单的签到程序 python笔记

简单的人脸识别签到程序 在看完以下代码后&#xff0c;略微修改一番&#xff0c;你就能够组装出自己的“简单的人脸识别签到程序”了。 请注意库的安装&#xff0c;否则会不可用。 你可以通过在cmd中使用&#xff1a;pip install来安装。 以下代码运行python 3.8 UI界面 使…...

30天如何成功转行成为AI产品经理?如果你也想转行到AI,赶紧进来抄作业!!!

前言 随着AI技术的快速发展&#xff0c;AI产品经理成为了备受瞩目的职业。如果您也想抓住这个机遇&#xff0c;不妨跟随这份30天快速入门指南&#xff0c;开始您的AI产品经理转型之旅。 一、学习路线 第一阶段&#xff08;5天&#xff09;&#xff1a;初阶应用 该阶段让大家…...

基于Python+Vue开发的蛋糕商城管理系统

项目简介 该项目是基于PythonVue开发的蛋糕商城管理系统&#xff08;前后端分离&#xff09;&#xff0c;这是一项为大学生课程设计作业而开发的项目。该系统旨在帮助大学生学习并掌握Python编程技能&#xff0c;同时锻炼他们的项目设计与开发能力。通过学习基于Python的蛋糕商…...

WSL开发--利用Git连接远程仓库(详细步骤)

这篇文章主要介绍了如何将本地项目推送到 GitLab 上&#xff0c;并且避免每次提交都需要输入用户名和密码。文中分步讲解了配置 GitLab SSH 密钥以及配置 Git 远程仓库地址的方法。以下是文章的优化和简洁版&#xff1a; 将本地项目推送到 GitLab 并配置 SSH 免密登录 为了方便…...

VLAN高级+以太网安全

VLAN聚合 MUX VLAN QinQ 以下是这三种VLAN技术的作用及其在项目中的应用实例&#xff1a; VLAN聚合 (VLAN Aggregation) VLAN聚合通常用于将多个VLAN数据聚合到一个物理链路上&#xff0c;以减少链路数量、提高链路利用率。这样可以在一个物理链路上同时传输不同VLAN的数据包&…...

R7:糖尿病预测模型优化探索

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 一、实验目的&#xff1a; 探索本案例是否还有进一步优化的空间 二、实验环境&#xff1a; 语言环境&#xff1a;python 3.8编译器&#xff1a;Jupyter notebo…...

Spring核心:探索IoC容器与依赖注入的奥秘

目录 一、什么是Spring&#xff1f; 二、什么是 Ioc &#xff1f; 2.1 控制反转的实现方式 2.1.1 依赖注入 2.1.2 依赖查找 2.1.3 优点分析 2.2 理解 Ioc 一、什么是Spring&#xff1f; 我们通常所说的 Spring 指的是 Spring Framework&#xff08;Spring 框架&#xff…...

15分钟学 Go 实践项目二:打造博客系统

打造博客系统 项目概述 在本项目中&#xff0c;我们将创建一个简单的博客系统&#xff0c;重点实现CRUD&#xff08;创建、读取、更新、删除&#xff09;操作和用户管理。这个博客系统将使用户能够发布文章&#xff0c;评论&#xff0c;并管理其个人账户信息。 目标 实现用…...

Follow软件的使用入门教程

开篇 看到很多兄弟还不知道怎么用这个当下爆火的浏览器&#xff01;在这里简单给需要入门的小伙伴一些建议&#xff1a; 介绍 简单解释一下&#xff0c;RSS 意思是简易信息聚合&#xff0c;用户可以通过 RSS 阅读器或聚合工具自主订阅并浏览各个平台的内容源&#xff0c;不用…...

【IC验证】systemverilog的设计特性

systemverilog的设计特性 一.概述二.面向硬件的过程语句块1.说明2.always_comb2.always_latch3.always_ff 三.关系运算符1.说明2.例子 四.inside判定符1.说明2.例子 五.条件分支语句&#xff08;1&#xff09;说明&#xff08;2&#xff09;例子&#xff08;case和unique case的…...

【点击劫持漏洞(附测试代码)】

漏洞描述 点击劫持&#xff08;Clickjacking&#xff09;是一种网络攻击技术&#xff0c;攻击者通过将一个恶意的页面或按钮隐藏在合法网站的页面下&#xff0c;诱使用户在不知情的情况下点击隐藏的内容&#xff0c;从而触发攻击者设计的操作。这种攻击通常会导致用户无意中执…...

【AD】3-4 在原理图中放置元件

1.打开原理图库&#xff0c;选中元件点击放置 2.点击工程右键&#xff0c;选择&#xff0c;&#xff0c;进行编译&#xff0c;点击Components&#xff0c;选中鼠标点击拖动即可...

协程2 --- 相关概念

文章目录 协程切换方案协程库的完善程度协程栈方案协程调度实现有栈协程与无栈协程对称协程与非对称协程 协程切换方案 具体使用和解析看栈切换那个博客 使用setjump、longjump c语言提供的方案 可参考&#xff1a;libmill 使用操作系统提供的api&#xff1a;ucontext、fiber …...

Hadoop-005-HDFS分布式文件存储原理

一、HDFS数据如何存储 分布式存储&#xff1a;每个服务器&#xff08;节点&#xff09;存储文件的一部分, 本文提到的part只是为方便理解, 指的文件部分数据, 并不是真实存在的概念 #mermaid-svg-qjJMG6r2bzRNcWkF {font-family:"trebuchet ms",verdana,arial,sans-s…...

【多线程入门篇】 创建线程以及线程的属性

大家好呀 我是浪前 今天给大家讲解的是创建线程以及线程的属性 祝愿所有点赞关注的人&#xff0c;身体健康&#xff0c;一夜暴富&#xff0c;升职加薪迎娶白富美!!! 点我领取迎娶白富美大礼包 &#x1f353;多线程编程: 前言&#xff1a; 我们为什么不用多进程&#xff1f;…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...

6.计算机网络核心知识点精要手册

计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法&#xff1a;数据与控制信息的结构或格式&#xff0c;如同语言中的语法规则语义&#xff1a;控制信息的具体含义和响应方式&#xff0c;规定通信双方"说什么"同步&#xff1a;事件执行的顺序与时序…...