时间限制：1.0s 内存限制：256.0MB
问题描述
学校给高一（三）班分配了一个名额，去参加奥运会的开幕式。每个人都争着要去，可是名额只有一个，怎么办？班长想出了一个办法，让班上的所有同学（共有n个同学）围成一圈，按照顺时针方向进行编号。然后随便选定一个数m，并且从1号同学开始按照顺时针方向依次报数，1, 2, …, m，凡报到m的同学，都要主动退出圈子。然后不停地按顺时针方向逐一让报出m者出圈，最后剩下的那个人就是去参加开幕式的人。
要求：用环形链表的方法来求解。所谓环形链表，即对于链表尾结点，其next指针又指向了链表的首结点。基本思路是先创建一个环形链表，模拟众同学围成一圈的情形。然后进入循环淘汰环节，模拟从1到m报数，每次让一位同学（结点）退出圈子。
输入格式：输入只有一行，包括两个整数n和m，其中n和 m的含义如上所述。
输出格式：输出只有一个整数，即参加开幕式的那个人的编号。
输入输出样例
学校给高一（三）班分配了一个名额，去参加奥运会的开幕式。每个人都争着要去，可是名额只有一个，怎么办？班长想出了一个办法，让班上的所有同学（共有n个同学）围成一圈，按照顺时针方向进行编号。然后随便选定一个数m，并且从1号同学开始按照顺时针方向依次报数，1, 2, …, m，凡报到m的同学，都要主动退出圈子。然后不停地按顺时针方向逐一让报出m者出圈，最后剩下的那个人就是去参加开幕式的人。
要求：用环形链表的方法来求解。所谓环形链表，即对于链表尾结点，其next指针又指向了链表的首结点。基本思路是先创建一个环形链表，模拟众同学围成一圈的情形。然后进入循环淘汰环节，模拟从1到m报数，每次让一位同学（结点）退出圈子。
输入格式：输入只有一行，包括两个整数n和m，其中n和 m的含义如上所述。
输出格式：输出只有一个整数，即参加开幕式的那个人的编号。
输入输出样例
8 3
7
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()-1;
boolean[] list = new boolean[n];
int count = n;
int gun = 0;
if (m==0) {
System.out.println(n);
}else {
while(count!=1){
for (int i = 0; i < list.length; i++) {
if (!list[i]) {
if (gun==m) {
list[i]=true;
gun =0;
count--;
}else {
gun++;
}
}
}
}
for (int i = 0; i < list.length; i++) {
if (!list[i]) {
System.out.println(i+1);
}
}
}
}
}
评论 (0)