有趣的算法-二进制

十以外的进制无处不在
特别是在时间单位的表达上尤为明显
比如分秒时就是60进制，
时和天之间是24进制，
天和周之间是7进制，
天到月是28/29/30/31进制不等，
月到年是12进制，
天到年是365.25进制，或者说是365/366进制，
年和世纪是100进制

二进制和十进制如何转换？

所谓的“进制”，就是用多少个字符来表示整数十进制是0～9这十个数字字符，二进制是0、1两个字符。

我们经常需要将整数在二进制和十进制之间转换如：(233)₁₀的对应二进制数为(11101001)₂，

具体是这样：

(233)₁₀=2×10²+3×10¹+3×10⁰

(11101001)₂=1×2⁷+1×2⁶+1×2⁵+0×2⁴+1×2³+0×2²+0×2¹+1×2⁰

十进制转换为二进制，采用的是“除以2求余数”的算法将整数不断除以2，每次得到的余数就是由低到高的二进制位。

“除以2”的过程，得到的余数是从低到高的次序，而输出则是从高到低，所以需要一个栈来反转次序

什么是栈（一种数据结构），我们来看个例子，一叠便条插入的待办事项放在清单的最前面；读取待办事项时，你只读取最上面的那个，并将其删除。因此这个待办事项清单只有两种操作：压入（插入）和弹出（删除并读取）。

下面来看看如何使用这个待办事项清单。这种数据结构称为栈。栈是一种简单的数据结构（先进后出）。

下面让我们分别用Scratch和Python来编写一个十进制转换为二进制的小程序吧！

参考算法流程图编写程序：

例如输入233 得出结果11101001

点我查看Scratch源码

Python实现

# 十进制 转换为二进制
def divide_by2(number):
    # 建立一个空列表用来存放求得的余数
    stack = []  # 模拟一个栈
    while number > 0:
        rem = number % 2  # 求余数
        number = number // 2  # 除以2向下取整
        stack.append(rem)  # 每次求得余数一个个压入栈中

    return stack[::-1]  # 返回栈中的倒序就是最后的二进制答案


if __name__ == '__main__':
    number = int(input("请输入一个十进制的整数"))
    print(divide_by2(number))  # 输出结果

老鼠找毒药

有7瓶药水，只有1瓶有毒,已知小白鼠喝完毒药1小时后身亡，现在有3只小白鼠和1小时的时间请找出哪瓶是毒药？

想一想如果有1000瓶药水，让你找出1瓶毒药，至少需要多少只小白鼠呢？

---

分享