链表|JZ46 孩子们的游戏(圆圈中最后剩下的数) 数据结构|算法|c++|递归法

JZ46 孩子们的游戏(圆圈中最后剩下的数

题目描述
思路分析
代码实现

题目描述点这里
思路分析 【链表|JZ46 孩子们的游戏(圆圈中最后剩下的数)】约瑟夫问题。
数组链表模拟/递推递归，都能做。
暴力模拟的方法就不讲了，当成链表节点就好。主要写下递归递推做法。递推/递归的关键是找到递推关系。
设 f ( n , m ) f(n,m) f(n,m)为问题规模为 n , m n,m n,m时问题的答案。
则画图重新标号+映射分析可得递推式 f ( n , m ) = ( f ( n ? 1 , m ) + m )m o dn f(n,m)=(f(n-1,m)+m)\ mod\ n f(n,m)=(f(n?1,m)+m) mod n
代码实现

class Solution {public: int LastRemaining_Solution(int n, int m) {if(!n) return -1; if(n==1) return 0; return (LastRemaining_Solution(n-1,m)+m)%n; } };