n个人围成一圈,顺时针编号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。
时间: 2024-05-29 09:07:55 浏览: 132
python 有n个人围成一圈,顺序排号,问最后留下的是原来第几号的那位。(示例)
5星 · 资源好评率100%
这个问题可以使用约瑟夫环(Josephus Problem)的思想来解决。假设共有n个人,从第一个人开始报数,每报到3的人出圈,我们可以依次推导出每轮出圈的人的编号:
第一轮:3, 6, 9, ..., 3k
第二轮:2, 5, 8, ..., 3k-1
第三轮:1, 4, 7, ..., 3k-1)+3) % n;
其中f(n)表示在n个人围成一圈,每报到3的人出圈的情况下最后留下的人的编号。
因此,在这个问题中,最后留下来的是原来第f(n)+1号的那位。
阅读全文