试题 历届真题 约瑟夫环【第九届】【决赛】【A组】

资源限制

时间限制:1.0s 内存限制:256.0MB

  n 个人的编号是 1~n,如果他们依编号按顺时针排成一个圆圈,从编号是1的人开始顺时针报         数。
  (报数是从1报起)当报到 k 的时候,这个人就退出游戏圈。下一个人重新从1开始报数。
  求最后剩下的人的编号。这就是著名的约瑟夫环问题。

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

  题目的输入是一行,2个空格分开的整数n, k
  要求输出一个整数,表示最后剩下的人的编号。

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

  例如输入:
  10 3

  程序应该输出:
  4

题目分析:

由于输入的数字数据太大,达到百万,正常的链表计算约瑟夫圆环肯定超时,那么我们可以用递推的方式进行求解。

递推公式

                            试题 历届真题 约瑟夫环【第九届】【决赛】【A组】

f(N,M)表示,N个人报数,每报到M时杀掉那个人,最终胜利者的编号。
f(N−1,M)表示,N-1个人报数,每报到M时杀掉那个人,最终胜利者的编号。

下面我们不用字母表示每一个人,而用数字。
                        1、2、3、4、5、6、7、8、9、10、11

表示10个人。他们先排成一排,设定报数3的人出局。

刚开始的时候,从编号1开始报数,第一轮出局的是是编号3。

第一轮过后,编号为4的人报1,第二轮出局的是编号6。

第二轮过后,编号为7的人报1,第三轮出局的是编号9。

第三轮过后,由于总共是11人,编号10报数1,编号11报数2,编号1报数3,编号1出局。

依次类推,游戏胜出者就是编号7。

下图表示这一过程(先忽视绿色的一行)

试题 历届真题 约瑟夫环【第九届】【决赛】【A组】

 现在我们来推导一下这个递推公式

将上面表格的每一行看成数组,这个公式描述的是:游戏胜出者在这一轮的数组下标位置

f(1,3)=0:只有一个人,这个人就是游戏胜出者,此时他的下标位置是0

f(2,3)=(f(1,3)+3)%2=3%2=1:在有2个人的时候,胜出者的下标位置是1

f(3,3)=(f(2,3)+3)%3=4%3=1:在有3个人的时候,胜出者的下标位置为1

f(4,3)=(f(3,3)+3)%4=4%4=0:在有4个人的时候,胜利者的下标位置为0

·······

最后 f(11,3)=6 (注意此时得到的是数组下标位置,最后应该+1才是编号) 

下面将讲解怎么推导这个公式。

1、假设我们知道了11人的时候,胜出者的下标位置是6,那么经过第一轮游戏之后,剩下10个人,应该是3,是向前移动了3位,为什么呢,因为前一轮已经走过了三个人,在走过了上一轮之后,原本报4的人,反而成了报1的人,所以得到胜出位置的这个3就是之前的6往前移动了3位。(此时也需要考虑数组越界问题,由于我们是用递推公式,在下一个假设中利用公式的取模即可)

2、同理倒着思考,假设知道了10个人的时候,胜出者的下标位置是3,有11个人的时候,同理推出他的下标位置应该向后移动3位,也就是加上3。但是因为数字的长度有限制,肯定不能让数组越界,所以要取模,得到数组位置,所以是f(11,3)=(f(10,3)+3)%11。

3.根据上面两点,此时整体看这个公式,此时有N个人,报数为M的出局,那么此时的数组应该是怎么移动的呢?

开局时,胜出者的位置是:f(N,M)=(f(N-1,M)+M)%N

当出局一人的时候,他的下一个人成为头部,报数1,此时相当于原数组向前移动了M个位置,此时有N-1个人,此时胜出者的位置是f(N-1,M)=(f(N-2,M)+M)%(N-1),依次类推,因为f(1,M)=1是一定的,这是递推的初始条件,那么我们就可以根据公式得出最后胜出者的位置。

理解这个递推式的核心在于关注胜出者的下标位置是怎么变的。每出局一个人,其实就是把这个数组向前移动了M位。然后逆过来,就可以得到这个递推式。

因为求出的结果是数组中的下标,最终的编号还要加1


import java.util.*;
public class Main {
	public static void cir(int n,int m) {
		int p=0;
   //当n=1的时候 p还是0 不进入循环 直接输出即可
		for(int i=2;i<=n;i++) {
    //为何从2开始呢,因为开始只有1个人的时候不用计算,返回的位置肯定是0
    //所以循环要从2开始
			p=(p+m)%i;
		
		}
		System.out.println(p+1);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner reader =new Scanner(System.in);
		int n=reader.nextInt();
		int m=reader.nextInt();
		cir(n,m);
	}

}

上一篇:【故障处理】队列等待之enq: US - contention案例


下一篇:11.盛最多水的容器--力扣题解