## 约瑟夫环问题——Josephus Problem

2018年04月01日 ⁄ 综合 ⁄ 共 1737字 ⁄ 字号 评论关闭

Joseph ring - known to n - (numbered 1, 2, 3... n, respectively) sitting around a round table. Number of people began to count off, from Numbers for 1 to 3 out the man; His next start from 1 number off, the man count to three
and break the ranks; In accordance with the law repeatedly, until the round out all the people around you.

Can use the list to solve the problem:
1. Manner to establish a chain of n nodes, the headless circular linked list of nodes;
2. Determine the position of the first count off people;
3. Continuously is removed from the list chain node, until the list is empty.

Create a one-way chain cycle table,  the head,Tail, cur. Head to the head of the list pointer, the addition of cur for the new node, tail to tail node,

⒈建立一个具有n个链结点，无头结点的循环链表；
⒉确定第1个报数人的位置；
⒊不断地从链表中删除链结点，直到链表为空。

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

typedef struct node{
int id;
struct node *next;
}*LIST;

LIST JoCreate(int nu)
{
int i;
LIST tail = NULL;
LIST cur;

for(i = 1; i <= nu; i++)
{
{
cur = malloc(sizeof(*cur));
if(NULL == cur)//dispose
return NULL;

cur->id = i;
tail->next = cur;

tail = cur;
}
else
{
return NULL;

}
}
}

void JoDispaly(LIST jo)
{
LIST p = jo;

do
{
printf("%d ", p->id);
p = p->next;
}while(p != jo);
printf("\n");
}

LIST JoKill(LIST jo, int nu)
{
int i;
LIST p = jo;
LIST q;

while(p->next != p)
{
for(i = 1; i < nu - 1; i++, p = p->next);

q = p->next;
p->next = q->next;
p = q->next;

free(q);
}

return p;
}

void JoDispose(LIST jo)
{
LIST q;
LIST p = jo->next;

while(p != jo)
{
q = p;
p = p->next;

free(q);
}
free(jo);
}

int main()
{
LIST jo = JoCreate(41);

JoDispaly(jo);

jo = JoKill(jo, 3);

JoDispaly(jo);

return 0;
}