厦门35网站建设公司/百度推广关键词怎么设置好

一、需求

• 报数游戏是这样的：有n个人围成一圈，按顺序从1到n编好号。从第一个人开始报数，报到m（<n）的人退出圈子；下一个人从1开始报数，报到m的人退出圈子。如此下去，直到留下最后一个人。
• 本题要求编写函数，给出每个人的退出顺序编号。
• 函数接口定义如下

void CountOff( int n, int m, int out[] );

• 其中n是初始人数；m是游戏规定的退出位次（保证为小于n的正整数）。
• 函数CountOff将每个人的退出顺序编号存在数组out[]中。
• 因为C语言数组下标是从0开始的，所以第i个位置上的人是第out[i-1]个退出的。

二、裁判程序样例

#include <stdio.h>
#define MAXN 20void CountOff( int n, int m, int out[] );int main()
{int out[MAXN], n, m;int i;scanf("%d %d", &n, &m);CountOff( n, m, out );   for ( i = 0; i < n; i++ )printf("%d ", out[i]);printf("\n");return 0;
}/* 你的代码将被嵌在这里 */

三、测试样例

• 输入样例

11 3

• 输出样例

4 10 1 7 5 2 11 9 3 6 8 

四、思路分析

思路1 

1. 新建一个数组s，其大小与out相同，初始化值为1~n，这个数组的作用是记录1~n各个位置上人的状态，假设1号退出了，那么它的状态s[1] = 0；
2. 定义一个people_number表示圈里还剩的人数，初始化值为n，每次退出一个人，people_number--，直到people_number为0；
3. 每次循环都要对s数组进行遍历，判断当前的人是否退出了，如果没有退出，那就开始报数，定义count来累计报数，初始化为0；
4. 报了数之后接着判断是否与m相同，相同的话：
   假设当前位置为i，那么s[i] = 0表示当前位置的人退出了，out[i] = quit_order(quit_order从1开始，表示退出次序)，
   然后人数people_number要减1，count重新开始计数，退出的次序加1。

代码是这样的：

void CountOff( int n, int m, int out[] )
{int people_number = n;int i;int s[MAXN];int count = 0;int quit_order = 1;for(int i = 0; i < n; i++) {s[i] = i + 1;}while(people_number) {for(int i = 0; i < n; i++) {if(s[i] != 0) {count++;if(count == m) {s[i] = 0;people_number--;out[i] = quit_order;quit_order++;count = 0;}}}}
}

思路2(超时问题不懂)

1. 1.将out数组中的元素全部初始化为0，目的是为了记录当前位置的退出次序，假设第1个人的退出次序为5(第5个退出的)，那么out[0] = 5；
2. 使用循环，当圈里没有人时退出循环，若当前位置的人没有退出，那么就报数(定义count，初始化为0)count++；
3. 报完数后接着判断是否等于m，相同的话：
   假设当前位置的人为i，那么它就要退出，它的退出次序为quit_order(quit_order初始化为0)，即quit_order++，out[i-1] = quit_order(关于为什么是i-1，是因为第1个报数后，i就是1，如果他要退出，很明显是设置out[0])，然后count清零；
4. 实现当前位置的循环滚动，即i = i % n。

代码是这样的： 

void CountOff( int n, int m, int out[] )
{int i;int people_number = n;int count =0;int quit_order = 1;for(i = 0; i < n; i++) {out[i] = 0;}i = 0;while(people_number) {if(out[i++] == 0) {//i++;         //若写i++，就会超时，真的奇怪啊。count++;}if(count == m) {out[i - 1] = quit_order;quit_order++;people_number--;count = 0;}i = i % n;//每一次循环i都会增大，保证i<n}
}