约瑟夫斯问题

约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。
人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。 
问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

历史

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

解法

比较简单的做法是用循环单链表模拟整个过程，时间复杂度是O(n*m)。如果只是想求得最后剩下的人，则可以用数学推导的方式得出公式。且先看看模拟过程的解法。

Python版本

# -*- coding: utf-8 -*- class Node(object):
def __init__(self, value):
self.value = value 
self.next = Nonedef create_linkList(n):
head = Node(1)
pre = head
for i in range(2, n+1):
newNode = Node(i)
pre.next= newNode
pre = newNode
pre.next = head
return headn = 5 #总的个数m = 2 #数的数目if m == 1: #如果是1的话，特殊处理，直接输出
print (n)  
else:
head = create_linkList(n)
pre = None
cur = head
while cur.next != cur: #终止条件是节点的下一个节点指向本身
for i in range(m-1):
pre =  cur
cur = cur.next
print (cur.value)
pre.next = cur.next
cur.next = None
cur = pre.next
print (cur.value)

C++版本

#include <iostream>using namespace std;typedef struct _LinkNode {
int value;
struct _LinkNode* next;} LinkNode, *LinkNodePtr;LinkNodePtr createCycle(int total) {
int index = 1;
LinkNodePtr head = NULL, curr = NULL, prev = NULL;
head = (LinkNodePtr) malloc(sizeof(LinkNode));
head->value = index;
prev = head;

while (--total > 0) {
curr = (LinkNodePtr) malloc(sizeof(LinkNode));
curr->value = ++index;
prev->next = curr;
prev = curr;
}
curr->next = head;
return head;}void run(int total, int tag) {
LinkNodePtr node = createCycle(total);
LinkNodePtr prev = NULL;
int start = 1;
int index = start;
while (node && node->next) {
if (index == tag) {
printf("\n%d", node->value);
if (tag == start) {
prev = node->next;
node->next = NULL;
node = prev;
} else {
prev->next = node->next;
node->next = NULL;
node = prev->next;
}
index = start;
} else {
prev = node;
node = node->next;
index++;
}
}}int main() {
run(5, 999999);
return 0;}