简答题 偏难
#22046

生产线测试 题目背景 工厂打算通过客户反馈来间接测试生产线,从而找到存在缺陷的生产线。工厂有n条生产线(编号0~n-1),已知其中恰有一条生产线存在缺陷。每一轮…

生产线测试

题目背景

工厂打算通过客户反馈来间接测试生产线,从而找到存在缺陷的生产线。工厂有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;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。