首页 > 试题广场 >

约瑟夫环

[编程题]约瑟夫环
  • 热度指数：14135 时间限制：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
5umm1t头像 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)
C
牛客915416951号头像 牛客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)
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)
提交观点

问题信息

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

热门推荐

相关试题

约瑟夫环

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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