这个问题是以弗拉维奥·约瑟夫斯命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。 — https://zh.wikipedia.org/wiki/约瑟夫斯问题
这是一个比较简单的问题，n个人围成圆圈，越过k-1个人，杀掉第k个人，如此反复直到只剩下最后一个人。可以用数学推导给出答案，问题本身已经足够简单，用链表可以模拟整个过程。实现起来比较直观。这里在初始化这个链表的时候，需要注意，到了最后一人的时候，他应该指向第一个人，这样才能形成一个环状的链表，然后问题就非常简单了，从第一人开始，后面就无所谓头和尾了，按照规则来，每次杀掉一个人，直到只剩下最后一人，就是结果。从维基的解释可以看出，最后两个人没死，这没节操的事情被拿来说，如果你数学好，你就可以救自己一命（站在合适的位置，让自己是最后一个）。
1. #include <iostream>
2. #include <fstream>
3. #include <sstream>
6. typedef struct person {
7. int ID;
8. struct person * next;
9. } person;
12. int main() {
13. std::ifstream infile("input.txt");
14. std::string line;
15. getline(infile, line);
16. int n, k;
17. std::stringstream ss(line);
18. ss >> n;
19. ss >> k;
21. person *head = new person;
22. head->ID = 1;
23. person *prenode = head;
24. for (int i=2; i<=n; i++) {
25. person *node = new person;
26. node->ID = i;
27. prenode->next = node;
28. prenode = node;
29. if (i == n)
30. node->next = head;
31. }
34. int left = n;
35. int i=1;
36. person *node = new person;
37. node = head;
38. while (left > 1) {
39. if (i % k == 0) {
40. prenode->next = node->next;
41. left--;
42. } else {
43. prenode = node;
44. }
46. i++;
47. node = node->next;
48. }
49. std::cout << node->ID << std::endl;
50. }