Josephus 约瑟夫环问题图解
经典案例
古代某法官要判决 n 个犯人死刑,他有一条荒唐的逻辑,将犯人首尾的相接排成圆圈,然后从第 start 开始数起,每数到第 distance 个犯人,就拉出来处决;然后又数 distance 个,数到的犯人又拉出来处决,依次类推。剩下的最后一人可以豁免。
一群猴子排成一圈,按1,2,…,n依次编号。然后从第 start 只开始数,数到第 distance 只,把它踢出圈,从它后面再开始数,再数到第 distance 只,在把它踢出去…,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。
题意说明
采用线性表标记 n 个人,设 n = 5, start = 1, distance = 3, 5 个人分别标记为 A B C D E,
josephus(5,1,3)
环问题的求解过程如图:
算法描述
求解 Josephus 环问题, n个人,从 start 开始计数,每次数到 distance 的人出环
Java 实现
1 | /** |
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment