首页 > 试题广场 >

约瑟夫环

[编程题]约瑟夫环
  • 热度指数：17977 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}有 n 个人（编号 0\sim n-1）围成一圈，从编号为 k 的人开始报数，报数依次为 1,2,\dots,m，报到 m 的人出队。下次从出队者的下一个人开始重新报数，循环往复，直到队伍中只剩最后一个人，该人即"大王"。

\hspace{15pt}给定三个正整数 n,k,m，请输出最后剩下的"大王"编号。

输入描述:
\hspace{15pt}在一行中输入三个整数 n\left(2 \leqq n \leqq 100 \right),k\left(0 \leqq k \leqq n-1\right),m\left(1 \leqq m \leqq 100\right)，用空格隔开。


输出描述:
\hspace{15pt}输出一个整数，表示最后剩下的"大王"编号。
示例1

输入

5 1 2

输出

3

说明

初始队列编号为 [0,1,2,3,4]，从编号 1 开始报数：

\hspace{8pt}1(1),2(2)\to 2 出队，剩余 [0,1,3,4]；

\hspace{8pt}3(1),4(2)\to 4 出队，剩余 [0,1,3]；

\hspace{8pt}0(1),1(2)\to 1 出队，剩余 [0,3]；

\hspace{8pt}3(1),0(2)\to 0 出队，剩余 [3]，输出 3。
算法知识视频讲解
添加回答
Python 3
吐你口水头像 吐你口水
import sys

if __name__=='__main__':
    data = []
    for line in sys.stdin:
        a = line.split()
        data = list(map(int,a))
   
    n,k,m = data[0],data[1],data[2]
    people = [i for i in range(n)]

    while(1):
        n = len(people)
        if n == 1:
            break

        if m/n > 1 :
            m -= n
        else:
            if m + k -1  <= n - 1 :
                people.pop(m + k -1)
                k = m + k -1
                m = data[2]

               
            else:
                people.pop((m - (n - k))-1)
                k = (m - (n - k))-1
                m = data[2]

    print(people[0])
             

发表于 2026-01-16 11:51:07 回复(0)
Python 3
celestia19881头像 celestia19881 
import sys

n,k,m=map(int,input().split())
arr=[]
for i in range(n):
    arr.append(i)
cont=k
for i in range(n-1):
    for j in range(m-1):
        cont=(cont+1)%len(arr)
    del arr[cont]

print(arr[0])

发表于 2025-10-06 17:55:40 回复(0)
Python 3
牛客83749222号头像 牛客83749222号
n,k,m=map(int,input().split())
p=list(range(n))
i=k
while len(p)>1:
    i=(i+m-1)%len(p)
    p.pop(i)
print(p[0])
发表于 2025-06-24 18:24:22 回复(0)
提交观点

问题信息

语言题 过关题目
上传者：牛客301599号
难度：
3条回答 1967浏览

热门推荐

相关试题

约瑟夫环

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号