描述
据说著名历史学家 Josephus有过以下的故事:Josephus及他的朋友共41人围成一个圆圈,由第1个人开始报数,每数到3该人就必须出去,然后再由下一个人重新报数,直到圆圈上少于3人为止。Josephus 将朋友与自己安排在第16个与第31个位置,成为最后剩下的人。
扩展这个问题,当人数为n,每次报数为k时,求解最后的K-1个剩下的人的位置
输入格式
在同一行内输入两个正整数n和k,要求k > = 2且n >= k
输出格式
以列表形式显示剩余的人的序号(如果k<2 或者n<k,打印”Data Error!”)
我们先看原始问题:
41个人的圆圈我们可以用一个列表来模拟:
print(list(range(1,42)))
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41]
每数到3退出,下一个人重新报数,相当于把下一个人的序号变为0,把前面越过的两个人接到队尾去。循环操作,直到列表长度小于3为止,输出列表元素。循环操作,直到列表长度小于3为止,输出列表元素:
注意:列表元素的序号从0开始,第3个元素序号为2
ls = list(range(1,42)) # 产生1-41的列表
while len(ls) > 2: # 当列表剩余元素数量多于2时
ls = ls[3:] + ls[:2] # 切片再拼接,去掉序号为2的元素,重新拼接为一个列表
print(ls) # 输出列表
# [16, 31]
为使程序具有通用性,可以将其定义为一个函数,由用户输入总人数和所报数字,当用户输入不符合要求时,输出’Data Error!’
def Josephus(n,k):
ls_n = list(range(1,n+1))
while len(ls_n) > k-1:
ls_n = ls_n[k:] + ls_n[:k-1]
return ls_n
n,k = map(int,input().split())
if k >= 2 and n >= k:
print(Josephus(n,k))
else:
print('Data Error!')