首页 > 试题广场 >

约瑟夫环

[编程题]约瑟夫环
  • 热度指数：21826 时间限制：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。
算法知识视频讲解
添加回答
C++
YCHG头像 YCHG
    int n, k, m;
    cin >> n >> k >> m;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        a[i] = i;

    while (a.size() > 1) {
        k = (k + m - 1) % a.size();
        a.erase(a.begin() + k);
    }
    cout << a[0] << endl;
发表于 2025-11-05 15:05:44 回复(1)
C++
追风的羽汀头像 追风的羽汀 
#include <iostream>
using namespace std;
 
int main() {
    int n,k,m; // 人数，开始位置，报数步长
    cin>>n>>k>>m;  
    int a[n];  // 标记是否出列
    int count=n;
    int cnt,num=k;  // num = k，用于标记当前报数人的位置
    for(int i=0;i<n;i++){
        a[i]=i;         // 初始化数组，每个人都有自己的编号
    }
    cnt=0;          // 计数器，当前报数的步数
    while (count>=1) {       // 还有未出列的人就循环
        if(a[num]!=-1) {     // 若当前报数人未出列
            cnt++;           // 则报数计数器+1，表示有人报数
            if(cnt==m) {     // 若数到了m！
               a[num]=-1;    // 当前人出列
               count--;      // 剩余人数--
               cnt=0;        // 报数计数归零！
            }
        } 
        if(num==n) num=1;    //假设转了一圈，则从头开始再来
        else num++;          // 
    }
    cout<<num-1<<endl;
}

发表于 2025-07-16 09:47:58 回复(0)
C++
牛客874874800号头像 牛客874874800号
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读取输入：总人数n，起始位置k，报数步长m
    int n, k, m;
    cin >> n >> k >> m;
   
    // 创建向量保存所有人员（编号0到n-1）
    vector<int> array;
    for(int i = 0; i < n; i++){
        array.push_back(i);
    }
   
    // 设置当前起始位置（确保在[0, n-1]范围内）
    int current = k % n;
   
    // 当还有超过1人时继续淘汰
    while(array.size() > 1){
        // 计算下一个要淘汰的人的位置：
        // 1. 从当前位置前进m-1步（因为报数从1开始）
        // 2. 使用当前剩余人数取模，实现环形结构
        current = (current + m - 1) % array.size();
       
        // 淘汰当前位置的人
        array.erase(array.begin() + current);
    }

    // 输出最后剩下的"大王"
    cout << array[0];
}
发表于 2025-08-19 15:40:12 回复(0)
K1m4stx头像 K1m4stx
n, k, m = map(int, input().split())
L = [i for i in range(0,n)]
for _ in range(1, n):
    k = (k+m-1)%n
    n = n-1
    L.remove(L[k])

print(L[0])

发表于 2025-06-18 00:43:21 回复(1)
C++
来吾告汝头像 来吾告汝 
#include <iostream>
using namespace std;
#include <list>
#include <iterator>

int main() {
    int n,k,m;
    cin >> n >> k >> m;
    list<int> lst;
    int count = 0;
    for(int i = 0; i < n; ++i)
    {
        lst.push_back(i);
    }

    list<int>::iterator curr = lst.begin();
    advance(curr, k);   

    while(lst.size() > 1)
    {
        ++count;
        if(count == m) 
        {
            curr = lst.erase(curr);
            if(curr == lst.end()) {curr = lst.begin();}
            count = 0;
        }
        else 
        {
            ++curr;
            if(curr == lst.end()) {curr = lst.begin();}
        }
    }
    cout << *lst.begin() << endl;
}

发表于 2025-12-14 00:19:07 回复(0)
Python3
意若久时天然呆头像 意若久时天然呆 
n,k,m=map(int,input().split())
l=list(range(n))
while n>=2:
    k=(k+m-1)%n
    l.pop(k)
    n-=1
print(*l)

发表于 2025-11-04 14:52:11 回复(0)
C
牛客709860552号头像 牛客709860552号 
#include <stdio.h>
int main() 
{
    int n, k, m;
    scanf("%d %d %d", &n, &k, &m);
    int arr[n],a=0,p=k;//arr[]s数组标记0出队，a标记出队人数，p标记当前未出队的首个报数编号
    for(int i=0;i<n;i++) arr[i] = 1;
    while(n-1-a)
    {
        for(int j=0;j<m-1;j++)
        {
            do{
              if(++p==n) p=0;
            }while(!arr[p]);//找出出队编号
        }
        arr[p]=0;
        a++;
        do{
            if(++p==n) p=0;
        }while(!arr[p]);//找出出队后下个首个报数编号
    }
    printf("%d\n",p);
    return 0;
}

发表于 2025-09-15 20:51:03 回复(0)
C
在刷题的老f很苦头像 在刷题的老f很苦
#include<stdio.h>
int main(){
    int b=0,c;          //c为总数1
    int n,k,m;          //k为起始位置
    scanf("%d %d %d",&n,&k,&m);
    int arr[n];          //存编号
    for(int i=0;i<n;i++)
        arr[i]=i;
    c=n;
    while(c>0){
        if(arr[k]!=-1)
            b++;
        if(b==m){
            if(c==1)
                printf("%d",arr[k]);
            //else
             // printf("%d->",arr[k]);
            b=0;        //重新从1记
            c--;        //出队一个，--
            arr[k]=-1;   //出队位置记为-1，下次不记
        }
        k=(k+1)%n;      //变为循环队列
    }
    return 0;
}
发表于 2026-01-02 15:41:54 回复(0)
Python3
活跃的小猫真的会谢头像 活跃的小猫真的会谢
n,k,m=map(int,input().split())
lst=list(range(n))
start=k
while len(lst) > 1:
    for _ in range(m-1):
        start = (start + 1) % len(lst)
    removed_person = lst.pop(start)
print(lst[0])
   
发表于 2025-07-30 15:40:51 回复(0)
mateng201头像 mateng201
#include <stdio.h>

int main() {
    int n, k, m;
    int cnt = 0;          // 报数
    scanf("%d %d %d", &n, &k, &m);
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = i;         // 初始化编号
    }
    int remain = n;       // 剩余人数
    // 从第 k 个人开始（下标 k-1），循环绕回
    for (int i = k - 1; ; i++) {
        if (i >= n) i = 0;          // 到达末尾则绕回头
        if (remain == 1) break;     // 只剩一人时结束
        if (a[i] != -1) {
            cnt++;
            if (cnt == m) {
                cnt = 0;
                a[i] = -1;
                remain--;
            }
        }
    }
    // 输出最后剩下的人
    for (int i = 0; i < n; i++) {
        if (a[i] != -1) {
            printf("%d", a[i]+1);
            break;
        }
    }
    return 0;
}
发表于 2026-04-04 11:54:51 回复(0)
Python3
想要offer的马来熊很爱喝奶茶头像 想要offer的马来熊很爱喝奶茶 
n, k, m = list(map(int, input().split()))
people = list(range(n))
index = k % n
while len(people) > 1:
    index = (index + m - 1) % len(people)
    people.pop(index)
print(people[0])

发表于 2026-04-01 19:52:49 回复(0)
C
在摸鱼的加菲猫头像 在摸鱼的加菲猫
#include<stdio.h>
int main()
{
    int n,k,m;
    scanf("%d %d %d",&n,&k,&m);
    int a[101]={0};
   int cur=k;
   int count=n;
   while(count>1)
   {
        int step=0;
        while(step<m)
        {
           
            if(a[cur]==0) step++;
            if(step==m) break;
            cur=(cur+1)%n;          
        }
         a[cur]=1;
         count--;
         do{
            cur=(cur+1)%n;

         }while(a[cur]==1);
       
   }
    printf("%d\n",cur);
    return 0;
}
发表于 2026-03-28 10:58:03 回复(0)
Python 3
NarduS_头像 NarduS_
n,k,m=map(int,input().split())
a=list(range(n))
while len(a)>1:
    pos=(k+m-1)%len(a)
    a.pop(pos)
    k=pos % len(a)

print(a[0])
发表于 2026-03-27 10:28:42 回复(0)
不愿吃饼的小山竹很沉稳头像 不愿吃饼的小山竹很沉稳
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Collections;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        List<Integer> list=    new ArrayList<>();
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int k = in.nextInt();
            int m = in.nextInt();
            while(n>0){
                list.add((n-1));
                 
                n--;
            }
            Collections.reverse(list);
            int index=k;
            while(list.size()>1){
             index = (index + m - 1) % list.size();
             list.remove(index);
            }

        }
        System.out.println(list.get(0));
    }
}//以最大极限来做就行，先找特殊规律n=5，k=0，m=5
发表于 2026-03-25 20:18:37 回复(0)
C
天天摸鱼的奇亚籽很犯困头像 天天摸鱼的奇亚籽很犯困
#include <stdio.h>

int main() {
    int n, k, m;
    scanf("%d %d %d", &n, &k, &m);

    int f = 0;

    for (int i = 2; i <= n; i++)
        f = (f + m) % i;
   
    printf("%d", (f + k) % n);

    return 0;
}
发表于 2026-03-10 18:22:00 回复(0)
蜜雪儿11头像 蜜雪儿11
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
       int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        in.close();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
    }
        int index = m;
        while (list.size() > 1) {
            index = (index + k - 1) % list.size();
            list.remove(index);
            if(index >= list.size()) {
                index = 0;
            }else{
                index = index % list.size();
            }

        }
        System.out.println(list.get(0));
    }
    }
发表于 2026-03-08 17:49:09 回复(0)
Java
cmhYaChiXiaoLe头像 cmhYaChiXiaoLe 
import java.util.Scanner;

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //n个人
        int n = in.nextInt();
        //从编号为k的人开始报数(编号即数组下标)
        int k = in.nextInt();
        //报到m的人出队
        int m = in.nextInt();
        //初始化队列
        List<Integer> people = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            people.add(i);
        }
        int currentIndex =
            k; //每次开始报数的人的下标，动态的、变化的。
        while (people.size() > 1) {
            //这个公式很关键，当前坐标+步数m-1 即是要移除的数的下标。 %是为了避免下标越界同时保证到最后一个数的时候环形遍历【核心！取模具有天然的环形遍历特性】
            //比如5个人，m=6,k=1 那么removeIndex=1+6-1=6,下标越界！6%5=1 则刚好吻合从下标1开始走6步到1。
            int removeIndex = (currentIndex + m - 1) % people.size();
            people.remove(removeIndex);

            //分2种情况：1、如果移除的数在最后一个数左侧，那么currentIndex=removeIndex; 2、如果移除的数是最后一个数，那么currentIndex会下标越界。
            //比如 0 1 3 4 ==> 0 1 3的过程，4被移除后，此时currentIndex=removeIndex=3,那么3在0 1 3 里开始重新计数会越界？怎么办？也会靠取模
            currentIndex = removeIndex % people.size();
            // System.out.println("当前队列：" + JSON.toJSONString(people));

        }
        System.out.println(people.get(0));

    }
}

发表于 2026-02-25 17:58:50 回复(0)
在等offer的回笼觉觉主很能干头像 在等offer的回笼觉觉主很能干
#include <stdio.h>

int main() {
    int n;
    int k;
    int m;
    scanf("%d %d %d", &n, &k, &m);
    int arr[100] = {0};
    for (int i = 0; i < n; i++) {
        arr[i] = 1;
    }

    int people = n;
    k = k - 1;
    int baoshu = 0;

    while (people != 1) {
        k++;
        baoshu++;

        while (arr[k] == 0) {
            k++;
            if (k > n - 1) {
                k = 0;
            }
        }

        if (baoshu == m) {
            arr[k] = 0;
            baoshu = 0;
            people--;
        }
    }

    int j=0;
    for (j = 0; j < n; j++) {
        if (arr[j] != 0) {
            break;
        }
    }
    printf("%d", j);

    return 0;
}
发表于 2026-02-13 23:54:05 回复(0)
gt666头像 gt666
#include<bits/stdc++.h>
using namespace std;
int n,k,m;
queue<int>q;
void gt(){
    for (int i = 0 ; i < n ; i++){
        q.push(i);
    }
    for (int i = 0 ; i < k ; i++){
        int t = q.front();
        q.pop();
        q.push(t);
    }

    while(q.size()>1){
        int temp = (m-1) % q.size();
        for (int i = 1 ; i < temp + 1 ; i++){
            int t = q.front();
            q.pop();
            q.push(t);
        }
        q.pop();
    }
    cout << q.front();
}
int main(){
    cin >> n >> k >> m;
    gt();
    return 0;
    }
发表于 2026-02-11 20:48:43 回复(0)
whisper_trap头像 whisper_trap
#include <iostream>
using namespace std;

int main() {
int n, k, m;
cin >> n >> k >> m;

// 用数组标记每个人是否还在圈里，1表示在，0表示已出队
int people[105] = {1};
for (int i = 0; i < n; ++i) {
people[i] = 1;
}

int count = 0; // 已出队人数
int current = k; // 当前报数的人的位置
int step = 0; // 当前报的数字

// 直到只剩最后一人
while (count < n - 1) {
// 如果当前人还在队里
if (people[current] == 1) {
step++;
// 报数到m时，此人出队
if (step == m) {
people[current] = 0;
count++;
step = 0;
}
}
// 移动到下一个人，循环前进
current = (current + 1) % n;
}

// 找到最后剩下的人
for (int i = 0; i < n; ++i) {
if (people[i] == 1) {
cout << i << endl;
break;
}
}

return 0;
}
发表于 2026-02-06 20:05:25 回复(0)
提交观点

问题信息

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

热门推荐

相关试题

约瑟夫环

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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