老鼠试药

ゞ浴缸里的玫瑰 2024-04-17 16:54 48阅读 0赞

# 题目： #

100瓶液体，有一瓶有毒药，99瓶是水，如果老鼠喝下毒药，一周后死亡。  
请问一周时间内需要多少只老鼠才能把毒药试出来？

# 解法： #

/*
     * Copyright 2019 the original author or authors.
     *
     * Licensed under the Apache License, Version 2.0 (the "License");
     * you may not use this file except in compliance with the License.
     * You may obtain a copy of the License at
     *
     *   http://www.apache.org/licenses/LICENSE-2.0
     *
     * Unless required by applicable law or agreed to in writing, software
     * distributed under the License is distributed on an "AS IS" BASIS,
     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     * See the License for the specific language governing permissions and
     * limitations under the License.
     */
    
    package cn.com.xuxiaowei;
    
    import java.math.BigInteger;
    import java.util.*;
    
    /**
     * 老鼠试药
     * <p>
     * 100瓶液体，有一瓶有毒药，99瓶是水，如果老鼠喝下毒药，一周后死亡。
     * 请问一周时间内需要多少只老鼠才能把毒药试出来？
     * <p>
     * 注：
     * <li>每瓶液体足够多，可分为无数份。</li>
     *
     * @author xuxiaowei
     * @since 0.0.1
     */
    public class Mouse {
    
        /**
         * 瓶子总数
         * <p>
         * 瓶子的编号为：1~100
         */
        private final static int SUM = 100;
    
        /**
         * 毒药药瓶的编号（随机）
         * <p>
         * 范围：1~100
         */
        private final static int POISON_NUMBER = 1 + new Random().nextInt(SUM);
    
        /**
         * 老鼠所喝瓶子的编号的集合
         */
        private static Map<Integer, List<Integer>> mouses = new HashMap<>();
    
        /**
         * 死亡老鼠的集合
         */
        private static List<Integer> dies = new ArrayList<>();
    
        /**
         * 实验原理：
         * 根据二进制的特点（仅有1和0，相当于毒药和水），将瓶子进行编号（1-100）后转化为二进制数，
         * 再根据瓶子编号的二进制数的每位上是否为1，进行判断该瓶液体是否喂给与瓶子编号的二进制数对应的位数相同的老鼠，
         * 根据死亡老鼠的编号对应的二进制数转化为的十进制数，即为毒药的编号
         */
        public static void main(String[] args) {
    
            // 计算老鼠的数量
            int mouseNumber = mouseNumber();
    
            System.err.println("总共需要：" + mouseNumber + "只老鼠");
            System.err.println();
    
            System.err.println("验证如下：");
            System.err.println();
    
            System.err.println("假设第 " + POISON_NUMBER + " 瓶有毒");
            System.err.println();
    
            System.err.println("开始实验：");
            test();
            System.err.println("每只老鼠所喝瓶子编号如下：");
            System.err.println();
    
            for (Map.Entry<Integer, List<Integer>> entry : mouses.entrySet()) {
                System.err.println("第 " + entry.getKey() + " 只老鼠所喝瓶子的编号为：");
                System.err.println(entry.getValue());
            }
    
            System.err.println();
            System.err.println("实验结束，等待一周时间，查看结果。");
    
            System.err.println();
            System.err.println("实验结果如下：");
            System.err.println("死亡老鼠如下：");
            System.err.println(dies);
            System.err.println();
    
            System.err.print("根据死亡老鼠，计算毒药瓶的编号为：");
    
            System.err.println(die());
        }
    
        /**
         * 根据死亡的老鼠，计算毒药瓶的编号
         */
        private static int die() {
            int dis = 0;
    
            for (int i : dies) {
                dis += (int) Math.pow(2, i - 1);
            }
    
            return dis;
        }
    
        /**
         * 实验
         */
        @SuppressWarnings("all")
        private static void test() {
    
            // 遍历所有瓶子（按照编号）
            for (int i = 1; i <= SUM; i++) {
    
                // 获取瓶子编号的二进制数
                String decimalToBinary = decimalToBinary(i);
    
                // 获取瓶子编号的二进制数的长度
                int length = decimalToBinary.length();
    
                // 根据瓶子编号的二进制数的长度进行循环判断各位上的数字书否为：1
                // 使用当前瓶子编号的二进制数的长度限制循环的次数（减少计算量）
                for (int j = 1; j <= length; j++) {
    
                    // 判断数的二进制第几位（从右向左数）是否为：1
                    boolean bits = bits(i, j);
    
                    // 判断当前瓶子的某个位是否为：1，如果为：1，喝了该瓶
                    if (bits) {
    
                        // 获取老鼠所喝的瓶子
                        List<Integer> integers = mouses.get(j);
    
                        // 如果该老鼠一次都没喝（创建一个集合，用于存放该老鼠所喝的瓶子编号的集合）
                        if (integers == null) {
    
                            // 创建集合
                            integers = new ArrayList<>();
    
                            // 地址指向
                            mouses.put(j, integers);
                        }
    
                        // 喝了当前的瓶子
                        integers.add(i);
    
                        // 该瓶是否为毒药
                        if (i == POISON_NUMBER) {
    
                            // 该老鼠是否会毒死
                            dies.add(j);
                        }
    
                    }
                }
    
            }
        }
    
        /**
         * 判断数的二进制第几位（从右向左数）是否为：1
         *
         * @param i      数
         * @param number 第几位（正整数，1,2,3...）
         */
        private static boolean bits(int i, int number) {
    
            // 根据位数计算最大位为：1，其余位为：0 的数
            int pow = (int) Math.pow(2, number - 1);
    
            // 进行“与”（位）运算
            int iPow = i & pow;
    
            return iPow != 0;
        }
    
        /**
         * 计算老鼠的数量
         */
        private static int mouseNumber() {
            String decimalToBinary = decimalToBinary(SUM);
            return decimalToBinary.length();
        }
    
        /**
         * 十进制转换成二进制
         */
        private static String decimalToBinary(int decimal) {
            String valueOf = String.valueOf(decimal);
            BigInteger bigInteger = new BigInteger(valueOf);
            return bigInteger.toString(2);
        }
    
    }

运算结果：

总共需要：7只老鼠
    
    验证如下：
    
    假设第 67 瓶有毒
    
    开始实验：
    每只老鼠所喝瓶子编号如下：
    
    第 1 只老鼠所喝瓶子的编号为：
    [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]
    第 2 只老鼠所喝瓶子的编号为：
    [2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27, 30, 31, 34, 35, 38, 39, 42, 43, 46, 47, 50, 51, 54, 55, 58, 59, 62, 63, 66, 67, 70, 71, 74, 75, 78, 79, 82, 83, 86, 87, 90, 91, 94, 95, 98, 99]
    第 3 只老鼠所喝瓶子的编号为：
    [4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31, 36, 37, 38, 39, 44, 45, 46, 47, 52, 53, 54, 55, 60, 61, 62, 63, 68, 69, 70, 71, 76, 77, 78, 79, 84, 85, 86, 87, 92, 93, 94, 95, 100]
    第 4 只老鼠所喝瓶子的编号为：
    [8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, 43, 44, 45, 46, 47, 56, 57, 58, 59, 60, 61, 62, 63, 72, 73, 74, 75, 76, 77, 78, 79, 88, 89, 90, 91, 92, 93, 94, 95]
    第 5 只老鼠所喝瓶子的编号为：
    [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95]
    第 6 只老鼠所喝瓶子的编号为：
    [32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 96, 97, 98, 99, 100]
    第 7 只老鼠所喝瓶子的编号为：
    [64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
    
    实验结束，等待一周时间，查看结果。
    
    实验结果如下：
    死亡老鼠如下：
    [1, 2, 7]
    
    根据死亡老鼠，计算毒药瓶的编号为：67