约瑟夫算法

约瑟夫环问题是一个非常著名的趣题，即由n个人坐成一圈，按顺时针由1开始给他们编号。然后由第一个人开始报数，数到m的人出局。之后从下一个人开始继续报数，直到所有人都死亡为止。现在需要求的是最后一个出局的人的编号。

题目

给定两个int n和m，代表游戏的人数。请返回最后一个出局的人的编号。保证n和m小于等于1000。

测试样例：

输入：
5 3
返回：4

分析如下：

• 1、我们来分析一下n=4和k=2的情况：f(4,2) = ((( f(4–1), 2 ) + 2 -1 ) % 4) +1
• 2、我们要解决f(3,2)，我们要计算：f(3,2) = ((( f(3–1), 2 ) + 2 -1 ) % 3) +1
• 3、为了解决f(2,2)，我们要计算：f(2,2) = ((( f(2–1), 2 ) + 2 -1 ) % 2) +1
• 4、已知f(1,k)=1，然后f(1,2)=1，从而知道f(2,2) = 1，f(3,2) = 3 ，f(4,2) = 1

代码如下：

package com.mj.didiDemo.demo.ByteDance;

import java.util.Scanner;

/**
 * @author zhoujian123@hotmail.com 2018/9/12 10:39
 */
public class WS {

    static int josephus(int n, int k) {
        if (n == 1) {
            return 1;
        } else {
            /* The position returned by josephus(n - 1, k)
            is adjusted because the recursive call
            josephus(n - 1, k) considers the original
            position k%n + 1 as position 1 */
            return (josephus(n - 1, k) + k - 1) % n + 1;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        System.out.println(josephus(n, k));
    }
}

image.png