这个问题是以弗拉维奥·约瑟夫斯命名的,它是1世纪的一名犹太历史学家。他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意,他不知道是哪一个。 – https://zh.wikipedia.org/wiki/约瑟夫斯问题

这是一个比较简单的问题,n个人围成圆圈,越过k-1个人,杀掉第k个人,如此反复直到只剩下最后一个人。可以用数学推导给出答案,问题本身已经足够简单,用链表可以模拟整个过程。实现起来比较直观。这里在初始化这个链表的时候,需要注意,到了最后一人的时候,他应该指向第一个人,这样才能形成一个环状的链表,然后问题就非常简单了,从第一人开始,后面就无所谓头和尾了,按照规则来,每次杀掉一个人,直到只剩下最后一人,就是结果。从维基的解释可以看出,最后两个人没死,这没节操的事情被拿来说,如果你数学好,你就可以救自己一命(站在合适的位置,让自己是最后一个)。

#include <iostream>
#include <fstream>
#include <sstream>

typedef struct person {
  int ID;
  struct person * next;
} person;

int main() {
  std::ifstream infile("data/id32.txt");
  std::string line;
  getline(infile, line);
  int n, k;
  std::stringstream ss(line);
  ss >> n;
  ss >> k;

  person *head = new person;
  head->ID = 1;
  person *prenode = head;
  for (int i=2; i<=n; i++) {
    person *node = new person;
    node->ID = i;
    prenode->next = node;
    prenode = node;
    if (i == n)
      node->next = head;
  }


  int left = n;
  int i=1;
  person *node = new person;
  node = head;
  while (left > 1) {
    if (i % k == 0) {
      prenode->next = node->next;
      left--;
    } else {
      prenode = node;
    }

    i++;
    node = node->next;
  }
  std::cout << node->ID << std::endl;
}