0

如果您不熟悉约瑟夫斯问题：

N个士兵围成一圈站成一圈，从1开始处死，M移动，最后只有一个活着。下面的代码要求输入 N 和 M 并生成最后一个站立的玩家。

#include <stdio.h>
#include <stdlib.h>
int main()
{
int N, M;
struct node { int player_id; struct node *next; }
struct node *p, *q;
int i, count;

printf("Enter N (number of players): "); scanf("%d", &N);
printf("Enter M (every M-th payer gets eliminated): "); scanf("%d", &M);

// Create circular linked list containing all the players:

p = q = malloc(sizeof(struct node));

p->player_id = 1;

for (i = 2; i <= N; ++i) {
    p->next = malloc(sizeof(struct node));
    p = p->next;
    p->player_id = i;
}  

p->next = q;// Close the circular linkedlist by having the last node point to the 1st  

// Eliminate every M-th player as long as more than one player remains:

for (count = N; count > 1; --count) {
   for (i = 0; i < M - 1; ++i)
      p = p->next;

   p->next = p->next->next;  // Remove the eiminated player from the circular linkedl
}

printf("Last player left standing is %d\n.", p->player_id);

return 0;
}

假设 N=17;M=7 输出应该是 13 上面的程序生成 2 （会发生什么？它从 M 开始计数而不是从 1 所以而不是 1,8,15 ......它消除了 7 ,14......）这是我需要你帮助的地方（因为链表对我来说仍然是一个困难的概念）。这个怎么修改？

4

1 回答 1

0

您将节点移除线放置在错误的位置。

for (count = N; count > 1; --count) {
   for (i = 0; i < M - 1; ++i)
      p = p->next;

   p->next = p->next->next;
}

您将此行放在从头开始计算 M 个节点的循环之后，因此它始终从删除第 (M+1) 个节点开始。您应该在它之前移动它，以便它从第一个节点开始。

for (count = N; count > 1; --count) {
   p->next = p->next->next;
            for (i = 0; i < M - 1; ++i) p = p->next;

}

这就是你要找的吗？

于 2013-06-02T20:23:59.850 回答