时间限制:1.0s 内存限制:256.0MB
北大附中书院有m个同学,他们每次都很民主地决策很多事情。按罗伯特议事规则,需要一个主持人。同学们民主意识强,积极性高,都想做主持人,当然主持人只有一人。为了选出主持人,他们想到了一个办法并认为很民主。方法是:
大家围成一圈,从1到m为每个同学编号。然后从1开始报数, 数到n的出局。剩下的同学从下位开始再从1开始报数。最后剩下来的就是主持人了。现在已经把同学从1到m编号,并约定报数为n的出局,请编程计算一下,哪个编号的同学将会成为主持人。
大家围成一圈,从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.0秒
我已知的两种解题方法:
1,循环
import java.util.Scanner; public class 书院主持人循环 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt()-1; boolean[] result = new boolean[n]; for (int i = 0; i < n; i++) { result[i] = true; } int count = n; int num =0; if (m==0) { System.out.println(n); }else { while(count!=1){ for (int i = 0; i < result.length; i++) { if (result[i]) { if (num==m) { result[i]=false; num=0; count--; }else { num++; } } } } for (int i = 0; i < result.length; i++) { if (result[i]) { System.out.println(i+1); } } } } }
2,递归(还不会)
import java.util.*; public class 书院主持人 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); System.out.println(zcr(m,n)); } public static int zcr(int n,int m){ if (m==1) { return m; } 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)模拟杀人过程,直到所有人都被杀死为止。
评论 (0)