LeedCode|约瑟夫环——递推公式详解（leetcode 1823. 找出游戏的获胜者) leetcode|递归算法|C++

约瑟夫环——递推公式详解（leetcode 1823. 找出游戏的获胜者) 约瑟夫环问题约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从第一个人开始报数，数到 k 的那个人出圈；他的下一个人又从 1 开始报数，数到 k 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。
题目:1823. 找出游戏的获胜者
详解解法有两种，模拟和递推；模拟往往是人们最容易想到的，可用多种数据结构来解决，代码放在了文末，本文着重讲解递推解法。
问题
举个例子：n=10，k=3; 总人数10人，数到3的人淘汰；
【LeedCode|约瑟夫环——递推公式详解（leetcode 1823. 找出游戏的获胜者)】把这些人简单用编号表示 0 1 2…
表解

文章图片

看表，第一行是报数次序，最多报到3，所以3的那一列的编号都是报到3的，这些编号都会被淘汰。
第二行，重新编号，意思是淘汰某人后，以此人的下一个人为起始，重新从0开始编号，这样做的原因后续来说。
接下来的n-1行分别是，淘汰某人后的实际编号顺序。
现在来重新理解第二行，以淘汰第4人举例，淘汰后的实际人员编号为3 4 6 7 9 0，他们重新编号后的新编号分别对应 0 1 2 3 4。
可以发现，每淘汰一个人后，相当于所有人向前移动k个单位
重新编号的意义：
0 1 2 3 4 5 6 7 8 9 淘汰一个后
0 1 ? 3 4 5 6 7 8 9 可见，若仍按这些编号组成一个环，之后就总需要考虑2号的空位问题，如何才能避免已经产生的空位对报数所造成的影响呢？答案：将这些号码重新编号，同时可以建立一种有确定规则的映射，
原始 0 1 2 3 4 5 6 7 8 9
旧环 0 1 ? 3 4 5 6 7 8 9
新环 7 8 ? 0 1 2 3 4 5 6
新编的环有这么一个优势: 相比于旧环中2与4之间在数学运算上的不连续性，新环8和0之间在对9取余的运算中是连续的，也就是说根本不需要单独费心设计用以记录并避开已产生的空位（如编号2）的机制，新环的运算不受之前遗留结果的掣肘。同时只要能将新环与旧环的映射关系逆推出来，就能利用在新环中的编号对应的旧环中的编号。
- 映射关系
新环编号=（旧环编号-k)%旧总人数得到的，所以旧环编号可以通过逆推得到：旧环编号=（新环编号+k)%旧总人数；
还记得前面说的，每淘汰一个人后，相当于所有人向前移动k个单位吗，与这里的公式相呼应，（旧环编号-k）就是向前移动k个单位，那么（新环编号+k)不就是新环向后移动k个单位吗，不就正好还原回了旧环吗。如：
原始 0 1 2 3 4 5 6 7 8 9
旧环 0 1 ? 3 4 5 6 7 8 9
新环 7 8 ? 0 1 2 3 4 5 6
- 递推公式
  f ( n , k ) = ( f ( n ? 1 , k ) + k ) ? m o dn f(n,k)=(f(n-1,k)+k)\,mod\ n f(n,k)=(f(n?1,k)+k)mod n
f(n,k)表示，n个人，每报到k时淘汰此人，最终剩下的那个人的编号
终于，通过这个公式我们现在用递归来进行解题,递归的出口是n=1，只剩下一个人，通过此人，可以通过递归的返回值，一层一层进行回代找到此人的实际编号。
特别注意：为什么图解中的编号要从0开始呢？其实也与我们的递推关系有关，假设我们从1开始编号，k为奇数，那么当递归走到出口回代时，根据旧环编号=（新环编号+k)%旧总人数，知此时留下的最后一个人的上一次编号是（1+k)%2=0,即出现了0编号，出现了我们意想不到的编号，无法解答问题。所以根据取余的特性,编号要从0开始; 如果非要从1开始也不是不可以,但代码实现就会有所不同。

递归解法

//编号从0开始 int f(int n, int k) {if (n == 1) return 0; return (f(n - 1, k) + k) % n; //或 //return n==1? 0:(f(n - 1, k) + k) % n; } int findTheWinner(int n, int k) {return f(n, k) + 1; //这里需要注意：若题目给的编号是从1开始，最后的返回结果就需要+1，若从0开始就不用+1 } //编号从1开始 int f(int n, int k) {if (n == 1) return 1; return ((f(n - 1, k) + k-1) % n)+1; //相比上面的就会繁琐一些 } int findTheWinner(int n, int k) {return f(n, k); //这里需要注意：若题目给的编号是从1开始，最后的返回结果就需要+1，若从0开始就不用+1 }

迭代解法

int findTheWinner(int n, int k) { //迭代其实就是从后往前推 int value = https://www.it610.com/article/0; for (int i = 2; i <= n; i++) //这里为什么要从2开始，还是要看递归，因为在递归回代的第一层n就是2 value = (value + k) % i; return value + 1; }

模拟解法
此篇博文是在代码完成之后所写，而代码又是使用Cpp来写，所以我也就直接粘了过来，C用户及其他语言用户也可以理解自行编写相应代码。见谅！

//法一：利用list来进行快速的删除，当遍历到尾是要注意重新更改迭代器的指向，避免迭代器失效，整体类似一循环链表。 class Solution {public: int findTheWinner(int n, int k) {list li; //O(N) for (int i = 1; i <= n; i++) {li.push_back(i); } int cur = 1; auto it = li.begin(); for (int i = 0; i < n - 1; i++) {cur = (k - 1)%li.size(); //对于k>>n的优化 while (cur--) {if (it == li.end()) it = li.begin(); it++; } if (it == li.end()) it = li.begin(); auto tmp = ++it; li.erase(--it); it = tmp; }return li.front(); }}; //法二：利用双端队列,先全部入队、然后不断出队，对于没有报到k的再入队 class Solution {public: int findTheWinner(int n, int k) {deque de; for (int i = 1; i <= n; i++) {de.push_back(i); } int cur = 1; while (de.size() != 1) {cur = (k - 1) % de.size(); while (cur--) {de.push_back(de.front()); de.pop_front(); } de.pop_front(); }return de.front(); } }; //法三：vector数组 class Solution {public: int findTheWinner(int n, int k) {vector v(n); for (int i = 0; i < n; i++) {v[i] = i + 1; }int d = k - 1; int index = 0; while (v.size()>1) {int pos = (index + d) % v.size(); v.erase(v.begin() + pos); index = pos; } return v[0]; } }; 以上三种都是模拟，只是各自使用了不用的数据结构