🏠个人主页：尘觉主页

62. 圆圈中最后剩下的数

题目链接

NowCoder

题目描述

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

问题：最后剩下的这个小朋友编号是什么？

解题思路

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

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

解析情况如下：

1. 如果圈里只剩下 1 个小朋友，那么编号就是 0。
2. 如果不止 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;
}

思考分析

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

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

😄总结

该问题提供了一种关于约瑟夫问题的优雅解法，通过返正方式，在数量不无限加长的情况下，仍能最终解出最后剩下的小朋友编号，并且突显了数学法则和循环计算的精妙。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞