生产线测试
题目背景
工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有n条生产线（编号0～n-1），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为1），否则正常收货（记为0）。受售后压力限制，在所有发货批次中，最多只能有k次退货（即结果为1的次数≤k）。工厂的目标是，设计最少的间接测试轮数w（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。
以下程序实现了工厂的目标，包含两部分：
i) 确定w的最小值，并设计最优测试方案；
ii) 根据测试结果推断存在缺陷的生产线。
该程序确定w最小值的方法为：由于不同的生产线故障时，测试应当返回不同的结果，因此w轮测试的可能结果数不应少于生产线数量。
`test_subset()` 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第1批次、最高位是第w批次）；其实现在此处未给出。
`test_subset()` 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第1批次、最高位是第w批次）；其实现在此处未给出。
试补全程序。
include <algorithm>
include <cstddef>
include <iostream>
include <vector>
using namespace std;
long long comb(int w, int i) { // 计算组合数C(w,i)
if (i < 0 || i > w) {
return 0;
}
long long res = 1;
for (int t = 1; t <= i; ++t) {
res = res * (w t + 1) / t;
}
return res;
}
long long count_patterns(int w, int k) { // 计算长度为w、1的个数≤k的码字总数
long long total = 0;
for (int t = 0; t <= min(w, k); ++t) {
total += comb(w, t);
}
return total;
}
int test_subset(const vector<vector<int>> &plan); // 抽象测试接口
int solve(int n, int k) {
// 第1步：求最小w
int w = 1;
while ( ① ) { // ①处待完善
++w;
}
cout << w << endl;
// 第2步：生成n个长度为w、含1的数量不超过k的二进制串，保存在code里面
vector<vector<int>> code(n, vector<int>(w, 0));
int idx = 0;
for (int ones = 0; ones <= k && idx < n; ++ones) {
vector<int> bits(w, 0);
fill(bits.begin(), bits.begin() + ones, 1);
do {
for (int b = 0; b < w; ++b) {
code[idx][b] = bits[b];
}
++idx;
if (idx >= n) {
break;
}
} while ( ② ); // ②处待完善
}
// 第3步：生成测试方案plan
vector<vector<int>> plan(w);
for (int i = 0; i < w; ++i) {
for (int j = 0; j < n; ++j) {
if ( ③ ) { // ③处待完善
plan[i].push_back(j); // 将第j条生产线产品混合到第i轮测试
}
}
}
// 第4步：调用测试接口
int signature = test_subset(plan);
// 第5步：结果解码，将signature转为二进制串sig_bits
vector<int> sig_bits(w, 0);
for (int i = 0; i < w; ++i) {
if ( ④ ) { // ④处待完善
sig_bits[i] = 1;
}
}
// 第6步：匹配sig_bits与code，找到缺陷生产线
for (int j = 0; j < n; ++j) {
if ( ⑤ ) { // ⑤处待完善
return j;
}
}
return -1;
}
int main() {
int n, k;
cin >> n >> k;
int ans = solve(n, k);
cout << ans << endl;
return 0;
} (1)．①处应填？
| A． (1 << w) < n |
B． count_patterns(w, k) < n |
| C． count_patterns(k, w) < n |
D． comb(w, k) < n |
⑤处应填？
| A． is_permutation(code[j].begin(), code[j].end(), sig_bits.begin()) |
B． code[j] == sig_bits |
| C． plan[j] == sig_bits |
D． code[j][i] == sig_bits[i] |
④处应填？
| A． (signature>>i) & 1 |
B． (signature >> i) ^ 1 |
| C． signature | (1 << i) |
D． (signature >> 1) | 1 |
③处应填？
| A． (j>>i) & 1 |
B． (i >> j) & 1 |
| C． code[i][j] = 1 |
D． code[j][i] == 1 |
②处应填？
| A． next_permutation(bits.begin(), bits.end()) |
B． prev_permutation(bits.begin(), bits.end()) |
| C． next_permutation(bits.begin(), bits.begin() + ones) |
D． prev_permutation(bits.begin(), bits.begin() + ones) |
