时间限制：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)