约瑟夫环

复习一下关于约瑟夫环的实现原理:

如果用C来写的话,也会有许多的方法,比如1:采用链表(双向链表)2:递归3:队列(不断出队与入队) 4:非递归循环。

现在简单介绍一下非递归的约瑟夫算法。

首先,需要明白约瑟夫环的具体规则:个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。

假设从零开始报,报到m-1的人退出,那么应该报m的人开始报零,再报到m-1,该报m的人报零,以此类推,当所剩人数为二的时候,两个人依次从0报到m-1,剩下的一个人即是最后的幸存者。而在这两个人中:

假设m=4,绿色的代表剩存的人,那么在该轮报数中,其所报的数则为4%2=0;而假设m=5则有

5%2=1,在该轮中这位幸存者所报的最小数字为1。

之所以按照此方法进行探究的原因为如果n=2,即一共有两个人,以m报数,那么幸存者在游戏开始的编号为m%2。

依次类推,当n≠2,或者是n为更大的数时,这个幸存的人最开始的编号是多少m=5n=3继续作图

可知在共有三个人时最终幸存者的位置,本轮的开始到达结束共5人,结束后的第二个才是幸存者,故幸存者到达该轮的编号0间隔5+1个长度。(5+1)%3=0,可知在该轮(n=3)中,幸存者是编号0的数。

当n=2时,由于下一轮筛选只有一个数编号零,所以可以视为0,故(4+0)%2=0,(5+0)%3=1,符合假设式子。

另,当m<n时,对式子进行检验,m=3,n=5时,有

(3+0)%4=3    (3+1)%4=0   在有四个人时,绿色的应为编号3,红色的应为编号0,符合事实,在有五个人时,(3+3)%5=1,(3+0)%5=3;绿色的为1,红色的应为3,符合事实,故解法需要从最后一个开始倒推直到人数为n时,所求即为正解。

实现方法可以有:

s=0;a[0]=0;a[1]=0;

for(i=2;i<n;i++)

{s=(s+m)%i;a[i]=s;}

得到在一定的m下,不同总人数的一系列胜利者的原始编号。

下面来介绍题目的求解。

由于题目的要求是前k位留下,后k位淘汰,所以求最终剩余的方法并不方便,从后到前的时间复杂度也会变大。故使用的方法为逐个淘汰,判断 淘汰的人是否符合要求,不符合,则改变m。

要达到淘汰的为总人数的后半段,所以第一次考虑m应最小为k+1;

在此基础上,for语句循环自增m,判断合理性。

合理性的判断:

x为淘汰的人的原始编号,x=(m+s)%n      (s初始化为0,表示淘汰的人后面一个人被初始化为零后,该人的前面有几个编号的人,m+s表示的是下一次需要淘汰的人,由于共有n个人,故需要取模,使淘汰掉的人编号永远大于k,具体k个坏人的排序不需要考虑,因为是否淘汰的是坏人只需要判断是否 <k)

如果x<k 代表淘汰掉了好人,循环退出,m++;

如果x=0;说明淘汰掉的为最后一个人,设其编号为n,目的是为了避免将x<k的判断代入,影响结果。

如果处理后的淘汰人编号符合条件,则总数n--;

将淘汰的人的编码记下,其前面有多少人也记下。

当n--后与k相等,则说明该m符合条件,循环结束。

#include<stdio.h>

void main()

{

int a[15];

int x, s, i, k, n, m, tem = 0;

for (i = 1;i < 15;i++)

{

tem = 0;

for (m = i + 1;;m++)

{

if (tem == 1)

break;

s = 0;n = 2 * i;

while (1)

{

x = (s + m) % n;

if (x < 1)

x = n;

if (x <= i)

break;

n--;

s = x - 1;

if (n == i)

{

a[i] = m;

tem = 1;

break;

}}}}

while (scanf("%d", &k)&&(k != 0))

printf("%d\n",a[k]);

}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容