有1000个一模一样的瓶子,其中有999瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有10只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?
1. 将所有瓶子编号,1、2、3、... 、1000;
2. 将所有编号转换成对应二进制数, 0000000001,0000000010,0000000011,...,1111101000;
3. 给1号小白鼠吃所有二进制数最低位为1的药,如,1、3、5、7、...
给2号小白鼠吃所有二进制数中,次低位为1的药,如,2、3、4、6、...
。。。。
给10号小白鼠,吃所有二进制数中,右数第10位为1的瓶子对应的药,如,512、513、514、...
4. 最后,根据死去的小白鼠就可以推断出是哪瓶为毒药,如,第2、4、7、9个小白鼠死了,那么对应的二进制数为0101001010,即,第660瓶为毒药
原文摘自:http://www.cnblogs.com/newwayy/archive/2012/04/01/2429236.html
关于这个理解了好半天,才算有点明白,感觉效率不算很高,实际操作起来要给每只小白鼠吃500次药水,估计都撑死了,呵呵,下面是C#代码实现,接触C#不久写的很烂望见谅
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Data.Linq; namespace MouseDemo { class Program { /*1. 将所有瓶子编号,1、2、3、... 、1000; . 将所有编号转换成对应二进制数, 0000000001,0000000010,0000000011,...,1111101000; . 给1号小白鼠吃所有二进制数最低位为1的药,如,1、3、5、7、... 给2号小白鼠吃所有二进制数中,次低位为1的药,如,2、3、4、6、... 。。。。 给10号小白鼠,吃所有二进制数中,右数第10位为1的瓶子对应的药,如,512、513、514、... . 最后,根据死去的小白鼠就可以推断出是哪瓶为毒药,如,第2、4、7、9个小白鼠死了,那么对应的二进制数为0101001010,即,第660瓶为毒药! */ static void Main(string[] args) { int a = 1000; //初始化毒瓶 List<PoisonBottle> list = new List<PoisonBottle>(); for (int i = 1; i < 1001; i++) { PoisonBottle p = new PoisonBottle(); p.Id =TenToTwo(i); list.Add(p); } Random rad = new Random(); int n = rad.Next(1, 1001); foreach (PoisonBottle p in list) { if (p.Id ==TenToTwo(n)) p.IsPoison = 1; else p.IsPoison = 0; } //初始化小白鼠 List<Mouse> mouseList = new List<Mouse>(); for (int i = 1; i < 11; i++) { Mouse m = new Mouse(); m.Id = i; m.IsDead = ""; mouseList.Add(m); } //测试开始 foreach (PoisonBottle p in list) { for (int i = 1; i < 11; i++) { if (p.Id.Substring(p.Id.Length-i,1)=="1") { var mouse = (Mouse)mouseList.Where(r => r.Id == i).Single(); if (p.IsPoison == 1) mouse.IsDead = "1"; } } } //死亡老鼠 var query = mouseList.Where(p=>p.IsDead=="1"); foreach (var item in query) { Console.WriteLine("死亡老鼠:"+item.Id); } //实际有毒的瓶号 var query1 = list.Where(e=>e.IsPoison==1); foreach (var item in query1) { Console.WriteLine("有毒的瓶子:"+item.Id+"=>"+TwoToTen(item.Id)+"号瓶子有毒"); } Console.ReadLine(); } //十进制转二进制 public static string TenToTwo(int num10) { int num2=0; string str = ""; while (num10>0) { num2= num10 % 2; num10 = num10 / 2; str= num2.ToString()+str; } if (str.Length<10) { int len = str.Length; string pathStr = ""; for (int i = 0; i < 10-len; i++) { pathStr += "0"; } str = pathStr + str; } return str; } //二进制转十进制 public static int TwoToTen(string num2) { int num10 = 0; for (int i = 0; i < num2.Length; i++) { num10 += (int)Math.Pow(2, i) * Convert.ToInt32(num2.Substring(num2.Length-i-1,1)); } return num10; } public class PoisonBottle { private string id; public string Id { get { return id; } set { id = value; } } private int isPoison; public int IsPoison { get { return isPoison; } set { isPoison = value; } } } public class Mouse { private int id; public int Id { get { return id; } set { id = value; } } private string isDead; public string IsDead { get { return isDead; } set { isDead = value; } } } } } /*输出结果: 死亡老鼠:7 死亡老鼠:9 有毒的瓶子:0101000000=>320号瓶子有毒 */