逻辑题目，讨论下

suquan77

同楼上，这个和一桶不一样，没法用二进制的
我倾向于排方阵然后用行和列去推，但是那样也至少要几十个，估计不是最佳算法

瞬间被插了几楼，反而翻页了啊……
猛然发现坐标还是无法排干净，虽然可以再做点什么，但是没时间了

turwater

带浪费酒的不

pharon

何处寻光: Re:逻辑题目，讨论下

不知道可行否……
注意到10X10X10=1000，联系三维坐标系，将1000桶酒堆成10X10X10的立方体，坐标单位为1（...

死4个好说，如果死了6个，XYZ怎样做匹配？

鬼手百炼

金时为开

有2次是奇数可叠加到下次进行。

snhun

何处寻光: Re:逻辑题目，讨论下
例如，若编号X1,Y1,Z1,Z2的犯人死了，那么有毒的酒坐标就是（1，1，1），（1，1，2）。

如果（1，1，1）里面有毒，那么整个X=1的人都会死，整个Y=1的人都会死，整个Z=1的人都会死。
就是说，如果（1，1，1）有毒，那么回游29个人会死哦。。。怎么可能只死6个人？

Ross

这个是ACM经典题型的加难版...
实际上是一个始终不出现最优情况的无序序列查找问题...
最优解仍然是使用分治策略...

先看原有题型：在N个样本中，有1个样本有毒，使用实验体来查找有毒样本。
根据分治策略，我们先将N个样本分为两组，每组数量为N/2，当N为奇数时，则分组时假定加入一个无毒样本，以保证分组平均。然后我们使用一个实验体服下其中一组。
然后递归该过程，最后综合所有实验体数据得到查找结果。

实验体数量则可以使用
int count = 0;
int num = 1000;
while( (num = (num + 1) / 2)!= 1) count++;
来得出

接下来看当前题，在该题中，有毒样本变成了2个。
在题目要求“确保”找出毒药的情况下，可以理解为分组时必出现最差情况。
那么在第一次分组迭代时，就有2种情况，2个毒样本在同一分组或2个毒样本分别于两个分组。
依据最差结果原则，则第一次分治后，之后需要对2个组进行查询。
则消耗count = 2 * count - 1(因为第一次分治仍然只消耗1，所以-1)

由之前代码，可以算得1000样本时，需要9名
则变成2个后，只需要9*2 - 1 = 17
...
完毕...

snhun

鬼手百炼: Re: 逻辑题目，讨论下

情况有499500种情况，问题是你怎么把这499500种情况“只用1000个酒桶”来表示出来？

如果题目是“有499500个酒桶，里面只有1个是有毒的”，那可以这么做。

可问题是我们“只有1000个桶”，问题就在这里。
你怎么把这499500个情况只用1000个酒桶来表示出来？
你能吗？

snhun

Ross: Re:逻辑题目，讨论下
实验体数量则可以使用
int count = 0;
int num = 1000;
while( (num = (num + 1) / 2)!= 1) count++;
来得出

红色标记的部分，你有什么根据？

Ross

snhun: Re: Re:逻辑题目，讨论下


红色标记的部分，你有什么根据？

这个是2分查找算法迭代次数的计算方法= =0
详见《计算机常用算法与程序设计》