首页
酷软
游戏
媒体
- 电影
- 剧集
- 动画
- 记录
- 综艺
- MV
- 有声世界
云资源
源码
更多
- 文库
- 系统
- web
- 站长帮
- 玩电脑
- 玩游戏
- 玩手机
- 涨姿势
- 玩软件
- 云图志
- 看漫画
- 微读书
- PS玩家
- 网文网语
- 硬件数码
- 编程开发
- 神秘之旅
- 福利线报
- 商业资源
- 网赚相关
- 健康加油站
赞助专区
云盘专区
资源阁
缘聚岛
BT种子库

[算法刷题] 试题算法提高书院主持人

作者：精品下载站日期：2020-03-29 00:00:00 浏览：68 分类：编程开发

资源限制时间限制：1.0s 内存限制：256.0MB问题描述　　北大附中书院有m个同学，他们每次都很民主地决策很多事情。按罗伯特议事规则，需要一个主持人。同学们民主意识强，积极性高，都想做主持人，当然主持人只有一人。为了选出主持人，他们想到了一个办法并认为很民主。方法是：
　　大家围成一圈，从1到m为每个同学编号。然后从1开始报数，数到n的出局。剩下的同学从下位开始再从1开始报数。最后剩下来的就是主持人了。现在已经把同学从1到m编号，并约定报数为n的出局，请编程计算一下，哪个编号的同学将会成为主持人。输入格式　　一行，由空格分开的两个整数m n。输出格式　　一个整数，表示主持人的编号样例输入15 3样例输出5样例输入200 55样例输出93数据规模和约定　　10000>m>0; 100>n>0;
　　时间限制1.0秒

我已知的两种解题方法：

1，循环

importjava.util.Scanner;

publicclass书院主持人循环{

	/**
	*@paramargs
	*/
	publicstaticvoidmain(String[]args){
		//TODOAuto-generatedmethodstub
		Scannersc=newScanner(System.in);
		intn=sc.nextInt();
		intm=sc.nextInt()-1;
		boolean[]result=newboolean[n];
		for(inti=0;i<n;i++){
			result[i]=true;
		}
		intcount=n;
		intnum=0;
		if(m==0){
			System.out.println(n);
		}else{
			while(count!=1){
				for(inti=0;i<result.length;i++){
					if(result[i]){
						if(num==m){
							result[i]=false;
							num=0;
							count--;
						}else{
							num++;
						}
					}
				}
			}
			for(inti=0;i<result.length;i++){
				if(result[i]){
					System.out.println(i+1);
				}
			}
		}
		
	}

}

2，递归（还不会）

importjava.util.*;
publicclass书院主持人{

	/**
	*@paramargs
	*/
	publicstaticvoidmain(String[]args){
		//TODOAuto-generatedmethodstub
		Scannersc=newScanner(System.in);
		intn=sc.nextInt();
		intm=sc.nextInt();
		System.out.println(zcr(m,n));

	}
	publicstaticintzcr(intn,intm){
		if(m==1){
			returnm;
		}
		return(zcr((m-1),n)+n-1)%m+1;
	}
}

这个题就是所谓的约瑟夫环，

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。分析：（1）由于对于每个人只有死和活两种状态，因此可以用布尔型数组标记每个人的状态，可用true表示死，false表示活。（2）开始时每个人都是活的，所以数组初值全部赋为false。（3）模拟杀人过程，直到所有人都被杀死为止。