首页 > 试题广场 >

约瑟夫环

[编程题]约瑟夫环

热度指数：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$ ，请输出最后剩下的"大王"编号。

输入描述:

在一行中输入三个整数 ，用空格隔开。

输出描述:

输出一个整数，表示最后剩下的"大王"编号。

示例1

输入

5 1 2

输出

说明

初始队列编号为 ，从编号  开始报数：

 出队，剩余 ；

 出队，剩余 ；

 出队，剩余 ；

 出队，剩余 ，输出 。

算法知识视频讲解

C++

XG3X

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号

#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

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)

牛客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)

在刷题的老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)

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)

小蔡驾到

#include <stdio.h>

int main() {

int n,k,m;

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

int arr[n];

for(int i=0;i<n;i++){

arr[i]=i;

}

int len=n;//当前剩余人数

int pos=k;//记录当前起始位置

while(len>1){

pos=(pos+m-1)%len;

for(int j=pos;j<len-1;j++){

arr[j]=arr[j+1];

}

len--;

}

printf("%d\n",arr[0]);

return 0;

}

发表于 2026-02-05 22:25:30 回复(0)

牛客160169021号

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k, m;
    cin >> n >> k >> m;
    
    vector<int> circle(n, 0);  // 0表示还在队列中
    int count = n;             // 剩余人数
    int current = k;           // 当前报数位置
    
    while (count > 1) {
        // 报数m次
        int step = 0;
        while (step < m) {
            // 如果当前人还在队列中，算一次报数
            if (circle[current] == 0) {
                step++;
                if (step == m) break;  // 报到m了
            }
            current = (current + 1) % n;  // 移动到下一个人（循环）
        }
        
        // 当前人出队
        circle[current] = 1;
        count--;
        
        // 找到下一个开始报数的人（下一个还在队列中的人）
        while (circle[current] == 1) {
            current = (current + 1) % n;
        }
    }
    
    // 找到最后剩下的人
    for (int i = 0; i < n; i++) {
        if (circle[i] == 0) {
            cout << i << endl;
            break;
        }
    }
    
    return 0;
}

发表于 2026-02-03 19:10:05 回复(1)

C++

Alkaid27

用数组解决

#include<bits/stdc++.h>
using namespace std;
int main() {
    // 定义核心变量：n=总人数，k=报数初始起点，m=报数淘汰数
    int n, k, m;
    cin >> n >> k >> m;
    int a[105] = {0};    // 淘汰状态数组：0=未淘汰，1=已淘汰
    int cnt = 0;         // 淘汰人数计数器
    int i = k;
    int t = 0;           // 报数模拟,在i处报出的数字
    while (cnt != n - 1) {
        if (i > n - 1) {
            i = 0;
        }

        if (a[i] == 0) {
            t++;
            if (t == m) {
                a[i] = 1;
                cnt++;
                t = 0;
            }
        }
        i++;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            cout << i;
        }
    }
    return 0;
}

发表于 2026-01-31 09:38:58 回复(0)

Java

爱敲代码的小豪

import java.util.*;
public class Main{
    public static void main(String[] args){
        int n,k,m;
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        k = in.nextInt();
        m = in.nextInt();
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++)list.add(i);
        while(true){
            if(list.size()==1)break;
            if(k+m-1>list.size()-1){
                int len = list.size();
                list.remove((k+m-1)%list.size());
                k = (k+m-1)%len;
            }else{
                list.remove(k+m-1);
                k = k+m-1;
            }
        }
        System.out.println(list.get(0));
    }
}

发表于 2026-01-27 15:19:47 回复(0)

gotoreturn

最笨的方法

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cout.tie(nullptr) ;
    int n , k , m ;
    cin >> n >> k >> m ;
    bool* jsf = new bool[n]() ;
    int kill = 0 , cnt = 0 ;
    for (int i = k ; kill < n-1 ; i = (i+1)%n) {
        if (!jsf[i]) {
            cnt++ ;
        }
        if (cnt==m) {
            jsf[i] = true ;
            cnt = 0 ;
            kill++;
        }
    } 
    for (int i = 0 ; i<n ; ++i) {
        if (!jsf[i]) {cout << i ;break ;}
    }

    delete [] jsf ;
    return 0 ;
}

发表于 2026-01-27 10:34:53 回复(0)

C++

喜欢后撤步的小太阳等一个offer

序列太好用了

#include <bits/stdc++.h>

using namespace std;

int main() {

vector <int> a;

int n,k,m,i;

cin>>n>>k>>m;

for(i=0;i<n;i++){

a.push_back(i);

}

int pos=(k+m-1)%a.size();

a.erase(a.begin()+pos);

while(a.size()!=1){

pos=(pos+m-1)%a.size();

a.erase(a.begin()+pos);

}

cout<<a[0];

}

发表于 2026-01-25 17:44:43 回复(0)

C++

Ashain

1.#include<iostream>

#include<queue>

using namespace std;

const int N=110;

int main()

{

int n,k,m;

cin>>n>>k>>m;

queue<int> q;

for(int i=0;i<n;i++)

{

q.push(i);

}

for(int i=1;i<=k;i++)

{

auto t=q.front();

q.pop();

q.push(t);

}

while(q.size()>1)

{

for(int i=1;i<m;i++)

{

auto t=q.front();

q.pop();

q.push(t);

}

q.pop();

}

cout<<q.front()<<endl;

return 0;

}

2.#include<iostream>

using namespace std;

const int N=110;

int a[N];

int main()

{

int n,k,m;

cin>>n>>k>>m;

for(int i=0;i<n;i++)

{

a[i]=i;

}

int num=k,count=n,cnt=0;//num:表示现在报数的人的编号,count:表示游戏剩余人数,

//cnt:表示当前的报的数字编号是多少

while(count>=1)

{

if(a[num]!=-1)

{

cnt++;

if(cnt==m)

{

a[num]=-1;

count--;

cnt=0;

}

if(num==n-1)num=0;

else num++;

}

cout<<num-1<<endl;

return 0;

}

发表于 2026-01-21 18:48:54 回复(0)

C++

牛客269180073号

#include <iostream>

using namespace std;

int main() {

int n,k,m;

cin>>n>>k>>m;

int a[100];

for(int i=0;i<n;i++){

a[i]=i;

}

int cnt=0,count=n;

while(count>=1){

if(a[k]!=-1){

cnt++;

if(cnt==m){

count--;

a[k]=-1;

cnt=0;

}

if(k==n-1) k=0;

else k++;

}

cout<<k-1;

}

发表于 2026-01-16 19:12:18 回复(0)

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)

L1LL

#include <stdio.h>

int main() {
	int n, k, m;
	if (scanf("%d %d %d", &n, &k, &m) != 3 || n < 2 || n > 100 || k < 0 || k >= n || m < 1 || m > 100) {
		return 1;
	}
	int N[n], t = m - 1;
	for (int i = 0; i < n; i += 1) {
		N[i] = i;
	}
	while (n > 1) {
		k = (k + t) % n;
		n -= 1;
		for (int i = k; i < n; i += 1) {
			N[i] = N[i + 1];
		}
	}
	printf("%d", *N);
	return 0;
}

发表于 2026-01-08 18:37:19 回复(1)

提交观点

问题信息

语言题过关题目

上传者：牛客301599号

难度：

46条回答 577收藏 1961浏览

约瑟夫环

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题