csp试题2：游戏

• • 题目
  • 分析
  • 代码
  • 总结

题目

      有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。

      游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。

      例如，当n=5, k=2时：

      1号小朋友报数1；

      2号小朋友报数2淘汰；

      3号小朋友报数3；

      4号小朋友报数4淘汰；

      5号小朋友报数5；

      1号小朋友报数6淘汰；

      3号小朋友报数7；

      5号小朋友报数8淘汰；

      3号小朋友获胜。

      给定n和k，请问最后获胜的小朋友编号为多少？

输入格式

      输入一行，包括两个整数n和k，意义如题目所述。

输出格式

      输出一行，包含一个整数，表示获胜的小朋友编号。

样例1

输入：

5 2
           

输出：

3
           

样例2

输入：

7 3
           

输出：

4
           

数据规模和约定

      对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。

分析

      模拟运行类的的题目。游戏的进行过程就是解题思路。具体过程已在代码中用注释给出。

代码

/*
20190922
csp试题2：游戏 
*/ 

#include <iostream>
using namespace std;

int main(){
	//接收数据
	int n, k;
	cin >>n >>k;
	
	//模拟运行
	//1.初始n个小朋友
	int stu[n];
	for(int i=0; i<n; i++){
		stu[i] = 0;
	}
	
	int number = 1;	//报的数字 
	int index = 0;	//用于选择该哪一个小朋友 
	int rest_num = n;	//剩下的人数 
	while(rest_num != 1){
		//2.如果没被淘汰
		if(stu[index] != -1){
			//报数 
			stu[index] = number;
			
			//判断此次报数是否会被淘汰
			if(stu[index]%k == 0 || stu[index]%10 == k){
				stu[index] = -1;	//被淘汰 
			} 
			
			//选择下一个小朋友
			index++;
			number++; 
		}
		else{	//如果被淘汰，则跳过此小朋友，让下一个下朋友报数 
			index++;
		}
		
		//3.当这一轮进行到最后一个小朋友时，从头开始 
		if(index == n){
			index = 0; 
		} 
		
		//4.判断是否只剩下一个小朋友
		rest_num = n; 
		for(int i=0; i<n; i++){
			if(stu[i] == -1){
				rest_num--;
			}
		} 
	} 
	
	//5.输出
	for(int i=0; i<n; i++){
		if(stu[i] != -1){
			cout <<i+1<<endl;
		}
	} 
	
	return 0;
} 
           

总结

      这类模拟运行类的题目还是相对较简单的。在最后对stu[ ]进行了两次循环遍历，当然有while循环，实际上不止两次，这段代码还可以再进行优化。