[复健计划][紫书]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);

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/910907.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

OpenBayes 一周速览丨Ministral-8B革新侧端AI新体验!PsyDTCorpus心理咨询数据集上线,含5k个数字孪生对话数据

公共资源速递 This Weekly Snapshots &#xff01; 5 个数据集&#xff1a; * Labelme 图像标注数据集 * TIMIT 英语方言录音数据集 * Food-101 食品图像数据集 * SVHN 真实世界图像数据集 * PsyDTCorpus 心理咨询师数字孪生数据集 1 个模型&#xff1a; * Allegro 3…

如何修改网络ip地址:一步步指南‌

在当今这个数字化时代&#xff0c;网络已成为我们日常生活与工作中不可或缺的一部分。无论是浏览网页、在线办公还是享受流媒体服务&#xff0c;稳定的网络连接和适当的IP地址管理都是确保良好体验的关键。然而&#xff0c;出于隐私保护、绕过地理限制或测试网络环境等需要&…

论 ONLYOFFICE:开源办公套件的深度探索

公主请阅 引言第一部分&#xff1a;ONLYOFFICE 的历史背景1.1 开源软件的崛起1.2 ONLYOFFICE 的发展历程 第二部分&#xff1a;ONLYOFFICE 的核心功能2.1 文档处理2.2 电子表格2.3 演示文稿 第三部分&#xff1a;技术架构与兼容性3.1 技术架构3.2 兼容性 第四部分&#xff1a;部…

如何将现有VUE项目所有包更新到最新稳定版

更新有风险,Enter要谨慎!!! 要将项目中的所有 npm 包更新到最新稳定版&#xff0c;可以使用 npm-check-updates 工具。以下是具体步骤&#xff1a; 步骤一&#xff1a;安装 npm-check-updates 首先&#xff0c;全局安装 npm-check-updates 工具&#xff1a; npm install -g…

高德 阿里231滑块 分析

声明: 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 有相关问题请第一时间头像私信联系我删…

特征检测与特征匹配方法笔记+代码分享

在一幅图像中&#xff0c;总能发现其独特的像素点&#xff0c;这些点可以被视为该图像的特征&#xff0c;我们称之为特征点。在计算机视觉领域中&#xff0c;基于特征点的图像特征匹配是一项至关重要的任务&#xff0c;因此&#xff0c;如何定义并识别一幅图像中的特征点显得尤…

【陕西】《陕西省省级政务信息化项目投资编制指南(建设类)(试行)》-省市费用标准解读系列07

《陕西省省级政务信息化项目投资编制指南&#xff08;建设类&#xff09;&#xff08;试行&#xff09;》规定了建设类项目的费用投资测算方法与计价标准&#xff0c;明确指出建设类项目费用包括项目建设费和项目建设其他费&#xff08;了解更多可直接关注咨询我们&#xff09;…

无人机干扰与抗干扰,无人机与反制设备的矛与盾

无人机干扰与抗干扰&#xff0c;以及无人机与反制设备之间的关系&#xff0c;可以形象地比喻为矛与盾的较量。以下是对这两方面的详细探讨&#xff1a; 一、无人机干扰与抗干扰 1. 无人机干扰技术 无人机干扰技术是指通过各种手段对无人机系统进行干扰&#xff0c;使其失去正…

Github配置ssh key原理及操作步骤

文章目录 配置SSH第一步&#xff1a;检查本地主机是否已经存在ssh key第二步&#xff1a;生成ssh key第三步&#xff1a;获取ssh key公钥内容第四步&#xff1a;Github账号上添加公钥第五步&#xff1a;验证是否设置成功验证原理 往github上push项目的时候&#xff0c;如果走ht…

MySQL日期类型选择建议

我们平时开发中不可避免的就是要存储时间&#xff0c;比如我们要记录操作表中这条记录的时间、记录转账的交易时间、记录出发时间、用户下单时间等等。你会发现时间这个东西与我们开发的联系还是非常紧密的&#xff0c;用的好与不好会给我们的业务甚至功能带来很大的影响。所以…

【Ant.designpro】上传图片

文章目录 一、前端二、后端 一、前端 fieldProps:可以监听并且获取到组件输入的内容 action{“/api/upload_image”} 直接调用后端接口 <ProFormUploadButtonlabel{"上传手续图片"}name{"imgs"}action{"/api/upload_image"}max{5} fieldPro…

vue3 基于element-plus进行的一个可拖动改变导航与内容区域大小的简单方法

1、先上个截图&#xff1a; 说明&#xff1a;拖动上面的分隔栏就可以实现&#xff0c;改变左右区域的大小。 2、上面的例子来自官网的&#xff1a; Container 布局容器 | Element Plus 3、拖动的效果来自&#xff1a; https://juejin.cn/post/7029640316999172104#heading-1…

Android Studio加载旧的安卓工程项目报错处理

文章目录 Invalid Gradle JDK configuration foundNDK not configuredCMake 3.10.2 was not found安装cmake适配cmake版本号 com.intellij.openapi.externalSystem.model.ExternalSystemExceptiongradle版本过低或下载不了下载gradle与依赖库超时替换gradle国内源替换Maven 仓库…

Qt中的Model与View 4:QStandardItemModel与QTableView

目录 QStandardItemModel API QTableView 导航 视觉外观 坐标系统 API 样例&#xff1a;解析一个表格txt文件 QStandardItemModel QStandardItemModel 可用作标准 Qt 数据类型的存储库。它是模型/视图类之一&#xff0c;是 Qt 模型/视图框架的一部分。它提供了一种基于…

web——sqliabs靶场——第一关

今天开始搞这个靶场&#xff0c;从小白开始一点点学习,加油&#xff01;&#xff01;&#xff01;&#xff01; 1.搭建靶场 注意点&#xff1a;1.php的版本问题&#xff0c;要用老版本 2.小p要先改数据库的密码&#xff0c;否则一直显示链接不上数据库 2.第一道题&#xff0…

Markdown快速上手(typora)

一级标题~六级标题 可以选中文本在这里直接设置&#xff0c;后面也有快捷键&#xff0c;也可以使用其语法&#xff0c;一个#&#xff0c;对应一级标题&#xff0c;两个#&#xff0c;对应二级标题&#xff0c;等。 我这里使用Ctrl1没生效是因为快捷键冲突&#xff0c;也需要注意…

一招解决Mac没有剪切板历史记录的问题

使用Mac的朋友肯定都为Mac的剪切功能苦恼过&#xff0c;旧内容覆盖新内容&#xff0c;导致如果有内容需要重复输入的话&#xff0c;就需要一次一次的重复复制粘贴&#xff0c;非常麻烦 但其实Mac也能够有剪切板历史记录功能&#xff0c;iCopy&#xff0c;让你的Mac也能拥有剪切…

在鱼皮的模拟面试里面学习有感

文章目录 1.上半场1.1.引言1.2.鱼皮的建议 2.下半场2.1中间问题 3.我的总结3.1我的体会3.2我的计划 1.上半场 今天的直播&#xff0c;第一次全程的跟下来&#xff1a;也算是放松一下~~ 1.1.引言 上半场是后来总结的&#xff0c;听的时候没有随手记录&#xff1a; 1&#xf…

windows在两台机器上测试 MySQL 集群实现实时备份

在两台机器上测试 MySQL 集群实现实时备份的基本步骤&#xff1a; 一、环境准备 机器配置 确保两台机器&#xff08;假设为服务器 A 和服务器 B&#xff09;能够互相通信&#xff0c;例如它们在同一个局域网内&#xff0c;并且开放了 MySQL 通信所需的端口&#xff08;默认是 …

MQTT从入门到精通之MQTT入门

MQTT入门 1 MQTT概述 1.1 MQTT简介 MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;由IBM于1999年开发的一种基于**"发布订阅模式"的轻量级的消息传输协议**&#xff01; 发布订阅模式是一种传统的客户端-服务器架构的替代方案&#xff0c;因为…