博客

n 个人的编号是 1~n，如果他们依编号按顺时针排成一个圆圈，从编号是1的人开始顺时针报数。

（报数是从1报起）当报到 k 的时候，这个人就退出游戏圈。下一个人重新从1开始报数。

求最后剩下的人的编号。这就是著名的约瑟夫环问题。

本题目就是已知 n，k 的情况下，求最后剩下的人的编号。

输入格式

题目的输入是一行，2个空格分开的整数n, k

约定：0 < n,k < 1百万

输出格式

要求输出一个整数，表示最后剩下的人的编号。

样例输入

10 3

样例输出

4

代码实现：

简单的模拟代码实现

package 蓝桥杯练习刷题;

import java.util.Scanner;

public class 约瑟夫环模拟 {
		public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int num=sc.nextInt();//输入总人数
		int k=sc.nextInt();//输入报到需要淘汰的数字
		int arr[]=new int[num];//使用数组进行模拟每个人，并初始化为0，若被淘汰则将数组中对应的数据转换为1即可
		int sum=num;//记录总人数
		int index = 0;//初始的下标
		int count=0;//计算次数
		while(sum>1) {
			if(arr[index]==0) {
				count++;//若当前未被淘汰，则将计数器加1
				if(count==k) {
					arr[index]=1;若此人报到需要淘汰的数字，将其标为1，意思是已淘汰
					count=0;将此人淘汰后，在从0开始计数淘汰
					sum--;//人员被淘汰，则将剩余人数减1
				}
			}
			
			index++;
			if(index==num) {//到达数组末尾则将索引指向数组头部
				index=0;
			}
		}
		for(int i=0;i<num;i++) {
			if(arr[i]==0) {
				System.out.println(i+1);
			}
		}
		}
}

使用逆推法实现

package 蓝桥杯练习刷题;
import java.util.Scanner;
public class 约瑟夫环 {
	public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int index=0;
        for(int i=2;i<=n;i++) {
        	index=(index+k)%i;
        	}
        System.out.print(index+1);
	}
}