问题描述:传说有这样一个故事,在罗马人占领乔塔帕特后,39 个犹太人与约瑟夫及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,第一个人从1开始报数,依次往后,如果有人报数到3,那么这个人就必须自杀,然后再由他的下一个人重新从1开始报数,直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是,约瑟夫要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,从而逃过了这场死亡游戏 。
    问题转换:41个人坐一圈,第一个人编号为1,第二个人编号为2,第n个人编号为n。
    1.编号为1的人开始从1报数,依次向后,报数为3的那个人退出圈;
    2.自退出那个人开始的下一个人再次从1开始报数,以此类推;
    3.求出最后退出的那个人的编号。

    解决方式:

    1. 顺序表
    2. 链表

    代码实现:
    顺序表:求解Josephus(5,1,3)问题
    共5个节点,从节点1开始报数,数到3时删除当前节点

    1. public

    核心代码为:

    • start = (start + distance - 1) % n
    • list.remove(start)
    • n--