2 분 입문 칩 검사

알고리즘 디자인 과 분석 을 배우 자마자 입문 2 분 만 에 교과서 문 제 를 가지 고 연습 을 했다.
프로젝트 주소: github / DivideAndConquer / TestChip /
제목
n 개의 칩 이 있 는데, 그 중 좋 은 칩 이 나 쁜 칩 보다 적어도 한 조각 더 많다 는 것 을 이미 알 고 있 으 며, 지금 은 테스트 를 통 해 좋 은 칩 을 찾 아야 한다.테스트 방법 은 두 개의 칩 을 시험대 에 올 려 놓 고 두 개의 칩 을 서로 테스트 하고 테스트 결 과 를 보고 하 는 것 이다.칩 의 보고 가 정확 하 다 고 가정 하면 나 쁜 칩 의 보 고 는 믿 을 수 없다.하나의 알고리즘 을 설계 하여 최소한 의 테스트 횟수 를 사용 하여 좋 은 칩 을 찾아내다.
코드 디자인

#include 
#include 

using namespace std;

#define TEST_NUM 11

//     
struct Chip {
    int id;
    bool isok;
};

//         ，ans1                ，ans2  
struct Ans {
    bool ans1;
    bool ans2;
};

//          
void Init(vector *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 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 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;
}