首页 > 试题广场 >

约瑟夫问题II

[编程题]约瑟夫问题II
  • 热度指数:9917 时间限制: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
返回:5
#用字典来解决约瑟夫问题
# -*- 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)
# -*- 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)
思路请参考第一赞的回答
# -*- 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)