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

每日一题——最小测试用例集覆盖问题

news 来源：原创 2025/8/6 12:46:40

最小测试用例集覆盖问题（C语言实现）

问题描述

假设我们有一系列测试用例，每个测试用例会覆盖若干个代码模块。

我们使用一个二维数组来表示这些测试用例的覆盖情况：

如果某个测试用例 i 能覆盖代码模块 j，则数组中 tests[i][j] = 1；
否则为 0。

目标是：找出一个最小数量的测试用例集合，使得这些用例组合起来能覆盖所有代码模块。

如果不存在这样的集合，则输出 -1。

文章目录

最小测试用例集覆盖问题（C语言实现）
- 问题描述
- 输入描述
- - 参数范围
- 输出描述
- 示例
- - 示例1
  - 示例2
  - 示例3
- 解题思路
- C语言实现（附详细注释）
- 总结

输入描述

第一行输入两个整数 n 和 m，分别代表测试用例总数和代码模块总数。
接下来的 n 行，每行输入 m 个数字 0 或 1，表示该测试用例对各个模块的覆盖情况。

参数范围

所有输入为 0 或 1
1 ≤ n ≤ 20（因为需要枚举子集）

输出描述

能覆盖所有代码模块的最小用例集合的大小；
如果不存在这样的集合，输出 -1。

示例

示例1

输入：
3 2
1 0
1 0
1 0输出：
-1

说明：所有用例都只覆盖模块0，无法覆盖模块1，返回 -1。

示例2

说明：用例0和1组合可以覆盖所有模块，也可以是用例2和3，总数最小是2。

示例3

输入：
3 2
1 0
0 1
1 1输出：
1

说明：用例2本身就可以覆盖所有模块。

解题思路

使用位掩码表示测试用例覆盖情况：
将每个测试用例的覆盖情况转化为一个整数，二进制的每一位表示对应模块是否被覆盖。
计算目标掩码：
所有模块都被覆盖时，目标掩码为 (1 << m) - 1，即低 m 位全是1。
暴力枚举所有子集：
总共有 $2^n$ 个测试用例子集，检查每个子集是否能覆盖所有模块。
更新最小数量：
如果当前子集的按位或结果等于目标掩码，说明它能覆盖所有模块，更新最小用例数量。

C语言实现（附详细注释）

#include <stdio.h>
#include <stdlib.h>#define MAX_N 20int min(int a, int b) {return a < b ? a : b;
}int main() {int n, m;scanf("%d %d", &n, &m);int tests[MAX_N] = {0};  // 每个测试用例的掩码表示（最多20个）// 读取测试用例数据并转为位掩码for (int i = 0; i < n; ++i) {int mask = 0;for (int j = 0; j < m; ++j) {int x;scanf("%d", &x);if (x == 1) {mask |= (1 << j);  // 将第j位设为1，表示覆盖第j个模块}}tests[i] = mask;}int target = (1 << m) - 1;  // 所有模块都被覆盖时的目标掩码int ans = n + 1;  // 初始设为比最大用例数多1（无效值）// 枚举所有可能的测试用例子集（从1到2^n-1）for (int subset = 1; subset < (1 << n); ++subset) {int union_mask = 0;int count = 0;for (int i = 0; i < n; ++i) {if (subset & (1 << i)) {  // 如果第i个用例在子集中union_mask |= tests[i];  // 累加覆盖模块count++;  // 子集中的用例个数}}// 如果该子集能覆盖所有模块，尝试更新最小值if (union_mask == target) {ans = min(ans, count);}}// 如果未找到有效子集，则返回-1if (ans > n) {printf("-1\n");} else {printf("%d\n", ans);}return 0;
}

总结

使用位运算可以高效表示模块覆盖情况；
暴力枚举适用于数据范围较小（如测试用例≤20）的问题；
注意边界条件，如所有模块都无法覆盖时应返回 -1。

每日一题——最小测试用例集覆盖问题

最小测试用例集覆盖问题（C语言实现） 问题描述假设我们有一系列测试用例，每个测试用例会覆盖若干个代码模块。我们使用一个二维数组来表示这些测试用例的覆盖情况： 如果某个测试用例 i 能覆盖代码模块 j，则数组中…...

编程日记 2025/8/6 12:46:40

React 文章分页

删除功能携带路由参数跳转到新的路由项 const navigate useNavigate() 根据文章ID条件渲染...

编程日记 2025/8/6 12:38:57

【技术派后端篇】Redis实现统计计数

在互联网项目中，计数器有着广泛的应用场景。以技术派项目为例，诸如文章点赞数、收藏数、评论数以及用户粉丝数等都离不开计数器的支持。在技术派源码中，提供了基于数据库操作记录实时更新和基于 Redis 的 incr 特性实现计数器这两种方案&…...

编程日记 2025/8/6 12:42:12

NHANES指标推荐：RFM

文章题目：Higher relative fat mass was associated with a higher prevalence of gallstones in US adults DOI：10.1186/s12876-025-03715-3 中文标题：在美国成年人中，相对脂肪质量越高，胆结石患病率就越高发表杂志&…...

编程日记 2025/8/6 12:43:30

嵌入式人工智能应用-第三章 opencv操作 4 灰度处理

嵌入式人工智能应用嵌入式人工智能应用-第三章 opencv操作 4 灰度处理嵌入式人工智能应用1 灰度处理2 算法2.1 均值方法2.2 最大值法2.3 分量法2.4 加权平均法（Weighted Average Method）2.5 系统自带方法 3 总结 1 灰度处理图像灰处理即是将一幅彩色…...

编程日记 2025/8/6 12:42:15

AI Agent破局：智能化与生态系统标准化的颠覆性融合！

Hi！好久不见云边有个稻草人-个人主页热门文章_云边有个稻草人的博客-本篇文章所属专栏~ 目录一、引言二、AI Agent的基本概念 2.1 定义与分类 2.2 AI Agent的工作原理 2.3 示例代码：AI Agent的基本实现三、AI Agent在企业数字化转型中的应用 …...

编程日记 2025/8/6 12:38:55

UniFlash以串口方式烧录MSPM0G3507(无需仿真器)

材料：MSPM0G3507黑钢版，只要有UART的其他版本亦可（PA14需接LED） 下载软件：UniFlash 9.1.0.5175，网址：UNIFLASH 软件编程工具 | 德州仪器 TI.com.cn 测试文件：MSPM0G30…...

编程日记 2025/8/6 8:20:57

坐标轴刻度QCPAxisTicker

一、QCPAxisTicker 概述 QCPAxisTicker 是 QCustomPlot 中控制坐标轴刻度生成和显示的基类，负责计算刻度位置和生成刻度标签。二、主要派生类类名描述QCPAxisTickerFixed固定步长的刻度生成器QCPAxisTickerLog对数坐标刻度生成器QCPAxisTickerPi专门显示π倍数…...

编程日记 2025/8/6 12:37:27

Spring Boot 版本与对应 JDK 版本兼容性

Spring Boot 版本与对应 JDK 版本兼容性以下是 Spring Boot 主要版本与所需 JDK 版本的对应关系，以及长期支持(LTS)信息： 最新版本对应关系 (截至2024年) Spring Boot 版本发布日期支持的 JDK 版本备注3.2.x (最新)2023-11JDK 17-21推荐使用 JDK 173…...

编程日记 2025/8/6 5:07:20

【MySQL】MySQL的基础语法及其语句的介绍

1、基础语法 mysql -h【主机名】 -u【用户名】 -p //登录MySQL exit或quit; //退出MySQL show database; //查看MySQL下的所有数据库 use 【数据库名】; //进入数据库 show tables; //查看数据库下的所有表名 *MySQL的启动和关闭 &am…...

编程日记 2025/8/3 5:06:59

1.计算并绘制利用附着系数曲线和制动效率曲线 clc close all %空载(no load)-1 ;满载(full load)-2 m14080; m29290; hg10.845; hg21.170; L3.950; a12.100; a22.950; b1L-a1; b2L-a2; beta0.38; %利用附着系数与制动强度的关系曲线 z0:0.01:1; phi_f1L*beta.*z./(b1z*hg1);%前…...

编程日记 2025/8/5 16:32:10

SpringCloud实战

环境准备： 1. 一台虚拟机，部署好centos7操作系统、安装好docker 2. 使用docker安装mysql数据库且启动mysql容器 3. IDEA配置的JDK版本是11 4. 前端代码启动Nginx 一、单体架构和微服务的区别？ 1. 单体架构将业务的所有功能集中在一个项目中…...

编程日记 2025/8/6 12:41:47

Cribl 对Windows-xml log 进行 -Serialize-05

The Serialize Function Description The Serialize Function is designed to transform an events content into a predefined format. Steps - Adding a Serialize Function important Select the Add Function<...

编程日记 2025/8/6 12:21:51

鸿蒙ArkUI之布局实战，线性布局（Column,Row）、弹性布局(Flex)、层叠布局(Stack)，详细用法

本文聚焦于ArkUI的布局实战，三种十分重要的布局，线性布局、弹性布局、层叠布局，在实际开发过程中这几种布局方法都十分常见，下面直接上手线性布局垂直布局（Column） 官方文档： Column-行列…...

编程日记 2025/8/6 12:43:29

缓存 --- 内存缓存 or 分布式缓存

缓存 --- 内存缓存 or 分布式缓存内存缓存（In-Memory Cache）分布式缓存（Distributed Cache）内存缓存 vs 分布式缓存内存缓存和分布式缓存是两种常见的缓存策略，它们在存储位置、访问速度和适用场景上有所不同。下面分…...

编程日记 2025/8/4 16:17:46

【Qt】QMainWindow类

🌈 个人主页：Zfox_ 🔥 系列专栏：Qt 目录一：🔥 QMainWindow 概述 🦋 菜单栏🎀 具体使用🎀 综合案例 🦋 工具栏🦋 状态栏🦋 窗口布局&a…...

编程日记 2025/8/6 12:37:26

缓存 --- 缓存击穿, 缓存雪崩, 缓存穿透

缓存 --- 缓存击穿, 缓存雪崩, 缓存穿透缓存击穿（Cache Breakdown）概念原理实际场景代码实现（互斥锁方案） 缓存雪崩（Cache Avalanche）概念原理实际场景代码实现（随机过期时间） 缓存…...

编程日记 2025/8/6 12:44:20

第五章 SQLite数据库：5、SQLite 进阶用法：ALTER 命令、TRUNCATE 操作、视图创建、事务控制和子查询的操作

1. SQLite ALTER 命令 SQLite 的 ALTER TABLE 命令允许在不完全重建表的情况下修改现有的表结构。通过 ALTER TABLE，您可以执行如重命名表名、添加新列等操作，但无法执行复杂的修改，如删除列或修改列的数据类型。语法重命名表用于重命名…...

编程日记 2025/8/6 12:46:09

【2】Kubernetes 架构总览

Kubernetes 架构总览主节点与工作节点主节点 Kubernetes 的主节点（Master）是组成集群控制平面的关键部分，负责整个集群的调度、状态管理和决策。控制平面由多个核心组件构成，包括： kube-apiserver：集…...

编程日记 2025/8/5 7:17:23

【数据结构】红黑树

红黑树（ R e d B l a c k T r e e Red\ Black\ Tree Red Black Tree）是一种自平衡二叉搜索树，也可以看作一种特化的 A V L AVL AVL 树（通过颜色规则来实现自平衡功能），都是在进行插入和删除操作时通过特定…...

编程日记 2025/8/5 13:46:27

ThreadLocal - 原理与应用场景详解

ThreadLocal 的基础概念在 Java 的多线程世界里，线程之间的数据共享与隔离一直是一个关键话题。如果处理不当，很容易引发线程安全问题，比如数据混乱、脏读等。而 ThreadLocal 这个工具类，就像是为线程量身定制的 “私人储物柜”…...

编程日记 2025/8/6 12:37:14

VS Code 远程连接服务器：Anaconda 环境与 Python/Jupyter 运行全指南。研0大模型学习（第六、第七天）

VS Code 远程连接服务器：Anaconda 环境与 Python/Jupyter 运行全指南在使用 VS Code 通过 SSH 远程连接到服务器进行开发时，尤其是在进行深度学习等需要特定环境的工作时，正确配置和使用 Anaconda 环境以及理解不同的代码运行方式非常关键。…...

编程日记 2025/8/6 5:19:36

chili3d调试6 添加左侧面板

注释前一个一个注释看对应哪个窗口无事发生子方法不是显示的窗口注释掉看看没了注释这个看看零件页面没了这个浏览器居然完全不用关的，刷新就重载了注释看看无工具栏版本 sidebar： 往框框里面加入 div({ className: style.input }, user_…...

编程日记 2025/8/5 14:26:04

Python变量全解析：从基础到高级的命名规则与数据类型指南

一、变量基础与内存机制 1.1 变量的三元构成每个Python变量由三个核心要素构成： 标识（Identity）：对象的内存地址，通过id(obj)获取（如id(name)输出0x5a1b2c3d）类型（Type&am…...

编程日记 2025/7/29 23:05:58

组装一台intel n95纯Linux Server服务器

前言笔者自己的电脑是macmini m4，平时都是使用虚拟机来充当Linux服务器（系统Ubuntu Server），但是毕竟是ARM CPU，而且黄金内存，开不了几个虚拟机（加内存不划算），所以组装…...

编程日记 2025/8/4 19:01:10

计算机网络中的网络层：架构、功能与重要性

一、网络层概述在计算机网络的分层模型中，网络层（Network Layer）位于数据链路层之上，传输层之下。网络层的主要任务是处理数据包的路由选择、转发以及分段，使得信息能够从源设备传送到目标设备。它还通过 IP协议&…...

编程日记 2025/7/30 0:44:55

Transformer系列（一）：NLP中放弃使用循环神经网络架构

NLP中放弃使用循环神经网络架构一、符号表示与概念基础二、循环神经网络1. 依赖序列索引存在的并行计算问题2. 线性交互距离三、总结该系列笔记阐述了自然语言处理（NLP）中不再采用循环架构（recurrent architectures）的原因&…...

编程日记 2025/8/6 5:07:17

(学习总结34)Linux 库制作与原理

Linux 库制作与原理库的概念静态库操作归档文件命令 ar静态库制作静态库使用动态库动态库制作动态库使用与运行搜索路径问题解决方案方案2：建立同名软链接方案3：使用环境变量 LD_LIBRARY_PATH方案4：ldconfig 方案使用外部库目标文件ELF 文…...

编程日记 2025/8/5 3:37:45

【QT】 QT中的列表框-横向列表框-树状列表框-表格列表框

QT中的列表框-横向列表框-树状列表框-表格列表框 1.横向列表框(1)主要方法(2)信号(3) 示例代码1:(4) 现象：(5) 示例代码2：加载目录项在横向列表框显示(6) 现象： 2.树状列表框 QTreeWidget(1)使用思路(2)信号(3)常用的接口函数(4) 示例代码&am…...

编程日记 2025/8/1 11:32:24

使用DeepSeek的AIGC的内容创作者，如何看待陈望道先生所著的《修辞学发凡》？

目录 1.从修辞手法的运用角度 2.从语言风格的塑造角度 3.从提高创作效率角度 4.从文化传承与创新角度大家好这里是AIWritePaper官方账号，官网👉AIWritePaper~ 《修辞学发凡》是陈望道 1932 年出版的中国第一部系统的修辞学著作，科学地总…...

编程日记 2025/8/1 20:44:55

使用 GitHub Actions 和 Nuitka 实现 Python 应用（customtkinter ui库）的自动化跨平台打包

目录引言前置准备配置文件详解实现细节CustomTkinter 打包注意事项完整配置示例常见问题引言在 Python 应用开发中，将源代码打包成可执行文件是一个常见需求。本文将详细介绍如何使用 GitHub Actions 和 Nuitka 实现自动化的跨平台打包流程，支持 W…...

编程日记 2025/8/3 20:20:17

【Part 2安卓原生360°VR播放器开发实战】第一节｜通过传感器实现VR的3DOF效果

《VR 360全景视频开发》专栏将带你深入探索从全景视频制作到Unity眼镜端应用开发的全流程技术。专栏内容涵盖安卓原生VR播放器开发、Unity VR视频渲染与手势交互、360全景视频制作与优化，以及高分辨率视频性能优化等实战技巧。 📝 希望通过这个专栏&am…...

编程日记 2025/8/4 19:02:42

【1】云原生，kubernetes 与 Docker 的关系

Kubernetes？K8s？ Kubernetes经常被写作K8s。其中的数字8替代了K和s中的8个字母——这一点倒是方便了发推，也方便了像我这样懒惰的人。什么是云原生？ 云原生： 它是一种构建和运行应用程序的方法，它包含&am…...

编程日记 2025/8/1 20:02:35

基于Redis实现RAG架构的技术解析与实践指南

一、Redis在RAG架构中的核心作用 1.1 Redis作为向量数据库的独特优势 Redis在RAG架构中扮演着向量数据库的核心角色，其技术特性完美契合RAG需求： 特性技术实现RAG应用价值高性能内存存储基于内存的键值存储架构支持每秒百万级的向量检索请求分布式架构…...

编程日记 2025/8/3 13:00:54

trivy开源安全漏洞扫描器——筑梦之路

开源地址：https://github.com/aquasecurity/trivy.git 可扫描的对象容器镜像文件系统Git存储库（远程）虚拟机镜像Kubernetes 在容器镜像安全方面使用广泛，其他使用相对较少。能够发现的问题正在使用的操作系统包和软件依赖项…...

编程日记 2025/8/5 9:31:34

pnpm确认全局下载安装了还是显示cnpm不是内部或外部命令,也不是可运行的程序

刚开始是正常使用的。突然开始用不了了一直报错 1.在确保自己node和npm都一直正常使用并且全局安装pnpm的情况下打开cmd查看npm的环境所在位置 npm config get prefix 2.接着打开高级系统设置查看自己的path配置有没有问题确认下载了之后pnpm -v还报错说明没有查询到位置 …...

编程日记 2025/7/31 7:44:00

基于 pnpm + Monorepo + Turbo + 无界微前端 + Vite 的企业级前端工程实践

基于 pnpm Monorepo Turbo 无界微前端 Vite 的企业级前端工程实践一、技术演进：为什么引入 Vite？ 在微前端与 Monorepo 架构落地后，构建性能成为新的优化重点： Webpack 构建瓶颈：复杂配置导致开发启动慢&#…...

编程日记 2025/8/2 13:56:33

软考高级系统架构设计师-第15章知识产权与标准化

【本章学习建议】根据考试大纲，本章主要考查系统架构设计师单选题，预计考3分左右，较为简单。 15.1 标准化基础知识 1. 标准的分类分类内容国际标准（IS） 国际标准化组织（ISO）、国际电工…...

编程日记 2025/8/5 22:12:36

MySQL 视图

核心目标： 学习如何创建和使用视图，以简化复杂的查询、提供数据访问控制、实现逻辑数据独立性，并通过 WITH CHECK OPTION 保证数据一致性。什么是视图？ 视图（View）是一种虚拟表，其内容由一个 …...

编程日记 2025/7/30 0:44:51

[操作系统] 信号

信号 vs IPC 板书最后提到了 “信号 vs IPC”，暗示了信号也是一种进程间通信 (Inter-Process Communication, IPC) 的机制。虽然信号的主要目的是事件通知，但它也可以携带少量的信息（即信号的类型）。初探“信号”——操作系统的“…...

编程日记 2025/7/30 0:44:49

网络基础（协议，地址，OSI模型、Socket编程......）

目录一、计算机网络发展二、协议 1.认识协议 2.OSI七层模型 3.TCP/IP 五层(或四层)模型 4.协议本质三、网络传输流程 1.MAC地址 2.协议栈 3.IP地址 IP地址 vs MAC地址 1. 核心区别 2. 具体通信过程类比 3. 关键总结为什么需要两者？ 4.协议栈图解…...

编程日记 2025/8/3 1:09:24

产品经理学习过程

一：扫盲篇（初始产品经理） 阶段1：了解产品经理了解产品经理是做什么的、产品经理的分类、产品经理在实际工作中都会接触什么样的岗位、以及产品经理在实际工作中具体要做什么事情。二：准备篇阶段2：工…...

编程日记 2025/8/5 8:07:12

深入理解Java包装类：自动装箱拆箱与缓存池机制

深入理解Java包装类：自动装箱拆箱与缓存池机制对象包装器 Java中的数据类型可以分为两类：基本类型和引用类型。作为一门面向对象编程语言， 一切皆对象是Java语言的设计理念之一。但基本类型不是对象，无法直接参与面向对象操作&…...

编程日记 2025/8/1 15:16:15

Linux中的信号量

目录信号量概念定义操作类型应用信号量封装一、创建信号量头文件函数原型参数说明返回值示例二、设置信号量初始值头文件函数原型参数解释返回值示例三、信号量的P操作头文件函数原型参数解释返回值示例四、信号量的V操作示…...

编程日记 2025/8/1 3:56:51

深入理解linux操作系统---第15讲 Web 服务器 Nginx

15.1 Nginx 概述核心特性与历史背景 Nginx由俄罗斯工程师Igor Sysoev于2002年开发，2004年正式发布，旨在解决传统服务器（如Apache）的C10K问题（即单机万级并发连接处理）。其采用事件驱动（Event…...

编程日记 2025/7/30 0:44:41

深度解析算法之前缀和

25.【模版】一维前缀和题目链接描述输入描述输出描述输出q行,每行代表一次查询的结果. 示例输入： 3 2 1 2 4 1 2 2 3 复制输出： 3 6 这个题的话就是下面的样子，我们第一行输入 3 2的意思即是这个数组是3个元素大小的数组&…...

编程日记 2025/8/3 13:53:03

混合精度训练中的算力浪费分析：FP16/FP8/BF16的隐藏成本

在大模型训练场景中，混合精度训练已成为降低显存占用的标准方案。然而，通过NVIDIA Nsight Compute深度剖析发现，‌精度转换的隐藏成本可能使理论算力利用率下降40%以上‌。本文基于真实硬件测试数据，揭示不同精度格式的计算陷阱。…...

编程日记 2025/8/3 10:38:03

6.8 Python定时任务实战：APScheduler+Cron实现每日/每周自动化调度

Python定时任务实战：APScheduler+Cron实现每日/每周自动化调度实现每日和每周定时任务关键词：定时任务调度、Python 原生调度器、Cron 脚本、异常重试机制、任务队列管理 1. 定时任务架构设计采用分层调度架构实现灵活的任务管理： #mermaid-svg-PnZcDOgOklVieQ8X {f…...

编程日记 2025/7/30 0:45:57

[Android] 豆包爱学v4.5.0小学到研究生题目Ai解析

[Android] 豆包爱学链接：https://pan.xunlei.com/s/VOODT6IclGPsC7leCzDFz521A1?pwdjxd8# 拍照解析答案【应用名称】豆包爱学【应用版本】4.5.0 【软件大小】95mb 【适用平台】安卓【应用简介】豆包爱学，一般又称河马爱学教育平台app,河马爱学。关…...

编程日记 2025/7/30 0:45:55

swift-12-Error处理、关联类型、assert、泛型_

一、错误类型开发过程常见的错误语法错误（编译报错） 逻辑错误运行时错误（可能会导致闪退，一般也叫做异常） 2.1 通过结构体第一步 struct MyError : Errort { var msg: String ｝ 第二步 func divide(_ …...

编程日记 2025/7/31 16:56:29