首页 > 试题广场 >

约瑟夫问题II

[编程题]约瑟夫问题II

热度指数：9961 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现有n个人围坐一圈，顺时针给大家编号，第一个人编号为1，然后顺时针开始报数。第一轮依次报1，2，1，2...没报1的人出局。接着第二轮再从上一轮最后一个报数的人开始依次报1，2，3，1，2，3...没报1的人都出局。以此类推直到剩下以后一个人。现给定一个int n，要求返回最后一个人的编号。

测试样例：

返回：5

算法知识视频讲解

Python

✔Shawn✘

#用字典来解决约瑟夫问题

# -*- coding:utf-8 -*-
class Joseph:
def getResult(self, n):
# write code here
dic = {}
for i in range(1,n+1):
dic[i] = 0
k = 2
t = 1
while len(dic) > 1:
if t == 1:
j = 1
for i in dic:
if j > k:
j =1
dic[i] = j
j += 1
k += 1
t += 1
for i in dic.keys():
if dic[i] != 1:
dic.pop(i)
else:
if t == 2:
rese = []
for i in dic:
rese.append(i)
rese.insert(0,rese.pop())
i = len(rese)
while i > 0:
j = 1
for p in range(len(dic)):
if j > k:
j = 1
dic[rese[p]] = j
j += 1
i = i -1
k += 1
t += 1
for i in dic.keys():
if dic[i] != 1:
dic.pop(i)
rese.remove(i)
for i in dic.keys():
return i

编辑于 2018-11-14 23:29:46 回复(0)

Python

张淮

# -*- 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]

发表于 2017-07-15 13:10:27 回复(0)

Python

Yannyezixin

思路请参考第一赞的回答

# -*- 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

编辑于 2016-08-08 07:49:50 回复(1)