用链表解决约瑟夫斯

我已经尝试了一段时间,但是我无法弄清楚如何使下面的程序将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 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 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; } 

结果应该与这个相同(但我需要它在链表中我不明白那个):>。

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

根据原始问题, 12 。 因此,可能只需用蛮力就可以在给定的时间限制内解决。

  • 你读N
  • 从1开始寻找m的循环
  • 在循环:
    • 运行算法,使用循环变量作为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做这个,你可以把这个循环放到一个函数中。 在这种情况下打印M ,该function应该返回它。 有趣的是:链表部分由你完成。 也许你应该先尝试更简单的练习。

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

注意:我想如果你真的想学习,你应该做这样的事情,而不是跳进一个不小的问题:

  • 理解指针
  • 了解结构
  • 了解链接列表
  • 实现对链表的头/尾/特定位置的插入/更新/删除
  • 在10分钟内解决约瑟夫问题