class Node():
def __init__(self,value,next=None):
self.value = value
self.next = next
def createLink(n):
if n<=0:
return False
elif n ==1:
return Node(1)
else:
root = Node(1)
tmp = root
for i in range(2,n+1):
tmp.next = Node(i)
tmp = tmp.next
tmp.next = root
return root
def showLink(root):
tmp = root
while True:
print(tmp.value)
tmp = tmp.next
if tmp ==None or tmp == root :
break
def josephus(n,k):
if k ==1 :
print("幸存者:",n)
return
root = createLink(n)
tmp = root
while True:
for i in range(k-2):
tmp = tmp.next
print("killed:",tmp.next.value)
tmp.next = tmp.next.next
tmp = tmp.next
if tmp.next == tmp:
break
print("survive:",tmp.value)
if __name__ =='__main__':
josephus(10,13)
计算结果:
killed: 3
killed: 7
killed: 2
killed: 10
killed: 1
killed: 6
killed: 8
killed: 9
killed: 4
survive: 5
def josephus(n, m):if type(n) != type(1) or n <= 0:
raise Exception('n must be an integer(n >0)')
if n == 1:
return 0
else:
return (josephus(n - 1, m) + m) % n
if __name__ == '__main__':
print josephus(8, 3)
print josephus(1, 2)
print josephus(0, 2)
# totalNum:猴子总数# startNum:开始序号
# intervalNum:间隔数
def KingElect(totalNum, startNum, intervalNum):
monkeyList = []
out_order = 0 # 出列排序
current_index = 0 # 当前列表下标
if (totalNum < intervalNum):
return
monkeyId = startNum # 猴子初始排列
for i in range(1, totalNum + 1):
if monkeyId == totalNum + 1:
monkeyId = 1
monkeyList.append(monkeyId)
monkeyId += 1
# print(monkeyList, end='')
while (len(monkeyList) > 1):
out_order += 1
current_index += 1
if (current_index > len(monkeyList)):
current_index = 1
if (out_order == intervalNum):
intervalNum += 1
out_order = 0
print('--', monkeyList[current_index - 1], 'Out')
monkeyList.pop(current_index - 1)
print( end='')
current_index -= 1
print('--', monkeyList[0], 'Gain the elect')
if __name__ == '__main__':
KingElect(60, 1, 2)