左神高级提升班2 约瑟夫环结构

【案例1】

【题目描述】

【输入描述：】

【输出描述：】

【输入】

【输出】

【思路解析】

【代码实现】

【案例1】

【题目描述】

某公司招聘，有n个人入围，HR在黑板上依次写下m个正整数A1、A2、……、Am，然后让这n个人围成一个圈，并按照顺时针顺序为他们编号0、1、2、……、n-1。录取规则是：
第一轮从0号的人开始，取用黑板上的第1个数字，也就是A1黑板上的数字按次序循环取用，即如果某轮用了第m个，则下一轮需要用第1个；如果某轮用到第k个，则下轮需要用第k+1个（k<m）
每一轮按照黑板上的次序取用到一个数字Ax，淘汰掉从当前轮到的人开始按照顺时针顺序数到的第Ax个人，下一轮开始时轮到的人即为被淘汰掉的人的顺时针顺序下一个人被淘汰的人直接回家，所以不会被后续轮次计数时数到经过n-1轮后，剩下的最后1人被录取所以最后被录取的人的编号与（n，m，A1，A2，……，Am）相关。

【输入描述：】

第一行是一个正整数N，表示有N组参数从第二行开始，每行有若干个正整数，依次存放n、m、A1、……、Am，一共有N行，也就是上面的N组参数。

【输出描述：】

输出有N行，每行对应相应的那组参数确定的录取之人的编号示例1:

【输入】

1
4 2 3 1

【输出】

【思路解析】

我们先认为就是每淘汰一个人就会重新排一次序，然后最后淘汰掉n-1个人后，只剩一个人排序为0。那么我们能不能通过他这次排序的编号，和上一轮淘汰掉Ax编号和上一轮一共有几个人这个信息来获得他上一轮的编号。如果能通过这样的信息来获得曾经的编号，那我们一直递归往上，直到获得他最初始的编号，然后返回这个编号。

0	1	2	3	4
2	3		0	1
	0		1	2
	0		1
			0

这个表格模拟了淘汰情况，（简单模拟每次都淘汰掉第三个人），通过每一次淘汰都画出新老编号的对应关系，看图知道大概是模一个东西的图像，然后总结表格和图像规律后可以得到函数为

F(x) = (x + m) % i；F(x) 为在第i轮的编号，x为在第i - 1轮的编号，m表示第i轮选择淘汰编号为多少的人。

又因为每轮次淘汰的m并不一样，但是他是循环使用的，在递归时一定要加入这个的变化。

【代码实现】

import java.util.Scanner;

/**
 * @ProjectName: study3
 * @FileName: Ex5
 * @author:HWJ
 * @Data: 2023/9/17 15:23
 */
public class Ex5 {
    static int[] arr;
    static int m;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        for (int i = 0; i < N; i++) {
            int n = input.nextInt();
            m = input.nextInt();
            arr = new int[m];
            for (int j = 0; j < m; j++) {
                arr[j] = input.nextInt();
            }
            System.out.println(getNum(n, 0));
        }

    }

    public static int getNum(int i, int ax) {
        if (i == 1) {
            return 0;
        }
        int x = (getNum(i - 1, ax == m - 1 ? 0 : ax + 1) + arr[ax]) % i;
        return x;

    }

}

文章来源地址https://uudwc.com/A/Ev33M