负计数的约瑟夫斯问题的解决方案

Question

我想找到一般 Josephus 问题的最简单算法，即在任何方向上都有一个计数。
组合“递归列表”算法作为基础（Python）。
它适用于正向转变，从负向转变开始时效果很好，但随后出现问题。

def add(x):
    if x >= 0:
        return 1
    return -1


def josephus(arr, start, shift):
    if len(arr) == 1:
        return arr
    else:
        start = (start + shift - add(shift)) % len(arr)
        arr.pop(start)
        print(arr)
        return josephus(arr, start, shift)

size = int(input())
people = list(range(1, size + 1))
start = int(input()) - 1
shift = int(input())
print(people)
josephus(people, start, shift)

添加几个“if”语句可能会有帮助，但我不想这样做。

Answer 1

具有负值的不同行为的原因是在执行 arr.pop(start) 后，start 索引处的值（模新大小）将始终是“顺时针”（右）方向的 下一个 元素。

当偏移为负时，应镜像此效果。

所以当shift为负数时，执行pop后start减一：

    arr.pop(start)
    if shift < 0: 
        start -= 1

负计数的约瑟夫斯问题的解决方案

Solution of Josephus problem with negative count

python

algorithm

josephus