【计算机】如何科学的扔鸡蛋？计算机算法的研究

粉丝福利 

严伯钧的硬派科普秀交流群来啦，跟着严老师一起聊聊科普、了解物理界新动向、第一时间get严老师的活动消息，还有不定期的社群活动福利哦。

入群方式

微信添加yan_bojun，并回复：科普秀，我们将会邀请你入群。

欢迎每一位在听《严伯钧的硬派科普秀》的你的到来。

精华笔记 

计算机研究的前沿领域是算法的研究。

一、什么是算法？

1. 算法就是在面对一个具体问题的时候，计算机所采取的解决问题的方法；

2. 譬如有两个鸡蛋和一栋一百层高的建筑，我们现在要检验从哪一层楼开始扔鸡蛋，鸡蛋会碎；

3. 比较笨的办法当然是用一个鸡蛋一层层地往下扔。但是如果运气不好，最多要试100次鸡蛋才会碎；

4. 因为我们有两个鸡蛋，比较聪明的办法是先每10层楼扔一次鸡蛋，试出具体是第几个十层开始鸡蛋会碎。譬如扔到80层的时候，鸡蛋碎了，那么第二个鸡蛋就可以从71层开始扔，最多再扔9次就可以试出结果。很显然这种算法比第一种算法快；

5. 算法研究就是针对同一个问题，尽量找到快速的方法，让计算的步骤减少；

二、复杂度

6. 算法有复杂度的概念，也就是针对一个具体问题，某个算法最多要多少步能完成解答。如果问题的规模是N的话，复杂度通常是关于N的函数；

7. 譬如你从图书馆借了64本书，但是走出图书馆的时候警报器响了，已知其中只有一本书没有消磁，那么应该怎么利用警报器测试出哪本书没有消磁呢？

8. 比较笨的方法，当然是一本本地试，最多要试64次才能试出来，这种算法的复杂度就是64；

9. 另一种算法是你可以把64本书分成两组，每组32本，看哪组会让警报器响。再把响的那一组分成两组，再去试，重复刚才的操作，只要6次就能试出结果。这个算法的复杂度就是6，也就是log2^N；

10， 很明显第二种算法的复杂度是更低的，算法的研究就是要尽量找到复杂度低的算法；

三、加密算法

11. 解决问题的算法基本都是解密算法，与之相应的还有加密算法；

12. 例如在一个荒岛上有两个人A和B。A有一把锁叫A锁，只有A自己的钥匙可以打开，B也有一把锁叫B锁，只有B自己的钥匙可以打开。A和B分别在小岛两端，这时B受了伤，A手上有药，岛上还有一个人C可以负责运送药物。A有一个箱子，这个箱子上可以挂多把锁。A想要把药放在箱子里让C运送给B，又不想让C有机会偷走箱子里的药。问A和B要怎么操作，才能成功地把药送到B手上？

13. 可行的操作是这样的：A先把药放在箱子里，用A锁把箱子锁上，让C把上锁的箱子带给B。B再把自己的锁也锁在箱子上，再让C把箱子带给A。A解开自己上的A锁，再让C把箱子带给B，最后B解开自己上的B锁，就能拿到药了。这就是所有加密过程的基本逻辑。