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 d   n f(n,m)=(f(n-1,m)+m)\ mod\ n f(n,m)=(f(n1,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;
    }
};

你可能感兴趣的