当前位置：首页 > article >正文

算法的学习笔记— 圆圈中最后剩下的数(牛客JZ62)

article 2024/12/27 7:06:43

🏠个人主页：尘觉主页

文章目录

62. 圆圈中最后剩下的数
- 题目链接
- 题目描述
- 解题思路
- Java 实现
- 思考分析
- 😄总结

62. 圆圈中最后剩下的数

题目链接

NowCoder

题目描述

让小朋友们围成一个大圈。然后，随机指定一个数 m，让编号为 0的小朋友开始披数。每次喊到 m-1的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续 0...m-1披数。这样进行，直到剩下最后一个小朋友，该小朋友可以不用表演。

问题：最后剩下的这个小朋友编号是什么？
在这里插入图片描述

解题思路

该问题是关于约瑟夫环（Josephus Problem）的关键计算。在这种问题中，我们需要确定每次出列的人，直到剩下最后一个。

在数学解析中，圈长为 n时，该问题的解可以看作圈长为 n-1的解，然后加上披数的长度 m。因为轮廓是圆形，所以最后需要对 n 取余。

解析情况如下：

如果圈里只剩下 1 个小朋友，那么编号就是 0。
如果不止 1 个，则通过下列关系进行返正： f(n,m)=(f(n−1,m)+m)%nf(n, m) = (f(n-1, m) + m) % n

这里，在通过混迁进行返正时，最后将实现从最初大圈中剩下的最后一个小朋友的编号。

Java 实现

以下是该解法的 Java 实现：

public int LastRemaining_Solution(int n, int m) {
    if (n == 0)     // 特殊输入的处理
        return -1;
    if (n == 1)     // 通过返正返回条件
        return 0;
    return (LastRemaining_Solution(n - 1, m) + m) % n;
}

思考分析

上述代码通过循环完成解析：

边界情况处理：如果圈里没有小朋友（n=0），则返回 -1 表示无解。
选择的解应定义：如果剩下 1 个小朋友，直接返回 0 作为编号。
通过参数进行递归：则通过算法：上一次解法值（LastRemaining_Solution(n - 1, m)）加上 m 之后，对 n 取余，将计算实现通过循环碳成了选中。