Josephu 问题:数组实现和链表实现
最后更新于：2022-04-01 21:39:57
Josephu 问题为：设编号为1，2，⋯ n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
### 数组实现
~~~
#include
#include
int Josephu(int n, int m)
{
int flag, i, j = 0;
int *arr = (int *)malloc(n * sizeof(int));
for (i = 0; i < n; ++i)
arr[i] = 1;
for (i = 1; i < n; ++i)
{
flag = 0;
while (flag < m)
{
if (j == n)
j = 0;
if (arr[j])
++flag;
++j;
}
arr[j - 1] = 0;
printf("第%4d个出局的人是：%4d号\n", i, j);
}
free(arr);
return j;
}
int main( )
{
int n, m;
scanf("%d%d", &n, &m);
printf("最后胜利的是%d号！\n", Josephu(n, m));
//system("pause");
return 0;
}
~~~
### 链表实现
~~~
#include
#include
typedef struct Node
{
int index;
struct Node *next;
}JosephuNode;
int Josephu(int n, int m)
{
int i, j;
JosephuNode *head, *tail;
head = tail = (JosephuNode *)malloc(sizeof(JosephuNode));
for (i = 1; i < n; ++i)
{
tail->index = i;
tail->next = (JosephuNode *)malloc(sizeof(JosephuNode));
tail = tail->next;
}
tail->index = i;
tail->next = head;
for (i = 1; tail != head; ++i)
{
for (j = 1; j < m; ++j)
{
tail = head;
head = head->next;
}
tail->next = head->next;
printf("第%4d个出局的人是：%4d号\n", i, head->index);
free(head);
head = tail->next;
}
i = head->index;
free(head);
return i;
}
int main( )
{
int n, m;
scanf("%d%d", &n, &m);
printf("最后胜利的是%d号！\n", Josephu(n, m));
//system("pause");
return 0;
}
~~~
';