史上最全的约瑟夫环算法程序和原理

数学算法:

#include "stdio.h"
#include "stdlib.h"

int josephus(int n, int m)
{
int pos;
if (n == 1) {
return 1;
} else {
pos = (josephus(n-1, m) + m -1)%n + 1;
}

return pos;
}

int josephus_no_recurse_1(int n, int m)
{
int s = 0;
int i;
for (i=2; i<=n; i++) {
s = (s + m)%i;
}
return s + 1;
}

int josephus_no_recurse_2(int n, int m)
{
int s = 1;
int i;
for (i=2; i<=n; i++) {
s = (s + m -1)%i + 1;
if (s == 0) {
s = n;
}
}
return s;
}

/*

以前两个非递归的算法，在http://baike.baidu.com/view/717633.htm说： 我们需要对f[n]=(f[n-1]+k)%n式进行修正：

　　f[n]=(f[n-1]+k)%n;if(f[n]==0)f[n]=n;

测试时发现：需不需要修正是根据情况而定的－－josephus_no_recurse_1这种不需要

*/

int main()
{
int n;
int m;
int i;
int count;
printf("pls input total num:/n");
scanf("%d", &n);
printf("pls input a loop count:/n");
scanf("%d", &m);
printf("n:%d, m:%d/n", n, m);

printf("last one:%d/n", josephus(n, m));
printf("no_recurse_algo last one:%d/n", josephus_no_recurse(n, m));
printf("no_recurse_algo_2 last one:%d/n", josephus_no_recurse_2(n, m));

return 0;
}

模拟算法：

#include<stdio.h>
#define MAX_COUNT 300

int main()
{
int n;
int m;
int i;
int data[MAX_COUNT];
printf("pls input total num:/n");
scanf("%d", &n);
if (n>MAX_COUNT) {
printf("total num exceed!/n");
return 1;
}
printf("pls input a loop count:/n");
scanf("%d", &m);
printf("n:%d, m:%d/n", n, m);

for (i=0; i<n; i++) {
data[i] = i+1;
}

int loop;
int count;
int pos;
count = 0;
pos = 0;
while (count<n) {
loop = 0;
while (loop<m) {
while (data[pos]==0){
pos = (pos+1)%n;
}
++loop;
pos = (pos + 1) % n;
}
--pos;
if (pos<0) {
pos = n - 1;
}
if (count == n-1) {
printf("last one:%d/n", data[pos]);
}
data[pos] = 0;
++count;
}

return 0;
}

链表算法:

#include "stdio.h"
#include "stdlib.h"

struct Node {
int id;
struct Node* next;
} node;

int main()
{
int n;
int m;
int i;
int count;
printf("pls input total num:/n");
scanf("%d", &n);
printf("pls input a loop count:/n");
scanf("%d", &m);
printf("n:%d, m:%d/n", n, m);

struct Node *first, *cur, *last;

first = NULL;

for (i=0; i<n; i++) {
cur = (struct Node*) malloc(sizeof(struct Node));
cur->id = i + 1;
if (first == NULL) {
last = first = cur;
} else {
last->next = cur;
last = cur;
}
}

last->next = first; // make the link to be a loop link

count = 1;
while (first != NULL) {
if (first->next == first) {
printf ("/nlast one:%d/n", first->id);
free(first);
break; // end while loop
}

if (count == m-1) {
cur = first->next; // cur poit to the out queue node
first->next = cur->next;
free(cur);
count = 0;
}

++count;
first = first->next;
}

return 0;
}

http://elite-lcf.blog.hexun.com/39488237_d.html

首先一开始的序列

序列 1 ： 1, 2, 3, 4, …, n-2, n-1, n

此时出队列的第一个人，位置为 k ， 号码肯定是 m%n 。这个应该没有问题，也就是取余操作使得数组类似能够有循 环的功能。

此时序列 2 ： 1, 2, 3, 4, … k-1, k+1, …, n-2, n-1, n

此时 k出队列，序列2中为n-1个人了。

根据序列 2 ， 得到序列 3 ：

k+1, k+2, k+3, …, n-2, n-1, n, 1, 2, 3,…, k-2, k-1

从序列2得到序列3很简单，也就是将k+1作为 开始，然后将1连到n的后面，其实只是位置的不同，但是本质两个序列是一样的。所以同样，这里也是n-1个元素。

序列3可以映射得到序列4：

1, 2, 3, 4, …, 5, 6, 7, 8, …, n-2, n-1

这里我就乱掉了，这个映射是可以做，但是映射关系 是怎样的？

OK,先不管映射关系， 我们继续来推导。

对于序列4，我们 假设能够得到解，也就是最后一个退出的人的号码，设置为x。如果我们能够通过映射关系，将x在序列3中对应的号码x’求出来，那我们就可以得到序列3的 解，因为序列3其实和序列2是同一个，所以序列2的解我们也就得到了，序列2就是序列1去掉一个k，这个k对于序列1的解没有任何影响，所以序列1的答案 就是求出来的x’。

那关键就是如何 通过x得到x’ ，也就是映射关系的问题。

对于序列4，如果我们要得到1到n-1序列中的值，我们也是做取余操作，只不过除数变为n-1了。

但是如何得到关系为 x'=(x+m)%n，从而得到递推式

f(i)=(f(i-1)+m)%i

还是没法理解出来

序列三：k+1, k+2, k+3, …, n-2, n-1, n, 1, …, k-2, k-1

序列四: 1 , 2 , 3 , …,n-k-2, n-k-1, n-k, n-k+1, …,n-2, n-1

又∵ k=m%n;
∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n
∴x'= (x+ m%n)%n = (x+m)%n

证毕

为什么x' = x+k,我们要看：

http://itt8.com/bckf/72016_2.html

在编号
第一个人(编号是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环
（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。

现在我们把他们的编号 做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1 （已经出列）

变换后就完完全全成为了(n-1)个人报数的子问题，假如 我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？
变回去的公式很简单，
1 对应k+1 2对应k+2……x对应k+x（如上面对应转换）
所以x`=x+k
但当x`<k时x`=x+k-n
所以 推出来：x'=(x+k)%n

http://baike.baidu.com/view/717633.htm

x‘=（x+k）%n,由此，我们可以得到一个递推公式

　　f[1]=1
　　f[n]=(f[n-1]+k)%n （n>1）
　　如果你认为上式可以推出约瑟夫环问题的解，很不幸，你错了，上面的递推公式中，在某种情况 下，f[n-1]+k会整除n，如n=2，k=3，这时我们修要对上式进行修正，
　　f[n]=(f[n-1]+k)%n;if(f[n]==0)f[n]=n;
　　问题得解

还没看的：

http://hi.baidu.com/tangqiaoboy/blog/item/da7428d37bac7f023bf3cf37.html/cmtid/c5efad1927dafa4943a9ad82

http://www.cppblog.com/guyuecanhui/articles/76443.html

http://baike.baidu.com/view/717633.htm