试题 算法提高 奥运会开幕式

Lan
Lan
2020-04-01 / 0 评论 / 695 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2020年04月01日,已超过1448天没有更新,若内容或图片失效,请留言反馈。
资源限制
时间限制:1.0s   内存限制:256.0MB
问题描述
  学校给高一(三)班分配了一个名额,去参加奥运会的开幕式。每个人都争着要去,可是名额只有一个,怎么办?班长想出了一个办法,让班上的所有同学(共有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

评论 (0)

取消