假設有2n個人圍成一個圈圈。前面n個人是好人,而後面n個人是壞人。請寫一個程式找出一個m值,當沿著圈圈處決每第m人時,所有壞人會先被處決。
def getMinimumM(K):
total = 2 * K
remainder = total
start = 1
hit = 0;
ans = K + 1 # 至少得数到n+1,所以n+1是搜索的起始值
while True:
next = start + ans - 1 # 从start开始数1,一直数到ans,位置是next
next %= remainder # remainder是剩下的人数
if next > K or next == 0: #next必须大于(否则next这个不能跨越K个人)或者等于0(因为是取模,next为0表示数到了最后一个人)
hit+=1 # 已经删掉了hit个
if hit == K:
return ans;
remainder-=1 # 删掉一个位于[n,2n]之间的
if next == 0:
start = 1 # 因为是模数运算,0就代表最后一个元素
else:
start = next # 这里start不是next+1而是next,有重新编号
else:
# 被删掉的数在前n个位置之中,这个答案是错的,继续搜索下一个
remainder = total
start = 1
hit = 0
ans+=1
n=5
m=getMinimumM(n)
print(m)
大概这种感觉
有帮助望采纳
def getMinimumM(K: int):
total = 2 * K
remainder = total
start = 1
next = 0
hit = 0
ans = K+1
while(1):
next = start+ans-1
next %= remainder
if next > K or not next:
hit += 1
if hit == K:
return ans
remainder -= 1
if not next:
start = 1
else:
start = next
else:
remainder = total
start = 1
hit = 0
ans += 1