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循環，實際上不止兩次，這段代碼還可以再進行優化。