完善程序（二） 6-10题 组合题 生产线测试 题目背景 工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有n条生产线（编号0～n-1），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为1），否则正常收货（记为0）。受售后压力限制，在所有发货批次中，最多只能有k次退货（即结果为1的次数≤k）。工厂的目标是，设计最少的间接测试轮数w（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。 以下程序实现了工厂的目标，包含两部分： i) 确定w的最小值，并设计最优测试方案； ii) 根据测试结果推断存在缺陷的生产线。 该程序确定w最小值的方法为：由于不同的生产线故障时，测试应当返回不同的结果，因此w轮测试的可能结果数不应少于生产线数量。 `test_subset()` 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第1批次、最高位是第w批次）；其实现在此处未给出。 `test_subset()` 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第1批次、最高位是第w批次）；其实现在此处未给出。 试补全程序。 include include include include using namespace std; long long comb(int w, int i) { // 计算组合数C(w,i) if (i w) { return 0; } long long res = 1; for (int t = 1; t > &plan); // 抽象测试接口 int solve(int n, int k) { // 第1步：求最小w int w = 1; while ( ① ) { // ①处待完善 ++w; } cout > code(n, vector (w, 0)); int idx = 0; for (int ones = 0; ones bits(w, 0); fill(bits.begin(), bits.begin() + ones, 1); do { for (int b = 0; b = n) { break; } } while ( ② ); // ②处待完善 } // 第3步：生成测试方案plan vector > plan(w); for (int i = 0; i sig_bits(w, 0); for (int i = 0; i > n >> k; int ans = solve(n, k); cout << ans << endl; return 0; }
正确答案：完善程序①答案：count_patterns(w,k)<n（结果数不足时增大w）。核心：求最小测试轮数。
试卷来源：2025 CSP-S提高级（第一轮）C++真题