首页 > 试题广场 >

约瑟夫环

[编程题]约瑟夫环

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

输出

说明

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

 出队，剩余 ；

 出队，剩余 ；

 出队，剩余 ；

 出队，剩余 ，输出 。

算法知识视频讲解

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)

鲸鱼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)

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

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)

牛客915416951号

#include <stdio.h>

int main() {

int n, k, m, arr[100];

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

int l = n;

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

while (n > 1) {

int count = 0;

while (count < m) {

if (arr[k] == 1) {

count++;

if (count == m) {

arr[k] = 0;

n--;

}

k = (k + 1) % l;

}

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

if (arr[i] == 1) {

printf("%d", i);

break;

}

发表于 2025-11-14 22:03:10 回复(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)

提交观点

问题信息

语言题过关题目

上传者：牛客301599号

难度：

7条回答 523收藏 1839浏览

约瑟夫环

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题