题意:对n个人员进行1 2 3 1 2 3...的编号,报数3的人退出,将退出的人设为-1。问最后剩余一个人的编号是什么?
题意解析:假设n=10,每次都是123编号
人: 1 2 3 4 5 6 7 8 9 10
编号:1 2 3 1 2 3 1 2 3 1
1 2 -1 1 2 -1 1 2 -1 1 //报数3的人设为-1
2 -1 -1 1 2 -1 -1 1 -1 2 //这块儿最后一个直接接到第一个前面跟着编号
-1 -1 -1 1 2 -1 -1 -1 -1 1
-1 -1 -1 2 -1 -1 -1 -1 -1 1
-1 -1 -1 2 -1 -1 -1 -1 -1 -1
不是-1的结果就是最后一个剩余的人->4
代码解析:
(1)对n个人员进行1 2 3 1 2 3...的编号:
这个并不需要真正的对每个人去赋值编号,而且编号是动态变化的,也无法做到赋值,因此可以引入一个变量count在循环内循环编号123,只需要将编号不为-1的值位置count++,当count=3时重新置为1。
(2)报数3的人退出,将退出的人设为-1:
用count来寻找报数为3的人,并将其赋值为-1
(3)需要将最后一个人与第一个人连接到一起排序,形成一个环:
如果用i来控制循环,数组长度为len1,则: i = i % len;
(4)如何判断还剩一个人:
定义变量left,初始化为人数量,每赋值一个-1,left--;当left=1极为最后一人。
完整代码:
int YSFH(int* arr,int len,int n){assert(arr != NULL&&n>0);int count = 0;int left = len;int i = 0;while (left > 1)//for (int i = 0; i < len;)//函数循环{if (arr[i] != -1) {count++;}if (count == n) {arr[i] = -1;//count=-1left--;count = 0;//从头开始编号}i++;//不能将i++写在i = i % len;后面!!i = i % len;//函数终止条件 剩余人数为1}for (int i = 0; i < len; i++){if (arr[i] != -1){return arr[i];}}}int main(){int len=10;//人数//scanf("%d", &len);int* arr = (int*)malloc(sizeof(int) * len);for (int i = 0; i < len; i++)*(arr + i) = i + 1;assert(arr != NULL);if (arr == NULL)printf("内存申请失败");printf("%d",YSFH(arr,len,3)) ;free(arr);arr = NULL; //将arr置空能避免对内存的重复freereturn 0;}
运行结果: