逛技术平台的时候,刷到一道算法题,一眼看去,就被其开头吸引了:
摘自知乎某 Google 分布式大神的一道题,技术是Google内部出的有史以来最难的一道题
嗯,距离下班还有一段时间,就看看把。
题目
包括你在内的一群计算机科学家被一帮邪恶的『数学毁灭教』的教徒们抓住了,各自分开关押,人数未知。现在,你被允许写一封邮件给狱长,狱长会帮你把这封邮件转发给其它所有人。在此之后,你们之间的交流将变得十分有限:
从明天起,每天上午,每个人必须写下一个0或者一个1,然后由狱长收集。狱长收到所有人的信息后,在心中将你们排成一个圆(顺序可以由狱长任意决定,每天都可能不一样)。
然后在当天下午,狱长会把每个人写下的那一位数字分别交给圆中位于这个人顺时针方向的下一个人。
如果某天,某位计算机科学家可以自信地把被抓的人的总数告诉狱长,并且答案正确,则全体释放;若答案错误则全体处死。
问:
(Easy)提供一个方案,使得至少99%概率下所有人能释放。
(Hard)提供一个确定性方案,使得保证所有人都能释放。
注意:狱长可能随机决定每个人在圆中的排列顺序,也可能根据你写给大家的邮件内容,或是当天大家写的数字等等,来排出某个有针对性的顺序。
注意2:所有人都是长生不老的。