约瑟夫环问题（报数题解）

题型描述

n 个人围成一圈，从第一个人开始报数，报到 m 的人出圈，下一个人重新开始报数，最后只剩下一个人。
该问题需要模拟整个过程或者直接得到最后一个人的编号。

解题思路

1.数组模拟
将 n 个人的编号存入数组，从第一个人开始报数，输出报数 m 的人的编号，并将该编号清零（表示出圈）。在之后的每次报数之前要判断是否在圈内，重复这样的操作直至出圈的人数等于 n 。

2.链表模拟

3.数学推导公式（直接得到最后一个人的编号）->待学习

实例题解

报数

题目描述
输入两个正整数 n 和 m（ (1<m<n<=50)），有 n 个人围成一圈，按顺序从 1 到 n 编号。从第一个人开始报数，报数 m 的人退出圈子，下一个人从 1 开始重新报数，报数 m 的人退出圈子。如此循环，直到留下最后一个人。
请按退出顺序输出退出圈子的人的编号，以及最后一个人的编号。

输入示例
5
3

输出示例
No1: 3
No2: 1
No3: 5
No4: 2
Last No is: 4

完整代码

#include<stdio.h>

int main()
{
    int n, m, i, count = 0, num = 0;
    int a[100];
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) {
        a[i] = i;
    }/*存入编号*/

    for (i = 1; ; i++) {
        if (a[i] != 0) {
            num++; /* num 表示计数器*/
            if (num == m) {
                count++;
                if (count == n) {
                    break;
                }
                printf("No%d: %dn", count, a[i]);
                a[i] = 0;
                num = 0;
            }/* 报数为 m 出圈：
             出圈人数加一，输出编号，编号清零，计数器清零*/
        }
        if (i == n) {
            i = 0;
        }
    }
    printf("Last No is: %d", a[i]);
    return 0;
}

参考资料：用一行代码解决约瑟夫环问题

• 还没有人评论，欢迎说说您的想法！

相关课程

JS中Prompt提示框的使用

4255 1元

CSS3样式设计

4793 0元 限免

C语言提高深入浅出

5373 9.8元