算法设计:找出诚实的人
一个地方有两种人：诚实的人和骗子，诚实的人只说真话，骗子可能说真话也可能说假话，已知的是这里诚实的人比骗子要多，而且当地人知道这里其他的人是骗子还是诚实的人。
你来到这里，要求找出所有的骗子，你可以问这里任何的人A关于另外个人B的问题“B是不是骗子？”。设计一个找出所有骗子的算法，但是时间复杂度是O(n)
算法 设计
[解决办法]
写了一个，最坏时间复杂度O(3n)
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
/**
* 一个地方有两种人：诚实的人和骗子，诚实的人只说真话，骗子可能说真话也可能说假话，已知的是这里诚实的人比骗子要多，
* 而且当地人知道这里其他的人是骗子还是诚实的人。
* 你来到这里，要求找出所有的骗子，你可以问这里任何的人A关于另外个人B的问题“B是不是骗子？”。设计一个找出所有骗子的算法，但是时间复杂度是O(n)
*
*
*/
public class Test008 {
public static void main(String[] args) {
ArrayList<People> list = new ArrayList<People>();
// init
final int PEOPLE_COUNT = 20;
final int SWINDLER_COUNT = Math.max(1,
new Random().nextInt(PEOPLE_COUNT - 1) / 2);
for (int i = 0; i < SWINDLER_COUNT; ++i) {
list.add(new Swindler());
}
for (int i = 0; i < PEOPLE_COUNT - SWINDLER_COUNT; ++i) {
list.add(new Honester());
}
//打乱顺序
Collections.shuffle(list);
//为方便查看结果，显示序号
for(int i = 0;i < list.size();++i) {
People p = list.get(i);
p.setNum(i);
}
System.out.println("询问前");
System.out.println(list);
//获取骗子序号
ArrayList<Integer> resultList = findSwindlers(list);
System.out.println("询问后，骗子序号:");
System.out.println(resultList);
}
/**
* 找到一个诚实的人就OK
* 第一次询问序号0 ～ N-1，检测第一个人是否是骗子(说他是骗子的人数 >= N/2)
* 如果不是骗子，就可以得到结果
* 否则从N/2 ~ N-1开始询问，检测第N/2个人是否是骗子(说他是骗子的人数 >= N/4)
* ...
* 以此类推,直到找出诚实的人
* 以上询问时间为N + N/2 + N/4 + N/8 + ... 无限接近O(2n)
* 最后询问诚实的人时间复杂度为O(n)
* 故总时间复杂度为O(3n)
*/
static ArrayList<Integer> findSwindlers(ArrayList<People> list) {
boolean isHonester = false;
int start = 0;
int end = list.size();
while(!isHonester) {
int swindlerCount = 0;
People checkPeople = list.get(start);
for(int i = start;i < end;++i) {
People p = list.get(i);
if(p.say(checkPeople)) {
++swindlerCount;
}
}
if(swindlerCount >= (end - start) / 2) {
//骗子
start = (end + start) / 2;
} else {
isHonester = true;
}
}
People honester = list.get(start);
ArrayList<Integer> resultList = new ArrayList<Integer>();
for(int i = 0;i < list.size();++i) {
People p = list.get(i);
if(honester.say(p)) {
resultList.add(i);
}
}
return resultList;
}
}
abstract class People {
protected boolean isSwindler = false;
protected int num;//编号
protected void setNum(int num) {
this.num = num;
}
protected abstract boolean say(People p);
}
class Honester extends People {
public Honester() {
isSwindler = false;
}
@Override
protected boolean say(People p) {
return p.isSwindler;
}
@Override
public String toString() {
return num + "诚实";
}
}
class Swindler extends People {
public Swindler() {
isSwindler = true;
}
@Override
protected boolean say(People p) {
int seed = new Random().nextInt(2);
return seed == 0;
}
@Override
public String toString() {
return num + "骗子";
}
}
package test;
import java.security.SecureRandom;
import java.util.ArrayList;
public class TrustAndLie{
private static SecureRandom sr=new SecureRandom();
public static void main(String...args){
Group unknown=Group.generateSource();
Group lieGroup=findLieGroup(unknown);
unknown.removeAll(lieGroup);
lieGroup.assertLie();
unknown.assertTrust();
System.out.println("I got it, Lie count:"+lieGroup.size()+" Trust count:"+unknown.size());
}
private static Group findLieGroup(Group unknown){
Group sayTrust=new Group();
Group sayLie=new Group();
Group lieGroup=new Group();
while(unknown.size()>0){
People base=unknown.remove(0);
for(People people:unknown)
if(people.test(base)) sayTrust.add(people);
else sayLie.add(people);
if(sayLie.size()==sayTrust.size()) return sayLie;
if(sayTrust.size()>sayLie.size()){
lieGroup.addAll(sayLie);
for(People people:sayTrust)
if(!base.test(people)) lieGroup.add(people);
return lieGroup;
}
lieGroup.add(base);
lieGroup.addAll(sayTrust);
unknown.removeAll(sayTrust);
sayTrust.clear();
sayLie.clear();
}
return lieGroup;
}
private static class Group extends ArrayList<People>{
private static final long serialVersionUID=145658485844788783L;
public static Group generateSource(){
Group group=new Group();
int trust=0;
int lie=0;
for(int i=0;i<1000;i++){
if(sr.nextBoolean()){
group.add(new Trust());
trust++;
}else{
group.add(new Lie());
lie++;
}
}
for(int i=0;i<lie+1-trust;i++)
group.add(new Trust());
return group;
}
public void assertTrust(){
for(People people:this)
people.assertTrust();
}
public void assertLie(){
for(People people:this)
people.assertLie();
}
}
private static class People{
private boolean trust;
public People(boolean trust){
this.trust=trust;
}
public boolean test(People people){
return people.trust;
}
public void assertTrust(){
}
public void assertLie(){
}
}
private static class Trust extends People{
public Trust(){
super(true);
}
@Override
public void assertLie(){
throw new IllegalArgumentException("You're wrong!");
}
}
private static class Lie extends People{
public Lie(){
super(false);
}
@Override
public boolean test(People people){
return sr.nextBoolean();
}
@Override
public void assertTrust(){
throw new IllegalArgumentException("You're wrong!");
}
}
}
