约瑟夫环

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

如果用Ｃ来写的话，也会有许多的方法，比如１：采用链表（双向链表）２：递归３：队列（不断出队与入队）　４：非递归循环。

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

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

假设从零开始报，报到ｍ－１的人退出，那么应该报ｍ的人开始报零，再报到ｍ－１，该报ｍ的人报零，以此类推，当所剩人数为二的时候，两个人依次从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]);

}