原题:
1000 瓶无色无味的药水,其中有一瓶毒药,10只小白鼠拿过来做实验。喝了无毒的药水第二天没事儿,
喝了有毒的药水后第二天会死亡。如何在一天之内(第二天)找出这瓶有毒的药水?
改编版:
有n被毒酒,求检验出毒酒所用的最少小白鼠?
原题思路:
利用二进制思想
可以首先把小白鼠用二进制表示,然后
巧妙的利用1和0标志位来表示喝与不喝
比如有4瓶
00 01 10 11
就可以找两只小白鼠
1号喝3 4 (也就是所有第一位是1的)
2号喝1 2就可以得到所有情况
如果1号死了就是3有毒
2死了就是2有毒
1 2都死了就是4有毒
都没死就是1有毒
这样就很巧妙的解出了原题,1000小于2^10(1024),按刚才的逻辑10只就可以找出毒酒
改编版题解:
通过找规律可以得出(2^n)+1~2^(n+1)之间都是需要n+1只
就可以先判断这个数是不是2的幂,有三种方法
1、判断此数二进制中是不是有一个1,具体算法自己实现;
2、x == x&(-x) 由于x&(-x)返回的是从右到左第一个1所表示的大小;对于110010000 返回的就是 10000;所以可以用来判断;
3、x&(x-1)==0 举个例子:1000 它减1变成 0111 与运算得0 所以是2的幂次方;
然后循环一下就可以了,每次除2,如果是2的幂最后再加上1就是结果了。
奉上鄙人的代码:
#include <stdio.h> #include <stdlib.h> #include <math.h> int main() { int t,n,i,ans; scanf("%d",&t); for(i=0;i<t;i++){ scanf("%d",&n); ans=0; if(n&(n-1)!=0){ ans++; } while(n/2>=1){ n/=2; ans++; } printf("%d ",ans); } return 0; }
总结:
有的时候看似不可能的问题总是能找到巧妙的解法,尤其是一件事物有二面性的时候,
一定要考虑二进制,当然二进制用的6还要熟练位运算qwq