计算机进制计算题（常见笔试算法题）

题目题目的形式一般是：有 n 瓶水，其中一瓶有毒假设老鼠接触毒药后 5 分钟死亡最少需要多少只老鼠才能在最短的时间找出哪瓶水有毒？（假设最少老鼠的数量为 m 吧），下面我们就来聊聊关于计算机进制计算题?接下来我们就一起去了解一下吧!

计算机进制计算题

题目

题目的形式一般是：有 n 瓶水，其中一瓶有毒。假设老鼠接触毒药后 5 分钟死亡。最少需要多少只老鼠才能在最短的时间找出哪瓶水有毒？（假设最少老鼠的数量为 m 吧）

分析

这道题目其实考的是二进制比特串能表示的状态数量。比如一个比特位能表示两种状态：0 和 1。而两个二进制比特位能表示 4 种状态：00,01,10,11。而在这个题目上下文中，老鼠也有两种状态：活和死。这样我们就可以将一只老鼠当做一个比特位，老鼠活着为 0，死了为 1。 两只老鼠就可以表示四种状态：00（活活），01（活死），10（死活），11（死死）。好了，现在我们可以用 m 只老鼠表示 2 的 m 次方种状态了。

然后我们给每瓶水从 0 开始编号。然后将某瓶水有毒对应一种状态。n 瓶水最多有 n 种状态。几只老鼠能表示的状态数，我们知道了，水可能的状态数我们也知道了。所以理论上我们只需要找到某种老鼠尝毒药的方案，5 分钟后，老鼠就会出现一种状态，只要能将老鼠的状态一一对应到水的状态，我们就能唯一辨别出哪瓶水有毒。只需要 2 的 m 次方 >= n，m 只老鼠就可以完整表示 n 瓶水的状态。满足这表达式的最小 m 就是答案。

我们先不管是怎么对应的，只知道是一一对应就行。

一个简单实例

第 0只老鼠的状态（死为 1，活为 0）第 1 只老鼠的状态（死为 1，活为 0）有毒的那瓶水的编号000011102113

所以，我们只需要 2 只老鼠就可以找出哪瓶水有毒。两只老鼠都没死，说明第 0 瓶水有毒；两只都死了就是第 3 瓶水有毒；第 0 只活着，第 1只死了就是第 2 瓶水有毒；第 0 只死了，第 1 只活着就是第 1 瓶水有毒。

我们让老鼠以某种方式尝水后，5 分钟后根据老鼠的状态就可以判断出哪瓶水有毒。

老鼠喝毒药的方案

虽然上面给出了对应关系，但是你可能不相信。活着你很好奇怎么安排老鼠喝毒药。我们现在来根据上面的对应关系，找出喝毒药的方案。

第 0 瓶水有毒时，两只老鼠都活着，说明两只老鼠都没喝第 0 瓶水。

第 1 瓶水有毒时，第 1 只老鼠死了，说明第 1 只老鼠喝了第 1 瓶水，而第 0只没喝。

第 2 瓶水有毒时，第 0只老鼠死了，说明第 0 只老鼠喝了第 2 瓶水，而第 1只没喝。

第 3 瓶水有毒时，两只老鼠都死了，说明两只老鼠都喝了第 3 瓶水。

所以方案是：

第 0 只老鼠要喝：第 2 瓶，第 3 瓶。

第 1 只老鼠要喝：第 1 瓶，第 3 瓶

根据方案和结果判断哪瓶水有毒

根据上面的方案，我们再来推一推。验证方案是否正确。

如果两只老鼠都活着，说明第 1,2,3 瓶水都没毒。有毒的自然是第 0 瓶。

如果第 0 只老鼠活着，而第 1 只老鼠死了，说明第 2 3 瓶水没毒，第 1 瓶水有毒。

如果第 0 只老鼠死了，而第 1 只老鼠活着，说明第 1 3 瓶水没毒，第 2 瓶水有毒。

如果两只老鼠都死了，说明 2 3 中有一瓶有毒，1 3 中有一瓶有毒，所以可以推出有毒的是第 3 瓶水。

总结

所以不管 n 的值是多少，根据只有 2 的 m 次方能表示大于等于 n 就行。假设 n = 1024，m = 10 就行。如果 n = 1025,10 只老鼠最多表示 1024 种状态，所以 10 只不行，得 11 只。11 只能表示 2048 种状态，肯定能识别出水的 1025 种状态。所以总结一下 m 的取值为：满足 2 的 m 次方 >= n 的最小 m 值。

通过这个问题，我们将更好地理解为什么计算机会使用二进制，只需要二进制就能表示所有的行为。

,