算法的学习笔记— 圆圈中最后剩下的数(牛客JZ62)
🏠个人主页：尘觉主页
62. 圆圈中最后剩下的数
题目链接
题目描述
让小朋友们围成一个大圈。然后，随机指定一个数 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取余，将计算实现通过循环碳成了选中。
😄总结
该问题提供了一种关于约瑟夫问题的优雅解法，通过返正方式，在数量不无限加长的情况下，仍能最终解出最后剩下的小朋友编号，并且突显了数学法则和循环计算的精妙。
😁热门专栏推荐
想学习vue的可以看看这个
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞
原文地址：https://blog.csdn.net/apple_67445472/article/details/144718492
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！