首页 > 试题广场 >

约瑟夫环

[编程题]约瑟夫环

热度指数：16156 时间限制：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)

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++

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

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

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

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)

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)

Java

牛客459616581号

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int k = sc.nextInt();

int m = sc.nextInt();

//存放布尔值表示该索引位置是否有人

boolean[] arr = new boolean[n];

for(int i = 0; i < arr.length; i++){

arr[i] = true;

}

//计数表示当前在圈内的人个数

int pnum = n;

//从索引为k的位置开始

int current = k;

//外循环结束条件圈内人数为1

while(pnum > 1){

//表示当前报数

int count = 0;

while(count < m){

//如果当前位置有人，则报数

if(arr[current]){

count++;

//报数等于要出队的数

if(count == m){

arr[current] = false;//出队状态标为false

pnum--; //圈内人减一

break;

}

//模的意义在于防止越界，实现环形访问

current = (current + 1)%n;

}

for(int i = 0;i < arr.length; i++){

if(arr[i]){

System.out.println(i);

}

发表于 2026-01-07 17:54:13 回复(0)

24届攒钱辞职的小牛马

#include <cassert>
#include <iostream>
#include <list>
#include <vector>

int method_1(int n, int k, int m) {
    std::vector<int> people;
    for (int i = 0; i < n; ++i) {
        people.push_back(i);
    }

    int cur_idx = k;
    while (people.size() > 1) {
        int elim_idx = (cur_idx + m - 1) % people.size();
        people.erase(people.begin() + elim_idx);
        cur_idx = elim_idx % people.size();
    }

    return people[0];
}

int method_2(int n, int k, int m) {
    std::list<int> people;
    for (int i = 0; i < n; ++i) {
        people.push_back(i);
    }
    auto it = people.begin();
    advance(it, k);

    while (people.size() > 1) {
        int steps = (m - 1) % people.size();

        while (steps--) {
            if (++it == people.end())
                it = people.begin();
        }
        it = people.erase(it);
        if (it == people.end())
            it = people.begin();
    }

    return people.front();
}

int main() {
    int n, k, m;
    std::cin >> n >> k >> m;
    assert(n >= 2 && n <= 100);
    assert(k >= 0 && k <= n - 1);
    assert(m >= 1 && m <= 100);

    // std::cout << method_1(n, k, m) << "\n";
    std::cout << method_2(n, k, m) << "\n";
    return 0;
}

发表于 2026-01-06 15:22:22 回复(0)

鲸鱼lord

#include <stdio.h>
#define MAX 105
int main() {
    int n=0,k=0,m=0;  
    int arr[MAX]={0};
    scanf("%d%d%d",&n,&k,&m);
    if(n>=2&&n<=100&&k>=0&&k<=n-1&&m>=1&&m<=100)
    {
        int count=n;//剩余人数
        int cur=k;
        for(int i=0;i<n;i++)
        {
            arr[i]=i;
        }

        while(count>1)
        {
            int step=0;//当前步数
            while(step<m)
            {
                if(arr[cur]!=-1)//出队的人的下标标为-1
                {
                    step++;
                }
                if(step<m)
                {
                    cur=(cur+1)%n;
                }
            }

            //报数到m了出队
            arr[cur]=-1;
            count--;

            while(arr[cur]==-1)
            {
                cur=(cur+1)%n;//重新报数位置
            }
        }

        for(int i=0;i<n;i++)
        {
            if(arr[i]!=-1)//最终数组里面只剩一个不为-1的元素就是大王了
            {
                printf("%d",arr[i]);
                break;
            }
        }
    }
    return 0;
}

发表于 2026-01-05 19:56:23 回复(0)

C++

神秘吐司

#include<bits/stdc++.h>
using namespace std;
int main() {
int n, k, m;
cin >> n >> k >> m;
vector<int> vec;
for (int i = 0; i < n; i++) {
vec.push_back(i);
}
int idx;
int next;

while (vec.size() != 1) {
idx = vec[(k + m - 1) % vec.size()];
next = vec[(k + m) % vec.size()];
auto it = find(vec.begin(), vec.end(), idx);
vec.erase(it);
auto iit = find(vec.begin(), vec.end(), next);
k = distance(vec.begin(), iit);

}
for (auto& ele : vec) {
cout << ele << " ";
}
cout << endl;
return 0;
}

发表于 2026-01-05 19:38:20 回复(0)

C++

某懿

#include <iostream>

using namespace std;

void del(int a[],int n,int t)

{

for(int i=t;i<n-1;i++)

a[i]=a[i+1];

}

int main(){

int n,k,m;

cin>>n>>k>>m;

int a[101];

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

int t=k;

while(n!=1)

{

t=(t+m-1)%n;//对于环的形成，要得到0-26，就要对27取余，要得到0——n-1，就要对n取余！！！

del(a,n,t);

n--;

}

cout<<a[0];

return 0;

}

发表于 2025-12-29 15:32:48 回复(1)

5umm1t

#include<stdio.h>

int main()

{

int n, k, m;

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

int a=n;

int count = 0;

int current = k-1;

int arr[100] = { 0 };

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

{

arr[i] = 1;

}

while (a > 1)

{

if (arr[current])

{

count++;

if (count == m)

{

arr[current] = 0;

count = 0;

a--;

}

current = (current + 1) % n;

}

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

{

if (arr[i])

{

printf("%d", i+1);

break;

}

return 0;

}

发表于 2025-12-07 14:12:10 回复(0)

牛客416124127号

#include <stdio.h>
int main() {
    int n = 0, k = 0, m = 0, count = 0, step = 0, current;
    int people[1000];
    //count是移除的人
    //step是报的数
    //current是现在的位置
    scanf("%d %d %d", &n, &k, &m);
    current = (k - 1 + n) % n;
    for (int i = 0; i < n; i++) {
        people[i] = 1;
    }//定义一个全是1的，个数为n的数组，1是还在队伍里面，0是已经出了队伍
    while (count < n -
            1) { //让移除的人还没到n的时候循环，一直持续到只有一个人在队伍里面
        //开始报数
        while (step < m) { //另起一个报数的计数器step
            if (people[current] == 1)
                step++;//如果这个人报数还没有到m，那么直接跳过他，报数计数器+1
            if (step < m)
                current = (current + 1) % n;
        }
        //一轮报数结束，开始换下一组
        //清除计数器，把移除的人标记成0
        step = 0;
        people[current] = 0;
        count++;
        //开始下一个

        while (people[current] == 0)
            current = (current + 1) %
                      n;//取模就相当于让最后一个直接跳到第一个，且不用担心溢出问题

    }
    for (int i = 0; i < n; i++) {
        if (people[i] == 1)
            printf("%d", i + 1);

    }

    return 0;
}

发表于 2025-12-01 22:27:09 回复(0)

C++

牛客843987641号

#include <iostream>

using namespace std;

int main() {

int a, b,c;

cin >>a >>b>>c;

int nowPoint =b;

int count=0;

int num =a;

int res[101]={0};

while(1){

if(res[nowPoint]==0){

//未排除

count++;

if(count%c==0){

if(num==1){

cout<<nowPoint;

break;

}

res[nowPoint]=1;

num--;

}

nowPoint++;

nowPoint%=a;

}

// 64 位输出请用 printf("%lld")

发表于 2025-11-16 23:20:35 回复(0)

提交观点

问题信息

语言题过关题目

上传者：牛客301599号

难度：

38条回答 515收藏 1820浏览

约瑟夫环

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题