现有n个人围坐一圈,顺时针给大家编号,第一个人编号为1,然后顺时针开始报数。第一轮依次报1,2,1,2...没报1的人出局。接着第二轮再从上一轮最后一个报数的人开始依次报1,2,3,1,2,3...没报1的人都出局。以此类推直到剩下以后一个人。现给定一个int n,要求返回最后一个人的编号。
测试样例:
5
返回:5
#用字典来解决约瑟夫问题
# -*- coding:utf-8 -*- class Joseph: def getResult(self, n): # write code here cons=[i for i in range(1,n+1)] res=n round=2 while res>1: for i in range(len(cons)): if (i+1)%round!=1: cons[i]=-1 res-=1 cons=[i for i in cons if i!=-1] cons.insert(0,cons.pop()) round+=1 return cons[0]
# -*- coding:utf-8 -*- class Joseph: def getResult(self, n): if n <= 0: return -1 con = range(1, n + 1) rest = n round = 1 while con: start = 1 for key, person in enumerate(con): if start == round + 2: start = 1 if start != 1: rest -= 1 con[key] = -1 start += 1 con = [i for i in con if i != -1] if rest == 1: return con[0] con.insert(0, con.pop()) round += 1