FLY

i am fengdy.

0%

约瑟夫算法

发表于 更新于 分类于 ，

简介

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏；

python实现版

1
2
3
4
5
6
7
8
9
10
11
def ysf(total_num, kill_index):
    """约瑟夫算法
    :param total 总人数，从1开始
    :param kill_index 自杀索引
    """
    dq = deque(range(total_num, 0, -1))
    while len(dq) >= kill_index:
        dq.rotate(kill_index-1)
        dq.pop()
    print(dq)