1047: [编程入门]报数问题

解题思路:

本题并不算在经典算法的范围内，只是比之前的题目多了一点逻辑上的难度。

我的思路是建一个大小为n的数组，数组里面的值是1到n，代表n个人的编号。每有一人报数计数器就+1，报数到3（即count == 3）时的人出局，即将此人在数组里对应位置的值改成0，然后计数器归零，剩余人数-1，同时在数组中遍历时，如果当前位置值为0，就右移一位，保证每次循环都能定位到非0数（未出局的人）。这样当剩余人数为1时，刚好定位到剩下的那个人的位置，于是返回那个值，就得到了幸存者的编号。

注意事项:

感觉我的注释已经够清楚了。个人觉得不足之处是代码应该可以写的更简洁（虽然写完已经简化不少了）。

参考代码:

#include <iostream>

using namespace std;

int numberOff(int n); // 报数，报到3者出局，返回最后生还者
int main() {
	int n = 0; // 人数
	cin >> n; // 读输入
	cout << numberOff(n) << endl;
	return 0;
}
int numberOff(int n) {
	int arr[n] = { 0 }; // n个人
	for(int i = 0; i < n; i++) {
		arr[i] = i + 1; // n个人编号为1~n
	}
	int left = n; // 剩余人数，为1时结束循环
	int count = 0; // 计数器，到3归零
	int i = 0; // 定位
	while(left != 1) {
		count++; // 计数器+1
		if(count == 3) {
			arr[i] = 0; // 把出局的人改成0
			left--; // 剩余人数-1
			count = 0; // 计数器归零
		}
		i = (i + 1) % n; // 碰到0就后移，到数组尾部就回到头部
		while(arr[i] == 0) {
			i = (i + 1) % n; // 保证每次都定位到未出局的人
		}
	}
	return arr[i]; // 返回幸存者的编号
}