C++编程：小 due 和同学聚在一起玩游戏。n 个人围成一圈，给同学从 1 到 n 编号。游戏开始时从编号为 1 的同学开始报数，接着编号为 2 的同学报数，当报到第 m 个数，该同学就会出局。下一个同学接着从 1 开始报数，每次第 m 个同学都会出局。循环往复，直到剩余最后一个，为胜利者。谁会是最终的幸运鹅呢？ 输入格式 共一行两个数字 n 和 m，用空格隔开， 1 ≤ , ≤ 1 0 4 1≤n,m≤10 4 输出格式 最后胜利的同学的编号

以下是C++代码实现：

#include <iostream>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int res = 0;
    for (int i = 2; i <= n; i++) {
        res = (res + m) % i;
    }
    cout << res + 1 << endl;
    return 0;
}

思路解析：

根据题意可以得到，每次删除第m个数，因此在第一轮删除后，剩下的数的编号为m+1,m+2,...,n,1,2,...,m-2,m-1。这相当于把整个序列向前移动了m个位置，因此可以将当前编号为i的数的位置标记为(i+m)%n，其中n为当前剩余的数的个数。接下来重复这个过程，每次将序列向前移动m个位置，标记当前位置，直到只剩下一个数为止。

参考链接：AcWing 89. 圆圈中最后剩下的数

相关问题

C++经典题目：有n个人围成一圈，顺序排号，然后数数进行淘汰的解法和一些思考...

这道题目可以使用约瑟夫环的经典解法。具体思路如下：

1. 将n个人放入一个循环链表中，编号从1到n。
2. 从第一个人开始，数m个人，将第m个人删除。
3. 从删除的人的下一个人开始重新计数，再数m个人，继续删除。
4. 重复以上步骤，直到链表中只剩下一个人为止。

这个算法的时间复杂度为O(nm)，其中n为人数，m为要删除的人数。可以通过动态规划来优化时间复杂度，使其变为O(n)。

具体优化思路如下：

1. 设f(n)为n个人中最后剩下的人的编号。
2. 对于n个人，第一次删除的人的编号为(m-1)%n+1，设为k。
3. 删除k后，剩下的n-1个人中，编号为k+1, k+2, ..., n的人重新排列编号，变为1, 2, ..., n-k。
4. 由于删除了k，所以下一次要从编号为k+1的人开始计数，即从编号为1的人开始计数。所以，下一次删除的人的编号为(m-1)%(n-1)+1。
5. 由于重新编号后，问题转化为n-1个人的问题，所以f(n)=f(n-1)+(m-1)%(n-1)+1。

使用动态规划的思路，时间复杂度可以优化为O(n)。

c++n个人围圈，找3游戏

这个问题其实是著名的约瑟夫问题，可以用递归或数学公式来解决。

解法一：递归

首先，我们可以用递归的方式来解决这个问题。假设有 $n$ 个人，围成一圈，从第一个人开始报数，报到 $m$ 的人出圈，然后剩下的人继续从 1 开始报数，直到剩下最后一个人。假设最后留下的人编号为 $f(n,m)$，那么可以得到以下递归式：

$$
f(n,m) =
\begin{cases}
0, & n=1 \\
[f(n-1,m)+m]\bmod n, & n>1
\end{cases}
$$

其中，$[x]$ 表示对 $x$ 取整。这个式子的含义是，如果只有一个人，那么他就是最后留下的人，编号为 0；否则，剩下 $n-1$ 个人，先从第 $m$ 个人开始报数，然后把报数到 $m$ 的人从圈子中删除，留下 $n-1$ 个人继续玩游戏。由于删除了一个人，所以剩下的人的编号会重新从 0 开始，所以需要对 $f(n-1,m)+m$ 取模，得到新的编号。

最后得到的 $f(n,m)$ 就是最后留下的人的编号。

代码实现：

int josephus(int n, int m) {
    if (n == 1) return 0;
    return (josephus(n - 1, m) + m) % n;
}

解法二：数学公式

还可以使用数学公式来解决这个问题。假设有 $n$ 个人，从第一个人开始报数，报到 $m$ 的人出圈，然后剩下的人继续从 1 开始报数，直到剩下最后一个人。假设最后留下的人编号为 $f(n,m)$，那么可以得到以下公式：

$$
f(n,m) = \begin{cases}
0, & n=1 \\
[f(n-1,m)+m]\bmod n, & n>1
\end{cases}
$$

其中，$[x]$ 表示对 $x$ 取整。这个式子的含义是，如果只有一个人，那么他就是最后留下的人，编号为 0；否则，剩下 $n-1$ 个人，先从第 $m$ 个人开始报数，然后把报数到 $m$ 的人从圈子中删除，留下 $n-1$ 个人继续玩游戏。由于删除了一个人，所以剩下的人的编号会重新从 0 开始，所以需要对 $f(n-1,m)+m$ 取模，得到新的编号。

最后得到的 $f(n,m)$ 就是最后留下的人的编号。

代码实现：

int josephus(int n, int m) {
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        ans = (ans + m) % i;
    }
    return ans;
}