Limboy
·
100 个囚犯的随机选择问题
💡
原文中文，约2400字，阅读约需6分钟。
📝
内容提要
一百名囚犯被随机分配编号，需在50步内找到自己的编号。通过链表策略，囚犯可以提高找到自己编号的成功率至30%以上。囚犯按抽屉数字指向下一个抽屉，形成环状链表，若链表长度不超过50，则必能找到自己的编号。如果能交换抽屉内的数字，成功率可达100%。
🎯
关键要点
- 有100个囚犯，每人被随机分配1到100的编号，需在50步内找到自己的编号。
- 囚犯之间不能互相传递信息，但可以事先商定策略。
- 随机打开抽屉的方式成功率极低，约为10的-31次方。
- 通过链表策略，囚犯可以将成功率提高到30%以上。
- 每个抽屉的数字指向下一个抽屉，形成环状链表，若链表长度不超过50，则必能找到自己的编号。
- 成功的概率是1减去链表长度大于50的概率，形成链表的可能性为1/n。
- 如果囚犯可以交换抽屉内的数字，成功率可达100%。
❓
延伸问答
囚犯如何在50步内找到自己的编号？
囚犯可以通过链表策略，按照抽屉内数字指向下一个抽屉的方式进行查找，形成环状链表。
随机打开抽屉的成功率有多低？
随机打开抽屉的成功率极低，约为10的-31次方。
链表策略如何提高成功率？
链表策略可以将成功率提高到30%以上，因为如果链表长度不超过50，囚犯必能找到自己的编号。
如果囚犯可以交换抽屉内的数字，成功率会怎样？
如果囚犯可以交换抽屉内的数字，成功率可达100%。
形成链表的条件是什么？
形成链表的条件是抽屉内的数字指向下一个抽屉，且链表长度不超过50。
成功找到编号的概率是如何计算的？
成功找到编号的概率是1减去链表长度大于50的概率，形成链表的可能性为1/n。
➡️
