Using Linked List to solve Josephus problem
这个问题是以弗拉维奥·约瑟夫斯命名的,它是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;
}