欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

C语言实现约瑟夫环代码

时间:2023-04-28

题意:对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;}


运行结果:

 

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。