1936 哪一瓶是毒药?

本文主要是介绍1936 哪一瓶是毒药?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

哪一瓶是毒药?

Time Limit:1000MS  Memory Limit:65536K
Total Submit:360 Accepted:91

Description

记得宣讲会的时候，管大神讲过一道小白鼠测毒药的问题，现在我们来泛化一下这个问题。假设有N个瓶，由于瓶子上标签丢失，我们不知道瓶子到底是普通水还是毒药，但是唯一能确定的是，其中有且只有一瓶是毒药，其他都是普通水。由于毒药是慢性毒药，小白鼠喝下去可能要过几天才会死亡，为了节约时间，我们想一次性测出哪一瓶是毒药。但是由于实验室的小白鼠不是无限的，所以希望用尽量少的小白鼠来检测出毒药。亲爱的ACMer们，你有什么好的方案吗？

Input

有多组测试数据，每组测试数据输入一个整数N（0 < N < 10^8）

Output

输出最少使用的小白鼠数量。 

Sample Input

1
2

Sample Output

0
1
一道非常非常好的题目啊啊啊啊啊啊！！！！！好到我直接五体投地；；
思想;是这样的，我们把n个瓶子（n个状态）标号为0~~n-1，假设1到n-1全部化成二进制最多k位，，那么我们把1~n中所有第k位为1的瓶子给第一个小白鼠喝，如果小白鼠死了，那么毫无疑问，有毒瓶子的第k位为1，如果没死，那么有毒瓶子第k位为0，接下来,第k-1位所有数字为1的瓶子给第2个小白鼠喝，如果小白鼠死了，那么该有毒瓶子的第k-1位为1，否则为0，后面以此类推，，不难得出总共需要的小白鼠的个数就是n-1的二进制位数
这个神算法  据说叫警官算法，一个侦探发现的，无比佩服
#include<stdio.h>
#include<string.h>
int main()
{int n;while(~scanf("%d",&n)){int p=0;n--;while(n>=1){p++;n>>=1;//因为是右移，所以n--1的最高位必定是1，而不会是0；}printf("%d\n",p);}return 0;
}

这篇关于1936 哪一瓶是毒药?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---