Josephu 问题(小孩出列问题)

匿名网友 匿名网友 发布于: 2015-08-30 00:00:00
阅读 87 收藏 0 点赞 0 评论 0

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) //数组初始化为1 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;
}

评论列表
文章目录