-
问题描述
| 试题编号： | 201712-2 |
| 试题名称： | 游戏 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： | 问题描述 有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。 输入格式 输入一行，包括两个整数n和k，意义如题目所述。 输出格式 输出一行，包含一个整数，表示获胜的小朋友编号。 样例输入 5 2 样例输出 3 样例输入 7 3 样例输出 4 数据规模和约定 对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。 |
-
解题思路
#include<iostream>
using namespace std;
int main()
{int CallNum = 0;int n, k;cin>>n>>k;int Child[n];for(int i = 0; i < n; i++){//必须要先置0。Child[i] = 0;}int exit = n;int i = 0;while(exit != 1){for(i = 0; i < n; i++){if(exit == 1) break;if(Child[i] == -1) continue;//检查是否已被淘汰。//没有被淘汰：CallNum++;//printf("%d号小朋友报数：%d\n", i+1, CallNum);if(CallNum%k == 0||CallNum%10 == k){//符合淘汰条件Child[i] = -1;exit--;}}}//找到最后一个报数的小朋友。int j;for(j = 0; j < n; j++){if(Child[j] != -1) break;}cout<< j+1;
}
-
思路总结
这一题在考试时使用Java的List做出来了。本博客中使用的是C++语言。
在此题中使用数组模拟报数。设置了一个大变量CallNum=0，用来记录所报的数字。设置一个Child[n]数组，用来表示多个小孩的序列。
程序中，先判断是否仅剩一个人，使用exit标识，若仅剩一人，则退出循环。然后开始报数，使用Child[i]=-1表示第i号小孩被淘汰。如果小孩没有被淘汰，则进行报数CallNum++，并根据筛选条件【CallNum%k == 0||CallNum%10 == k】判断是否要将当前小孩淘汰。如果小孩被淘汰了，就不再让他/她报数。
最后需要查找一下最后一个报数的小孩编号。博主因为没有考虑到这一点，卡了一下。不过通过打印测试找到了问题所在。
做这种题需要较强的逻辑能力，如果逻辑能力一般，可以在本子上写一下思路，方便写程序。
