支持任意方向计数的通用约瑟夫问题Python算法优化问询

问题核心原因 #

原有代码的add函数修正逻辑仅在初始数组长度下符合计数预期，数组弹出元素长度缩短后，正负移位的索引起点更新规则没有统一对齐，导致后续索引计算出现偏移。

优化思路 #

Python 内置的取模运算符%天然支持负数运算，返回结果永远和除数（数组长度）同号，也就是结果必然落在0 ~ len(arr)-1的合法索引范围内，无需额外分支判断修正负数索引。

优化后代码（最简无额外分支版本） #

如果你定义shift为从当前起始位置的下一个元素开始移动的步数（正数向右，负数向左，移动后到达的位置即为淘汰位置），可以完全删除冗余的add函数，代码如下：

def josephus(arr, start, shift):
    if len(arr) == 1:
        return arr
    # 单行统一计算淘汰索引，正负移位通用，无额外判断
    pop_idx = (start + shift) % len(arr)
    arr.pop(pop_idx)
    print(arr)
    # 下一轮起始位置即为当前淘汰位置（pop后后续元素前移，该位置就是下一轮计数起点）
    return josephus(arr, pop_idx, shift)

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

适配计数个数场景的版本 #

如果你需要保持shift的定义为计数的总个数（从当前起始位置作为第1个开始数，数到第abs(shift)个淘汰，正负代表方向），仅需要把索引计算逻辑调整为如下，仅保留1次符号判断，无其他额外分支：

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

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

验证说明 #

两种版本均支持任意正负shift取值，无需额外边界判断，运行逻辑完全统一，不会出现后续索引计算错误的问题。

内容的提问来源于stack exchange，提问作者lesobrod