负计数约瑟夫斯问题的解

Question

我想找出一般约瑟夫斯问题最简单的算法，也就是任意方向的计数。

将组合的“递归列表”算法作为基础(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