二分入门之芯片检测

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

项目地址: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;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • (1)蛮力算法 1)问题:假设条件:有n片芯片,已知其中好的芯片比坏的芯片至少多1片。问题要求:通过测试从中找出1...
    moosoo阅读 3,949评论 4 0
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 172,977评论 25 708
  • 广州这座内陆城市,偏偏有很多江洲岛。这个周末,去了生物岛,去拍蓝天、白云、小鸟。结果我只拍到了四张照片。 出了官洲...
    WiFi密码是多少阅读 566评论 0 1
  • 1.感恩父母生养之恩,有你们才有我。谢谢! 2.感恩亲人,死党,朋友,老师的支持,你们给予我负重前行中的善意,谢谢...
    心灵陪伴阅读 72评论 0 1
  • 2017我用命途多舛都不为过来形容自己 2018读书量增加 拿起古文观止 拿起国学。 拿起红学历史
    房程君宝宝阅读 152评论 0 0