约瑟夫环数组模拟循环列表实现"/>
约瑟夫环数组模拟循环列表实现
halo各位看客老爷们大家好,今天我们要介绍的主题是约瑟夫环,那么什么是约瑟夫环呢?
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后结果+1即为原问题的解。
最近在做vj上题的时候发现了这个很有趣的问题,初次接触觉得与海豚算法也就是时间复杂度为O(n)的算法很像,实际上还是有很大的不一样,这次我们先上原题和代码,再来分析:
原题地址:/
#include<stdio.h>
#include<string.h>int main () {int n,p,m;while(scanf("%d %d %d",&n,&p,&m)) {if(n == 0 && m == 0 && p == 0) {break;}int arr[1000] = {0};int print[1000] = {0};int step = 1;int count = 0;int temp = p-1;while(count < n) {//printf("1");if(step == m) {print[count] = temp + 1;count++;step = 0;arr[temp] = 1;}temp = (++temp)%n;if(arr[temp] == 0) {step++;}//printf("%d",step);}for(int i = 0;i < count-1;i++) {printf("%d,",print[i]);}printf("%d\n",print[count-1]);}
}
首先我们要对基本操作进行分析,假设我们有n个人,从第p位开始,每次隔m位出队一个,问题本质也就是一个循环,循环次数是n,因为要出队n人,但实际上每次出队完一次以后都会使总人数减少一位,所以没有一个固定的公式能让我们快速的知道结果。因此,我们利用一个标记数组arr来标记该人是否已经出队,出队记为1,没出队记为0,此外我们还需要一个临时变量temp来表示位置,以及step来表示已走的步数,需要注意的是,step在每次出队以后需要重置(提问!为什么第一次step的值为1,而不是每次重置后的0!)
经过这些变量初始化后,我们的问题实际上就很明了了,在出队人数没有到达n之前,我们不断的重复右移的操作,如果temp位置上的人没有出队,我们令step++,表示走了一步,如果temp位置上的人已经出队,我们令temp++,step不变表示跳过,输出结果只需要一个记录数组来记录,最后输出即可。还有一个注意的点是temp =(++temp)%n这里,temp不能一直累加,当temp超过总数n时,我们可以对temp进行取余,来达到循环的目的。
最后是我们的测试结果:
是不是很简单呢!
更多推荐
约瑟夫环数组模拟循环列表实现
发布评论