Wed
11
Oct '06
C/C++丢了好久了，以前也有些地方学得不好。快找工啦，开始练习！
目前策略是做题。
希望以后能坚持一周至少搞定一题，用C/C++/STL/Java来写
下面的题目来自百度，是它的网上笔试题目。
/*
题目：
有2k个芯片，好芯片多于坏芯片，好芯片与其他芯片比较的时候，会正确给出其他芯片的好与坏，坏芯片在与其他芯片比较的时候，会随机地给出一个答案，设计算法实现找到至少一个好芯片，给出比较次数的上限.
思路：
G G | O O
G B | X ?
B G | ? X
B B | ? ?
上面B,G分别代表坏芯片和好芯片，右侧对应是结果。O表示通过，X表示不通过。?表示随机。
1.芯片排成一列，靠近的两配对比较。只留下结果为O O的。这样就只能留下（G G和B B了）
2.混洗一下（2->4,4->6,6->8...)
3.重新两两比较，再次留下O O的。跳2……
4.一直到剩下一对为止。这对就是好芯片了。
由于G数量 > B数量，混洗能使得一定至少出现一对B G或者 G B。从而每次至少去掉一对。且每次筛选完，一定还是G数量>B数量。到最后
GG GG BB的时候，再次混洗，得到GB GG BG，则能确定了。
最坏情况计算得(2+1000) X 500 /2 + 1000 = 251250
*/
#include <vector>
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
class Chip {
friend ostream& operator << (ostream & os, Chip c);
public:
Chip(bool isGood) {this->status=isGood;}
Chip() {this->status=true;}
bool isGood() {return status;}
bool checkOther(Chip c) const
{
if (!status) {
int r=(int) (rand()/(RAND_MAX+1.0)*2);
if (r) return true;
else return false;
}
else return c.status;
}
bool operator == (const bool &c) const
{
return c == status;
}
private:
bool status;
};
ostream& operator << (ostream & os, Chip c)
{
if (c.status) os << 'G';
else os << 'B';
return os;
}
void print(const vector<Chip> &v)
{
vector<Chip>::const_iterator i=v.begin();
cout << "size:" << v.size() << endl;
while(i!=v.end()) {
cout << *i << ' ';
i++;
}
cout << endl<<"---------------"<<endl;
}
int main()
{
srand(time(NULL));
//生成2k个随机芯片
vector<Chip> chips(2000,true);
int badnum=(int) (rand()/(RAND_MAX+1.0)*999+1);
cout << "Bad Chip Number:" << badnum << endl;
int tmp=badnum;
int t2=0;
while(tmp!=0)
{
t2=(int) (rand()/(RAND_MAX+1.0)*2000);
if (chips[t2]==true) {
chips[t2]=false;
tmp--;
}
}
vector<Chip> work(chips);
vector<Chip>::iterator i2;;
int size=work.size();
int cnt=0;
while(true) {
// print(work);
i2=work.begin();
while(i2!=work.end()) {
Chip c1,c2;
c1=i2[0];
c2=i2[1];
if (!(c1.checkOther(c2) && c2.checkOther(c1)))
work.erase(i2,i2+2);
else
i2+=2;
}
if (size == work.size() && size != 2000) break;
// print(work);
size=work.size();
Chip p=work[1];
for(int i=1;i<=size-3;i+=2) {
work[i]=work[i+2];
}
work[size-1]=p;
cnt++;
}
cout << cnt << endl;
//ensure every element in work is GOOD
for(i2=work.begin();i2!=work.end();i2++)
if (!(*i2).isGood()) throw "BAD chip found!";
return 0;
}
Leave a passing comment »
Leave a Reply