校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 字符串算法
题目

给你10只实验小鼠,用7天的时间检验1000个瓶子中带有一瓶毒药的瓶子是哪一瓶,小鼠喝了毒药7天后才会死亡,如何编程实现

解答

这是二进制数的一个应用,如果你看到这个题目,能够立即想到2 的 10 次方 = 1024.那你已经知道答案了

我们让第一只小鼠(红色表示)喝第4、5、6、7瓶,让第二只小鼠(蓝色表示)喝第2、3、6、7瓶,让第三只小鼠喝第1、3、5、7瓶,这样小鼠7天后就只有这八种状态,如果是 第一只活(0),第二只活(0),第三只死(1),那就可以确定是第一瓶,其他的也如此。
2的3次方 = 8,2的10次方 = 1024,所以用10只小鼠可以检验1000个瓶子的。
小鼠的状态可用0(活)、1(死)表示,也就可以用计算机实现。
其实就是进制转换的问题:将二进制转为十进制。
最后输入小鼠的状态,如0000000000,转为十进制 0,则第0瓶有毒。

public class Base {
                  /**
                   * 将数转为任意进制
                   * @param num
                   * @param base
                   * @return
                   */
                 public String baseString(int num,int base){
                        if(base > 16){
                              throw new RuntimeException("进制数超出范围,base<=16");
                        }
                       StringBuffer str = new StringBuffer("");
                       String digths = "0123456789ABCDEF";
                       Stack<Character> s = new Stack<Character>();
                       while(num != 0){
                              s.push(digths.charAt(num%base));
                              num/=base;
                       }
                       while(!s.isEmpty()){
                              str.append(s.pop());
                       }
                       return str.toString();
                  }
                 /**
                   * 16进制内任意进制转换
                   * @param num
                   * @param srcBase
                   * @param destBase
                   * @return
                   */
                 public String baseNum(String num,int srcBase,int destBase){
                        if(srcBase == destBase){
                             return num;
                        }
                        String digths = "0123456789ABCDEF";
                        char[] chars = num.toCharArray();
                        int len = chars.length;
                        if(destBase != 10){//目标进制不是十进制 先转化为十进制
                              num = baseNum(num,srcBase,10);
                        }else{
                              int n = 0;
                              for(int i = len - 1; i >=0; i--){
                                         n+=digths.indexOf(chars[i])*Math.pow(srcBase, len - i - 1);
                              }
                              return n + "";
                        }
                        return baseString(Integer.valueOf(num),destBase);
                }
}

C 0条回复 评论

帖子还没人回复快来抢沙发