admin管理员组

文章数量:1794759

【题目/训练】约瑟夫环的一系列方法

1、dfs递归写法：

我们有n个数，下标从0到n-1，然后从index=0开始数，每次数m个数，最后看能剩下谁。我们假设能剩下的数的下标为y，则我们把这件事表示为 f(n, m) = y; 这个y到底表示了啥呢？注意，y是下标，所以就意味着你从index=0开始数，数y+1个数，然后就停，停谁身上谁就是结果。 行了，我们假设f(n-1,m)=x，然后来找一找f(n,m)和f(n-1,m)到底啥关系。 f(n-1,m)=x意味着啥呢？意味着有n-1个数的时候从index=0开始数，数x+1个数你就找到这结果了。那我不从index=0开始数呢？比如我从index=i开始数？那很简单，你把上面的答案也往后挪i下，就得到答案了。当然了，你要是挪到末尾了你就取个余，从头接着挪。 于是我们来思考f(n,m)时考虑以下两件事：

  1. 有n个数的时候，要划掉一个数，然后就剩n-1个数了呗，那划掉的这个数，下标是多少？
  2. 划完了这个数，往后数，数x+1个数，停在谁身上谁就是我们的答案。当然了，数的过程中你得取余

问题一：有n个数的时候，划掉了谁？下标是多少？ 因为要从0数m个数，那最后肯定落到了下标为m-1的数身上了，但这个下标可能超过我们有的最大下标（n-1）了。所以攒满n个就归零接着数，逢n归零，所以要模n。 所以有n个数的时候，我们划掉了下标为(m-1)%n的数字。 问题二：我们划完了这个数，往后数x+1下，能落到谁身上呢，它的下标是几？ 你往后数x+1，它下标肯定变成了(m-1)%n +x+1，和第一步的想法一样，你肯定还是得取模，所以答案为[(m-1)%n+x+1]%n，则 f(n, m) = [(m - 1) % n + x + 1] % n 其中x=f(n-1,m) 我们化简它！ f(n,m)=[(m-1)%n+x+1]%n =[(m-1)%n%n+(x+1)%n]%n =[(m-1)%n+(x+1)%n]%n =(m-1+x+1)%n =(m+x)%n

化简版本（编号从0开始）
代码语言：javascript代码运行次数：0运行复制
int LastRemaining_Solution(int n, int m) {
     return n == 0 ? n : (LastRemaining_Solution(n - 1, m) + m ) % n;
}
编号从1开始：
代码语言：javascript代码运行次数：0运行复制
int f1(int n, int m) {
	return n == 1 ? n : (f1(n - 1, m) + m - 1) % n + 1;
}
编号从0开始，并且记

本文标签： 题目训练约瑟夫环的一系列方法

版权声明：本文标题：【题目训练】约瑟夫环的一系列方法 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754826243a1706956.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。