# 详解约瑟夫环问题及其相关的C语言算法实现

N个人围成一圈顺序编号，从1号开始按1、2、3......顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。

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

f[1]=0;

f[i]=(f[i-1]+m)%i; (i>1)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct lnode
{
int pos;
struct lnode *next;
} lnode;

/**
* 构建循环链表&&循环遍历
*/
void create_ring(lnode **root, int loc, int n)
{
lnode *pre, *current, *new;
current = *root;
pre = NULL;

while (current != NULL) {
pre = current;
current = current->next;
}

new = (lnode *)malloc(sizeof(lnode));
new->pos = loc;
new->next = current;

if (pre == NULL) {
*root = new;
} else {
pre->next = new;
}

// 循环链表
if (loc == n) {
new->next = *root;
}
}

/**
* 约瑟夫环
*/
{
int i;
lnode *pre, *pcur;

while (pcur->next != pcur) {
for (i = 1; i < p; i ++) {
pre = pcur;
pcur = pcur->next;
}

printf("%d ", pcur->pos);
pre->next = pcur->next;
free(pcur);
pcur = pre->next;
}
printf("%d\n", pcur->pos);
free(pcur);
}

{
lnode *cur;

printf("%d ", cur->pos);
cur = cur->next;
}
printf("%d\n", cur->pos);
}

int main()
{
int i, p, n;

while (scanf("%d %d", &n, &p) != EOF) {
// 构建循环链表
for (i = 1, head = NULL; i <= n; i ++)

// 约瑟夫环
if (p != 1)
else
}

return 0;
}

/**************************************************************

Problem: 1188

User: wangzhengyi

Language: C

Result: Accepted

Time:110 ms

Memory:912 kb

****************************************************************/

#include <stdio.h>
#include <stdlib.h>

int main()
{
int i, index, p, n, remain, delete[3001], flag[3001] = {0};

while (scanf("%d %d", &n, &p) != EOF) {
remain = n;
index = 0;
while (remain >= 1) {
for (i = 0; i < n; i ++) {
if (flag[i] == 0) {
// 报数
index ++;
// 报p者退出圈外
if (index == p) {
// 退出圈外
flag[i] = 1;
// 重新报数
index = 0;
delete[remain - 1] = i + 1;
remain --;
}
}
}
}

// 输出每个退出人的序号
for (i = n - 1; i >= 0; i --) {
if (i == 0) {
printf("%d\n", delete[i]);
} else {
printf("%d ", delete[i]);
}
}
}

return 0;
}

三、数学推导

#include <stdio.h>

int main(void)
{
int i, n, m, last;

while (scanf("%d", &n) != EOF && n != 0) {
// 接收报数
scanf("%d", &m);

// 约瑟夫环问题
for (i = 2, last = 0; i <= n; i ++) {
last = (last + m) % i;
}
printf("%d\n", last + 1);
}

return 0;
}