二分入门之芯片检测

刚学算法设计与分析，入门二分，便拿课本题目练练手。

项目地址：github/DivideAndConquer/TestChip/

题意

有n片芯片，已知其中好芯片比坏芯片至少多一片，现在需要通过测试从中找出一片好芯片。测试方法是：将两篇芯片放到测试台上，2片芯片互相测试并报告测试结果：“好”或者“坏”。假定好芯片的报告是正确的，坏芯片的报告是不可靠的（可能是对的，也可能是错的）。设计一个算法，使用最少的测试次数来找出一片好芯片。

代码设计

#include <iostream>
#include <vector>

using namespace std;

#define TEST_NUM 11

//芯片结构体
struct Chip {
    int id;
    bool isok;
};

//测试芯片答案结构体，ans1为第一个芯片检测第二个芯片的结果，ans2相反
struct Ans {
    bool ans1;
    bool ans2;
};

//简单的初始化芯片函数
void Init(vector<Chip> *initVector) {
    for (int i = 0; i < TEST_NUM; i++) {
        Chip testChip;
        testChip.id = i;
        if (i % 2 == 1) {
            testChip.isok = false;
        } else {
            testChip.isok = true;
        }
        initVector->push_back(testChip);
    }
}

//显示容器内容
void Show(vector<Chip> showVector) {
    for (int i = 0; i < showVector.size(); i++) {
        cout << showVector[i].id << "|" << showVector[i].isok << endl;
    }
}

//测试芯片，内有两个bool
Ans CheckChip(Chip c1, Chip c2) {
    Ans ans;
    if (c1.isok) {
        ans.ans2 = c2.isok;
    } else {
        ans.ans2 = rand() % 2;
    }
    if (c2.isok) {
        ans.ans1 = c1.isok;
    } else {
        ans.ans1 = rand() % 2;
    }
    return ans;
}

int main() {
    //定义两个容器，用于存放当前的芯片以及通过的芯片
    vector<Chip> testVector[2];

    //初始化
    Init(&(testVector[0]));

    //用于保存结果的芯片在哪个容器
    int ansPos;

    //开始二分检测
    for (int i = 0;; i++) {

        //定义当前的容器以及另外一个容器的下标
        int pos = i % 2;
        int otherPos = (i + 1) % 2;

        //两两组合检测
        for (int j = 0; j < testVector[pos].size(); j = j + 2) {

            //检测结果都是好的，将其中一个加到另外一个容器
            if (j == testVector[pos].size() - 1) {
                testVector[otherPos].push_back(testVector[pos][j]);
            } else {
                //其余情况都抛弃
                Ans ans = CheckChip(testVector[pos][j], testVector[pos][j + 1]);
                if (ans.ans1 && ans.ans2) {
                    testVector[otherPos].push_back(testVector[pos][j]);
                }
            }
        }

        //清除当前容器
        testVector[pos].clear();

        //判断是否完成
        if (testVector[otherPos].size() <= 1) {
            ansPos = otherPos;
            break;
        }
    }
    cout << "ans" << endl;
    Show(testVector[ansPos]);
    return 0;
}