-1

我已经尝试了一段时间，但我不知道如何让下面的程序以 N 作为输入并生成一个 M，以便最后一个死去的士兵是第 13 个（N>13）；

 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 linked list.
     }    printf("Last player left standing is %d\n.", p->player_id);

   return 0;
  }

结果应该与这个相同（但我需要它在链表中，因为我不明白那个）：>。

4

1 回答 1

1

我没有阅读上面的所有代码，我认为它可以找到给定的最后一项N和M

根据原问题，12<N<100. 所以，可能它可以在给定的时间限制内简单地用蛮力解决。

  • 你读了N
  • m从 1开始循环查找
  • 在循环：
    • 运行算法，使用循环变量 as m。如果最后一项是 13，则返回循环变量。

编辑：你不必工作很多。您只需启动一个循环而不是阅读M.

M=1;
while(1)
{
//your code goes here: 
//build up the linked list with N element
//eliminate the nodes, until only one remains
//instead of writing out the last number, you check it: if it equals 13 print M, if doesn't, increment `M` and continue the loop.
 if(p->player_id==13)
 {
   printf("The minimal M is: %d\n", M);
   break;
 }
 else
   M++;
}

如果您想对多个N-s 执行此操作，您可以将此循环放入一个函数中。在这种情况下 insted 打印M，函数应该返回它。有趣的是：链表部分是你做的。也许你应该先尝试更简单的练习。

编辑2： 这是我的最终答案，检查结构和输出，我希望它是可以理解的。

注意：我认为如果你真的想学习，你应该做这样的事情而不是跳入一个不简单的问题：

  • 了解指针
  • 理解结构
  • 了解链表
  • 对链表的头/尾/特定位置实现插入/更新/删除
  • 10分钟自己解决约瑟夫问题
于 2013-06-01T18:01:33.007 回答