用C++实现：芯片测试

问题描述

　　有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。
　　每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。
　　给出所有芯片的测试结果，问哪些芯片是好芯片。

输入格式

　　输入数据第一行为一个整数n，表示芯片个数。
　　第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。

输出格式

　　按从小到大的顺序输出所有好芯片的编号

样例输入

3
1 0 1
0 1 0
1 0 1

样例输出

1 3

 

思路：已知好芯片数目比坏芯片数目多，而且当遇到一个好的芯片的时候，用坏芯片去检测，有可能检验结果正确，有可能错误，而拿合格的芯片去检测，则检验结果一定是合格，所以如果在检验一个芯片的时候，其他芯片表示1的个数大于芯片总数的一半，就可以说明这个正在被检测的芯片是好的芯片。

 

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class chips
 6 {
 7 public:
 8     int get_n()  //获取芯片个数
 9     {
10         cin >> n;
11         return n;
12     }
13 
14     int get_all_chips()   //初始化原来所有芯片
15     {
16         for(int i=1;i<=n;i++)
17         {
18             for(int j=1;j<=n;j++)
19             {
20                 cin>>all_chips[i][j];
21             }
22         }
23         return 0;
24     }
25 
26     int check_chips()  //筛选出合格的芯片
27     {
28         for(int i=1;i<=n;i++)
29         {
30             for(int j=1;j<=n;j++)
31             {
32                 if(all_chips[i][j]==1)
33                 {
34                     qualified_chips[j]++;
35                 }
36             }
37         }
38     }
39 
40     int print_qualified_chips()  //输出函数
41     {
42         int flag=0;   //用flag来控制输出格式
43         for(int i=1;i<=n;i++)
44         {
45             if(qualified_chips[i]>n/2)
46             {
47                 if(flag==0)
48                 {
49                     cout << i;
50                     flag=1;
51                 }
52                 else
53                 {
54                     cout<<" "<<i;
55                 }
56             }
57         }
58     }
59 private:
60     int all_chips[21][21];   //所有芯片
61     int qualified_chips[21]={0};   //合格芯片
62     int n;
63 };
64 
65 int main(void)
66 {
67     chips chip;
68     chip.get_n();
69     chip.get_all_chips();
70     chip.check_chips();
71     chip.print_qualified_chips();
72     return 0;
73 }

注意：题目要求i=j的时候不算数，所以在判断这个芯片是否符合条件的时候，用的>而不是>=，如果在判断的时候考虑进去，就加一个等号。