0


约瑟夫环经典问题(c语言利用数组和指针解决)

问题描述

现在有m个人首尾相连围成一圈将他们一次编号为:1,2,3…n,然后从编号为1的人开始报数 1、2、3…n,报到n的这个人将离开队列,然后按照循环队列从下一个人从新按照以上规则报数。如此循环下去求最后获胜者的编号是多少?并讲每次出列的人的编号一次打印出来。

举一个简单的例子:现在有6个人围成一圈,依次编号为:1、2、3、4、5、6,按照1、2、3报数。
编号如图那么出队的顺序就是:3、6、4、2、5。最后留下的就是1号。

解题方法

c语言数组解决代码以及思想如下:

intmain(){int people[128]={0};//创建一个数组 初始化值都为0int m, remain, num_now =0, n;//m 总人数 // remain 剩余人数 // num_now 目前报的数字int* p = people;//p工作指针 初始指向第一个人printf("请输入总人数m和报数循环n;\n");scanf("%d%d",&m,&n);
        remain = m;for(int i =0; i < m; i++){//给n个人编号 1 2 3 4 ... m
            people[i]= i +1;//编号}while(remain >1){//只要剩下的人数大于1就仍然循环报数
            p = people;//每次循环完都从第一个人开始while(p !=&(people[m])){//p指针不指向最后一个人就沿着数组地址空间遍历if(*p ==0){//当前位置的人已经被逻辑删除
                    p++;//工作指针直接后移 不报数}else{//当前位置有人
                    num_now++;//报数if(num_now == n){//报数报到n
                        num_now =0;//报数置零,下一个重新从1报数printf("%d出列  ",*p);//打印出列人的序号*p =0;//当前位置的人作逻辑删除
                        remain--;//剩余人数-1}
                    p++;//工作指针后移}}}printf("  最后剩余的人的编号是:");for(int i =0; i < m; i++){//便利数组中没有被逻辑删除的人的序号并打印出来if(people[i]!=0){printf("%d", people[i]);break;}}return0;}

运行结果

在这里插入图片描述

总结

以上只是我用c语言数组以及指针的思想解决的步骤,希望能够在c语言学习中帮助到大家。当然学过数据结构的小伙伴还可以尝试用循环链表来解决,解题过程可能会更加直观。

标签: c语言

本文转载自: https://blog.csdn.net/qq_45875349/article/details/124019710
版权归原作者 努力的小关 所有, 如有侵权,请联系我们删除。

“约瑟夫环经典问题(c语言利用数组和指针解决)”的评论:

还没有评论