美文网首页
二分入门之芯片检测

二分入门之芯片检测

作者: Chasiny | 来源:发表于2017-10-13 15:53 被阅读0次

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

    项目地址: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;
    }
    

    相关文章

      网友评论

          本文标题: 二分入门之芯片检测

          本文链接:https://www.haomeiwen.com/subject/qpizyxtx.html