前几天看到网上一道题,大致内容是:有10000瓶无色无味的药剂,其中1瓶有毒,先有10只小白鼠及足量的试管,怎样找出有毒的那瓶。
程序员看到这个问题的第一反应应该是二分法。但仔细想了一下,感觉二分法不太好,首先,要觉得,两组是同时进行还是先后进行。
同时,进行的好处是用1只小白鼠的代价,确定了5000瓶的范围。但先后进行的好处是,同样的实验,但确定第一组没问题,也可以确定,这样就节省1只小白鼠。但节省1只小白鼠这个事导致问题复制了。
由此引申一下,可以用另一个方法,10000瓶药剂,分成11组,前10组每组900瓶,最后一组1000瓶。然后,前10组,每组1只小白鼠,同步实验。这样可以用1只小白鼠的代价确定900瓶的范围或没有小白鼠损失确定1000瓶的范围。这比5000瓶的范围要好很多。
而且要考虑药剂混合的层本(主要考虑耗时,计算机领域嘛),以及等待小白鼠的药物反应层本。
这里把任务分组后,每一组看做一个出来任务,任务和CPU等资源的匹配问题也是需要考虑的问题。
记下这个,提醒自己