726

编程入门行业动态更新时间:2024-10-08 18:31:43

726

问题如下

100瓶水，一瓶有毒，有一种试纸，不过需要一个小时才能出结果，问最少需要几片试纸才能在一小时内找到有毒的那一瓶。

答案是：7

算法思路

本地解题方案类似于布隆过滤器的算法思路。
参考我的博客：大数据查重-布隆过滤器
本题的思想就是：算法的思想就是把数字用二进制表示。

解题过程

首先我们需要准备七张试纸如下：

然后对瓶子的编号进行二进制排序
比如：
一号瓶子是000 0001；七号瓶子是000 0111；100号瓶子则是110 0100。
然后按编号把瓶子的液体滴到试纸上
比如：
一号瓶是000 0001，就把一号液体滴到1号试纸；
7好瓶是000 0111，把七号液体滴到1、2、3号试纸上。
然后静等试纸变色
如果是1、3、5、7号试纸均变色，那么对应的101 0101 = 75号瓶就是有毒的。

更多推荐

726

本文发布于:2024-03-09 02:14:23，感谢您对本站的认可！

本文链接:https://www.elefans.com/category/jswz/34/1723374.html