約瑟夫斯問題

約瑟夫問題（有時也稱為約瑟夫斯置換），是一個出現在計算機科學和數學中的問題。在計算機編程的算法中，類似問題又稱為約瑟夫環。

人們站在一個等待被處決的圈子裡。 計數從圓圈中的指定點開始，並沿指定方向圍繞圓圈進行。 在跳過指定數量的人之後，執行下一個人。 對剩下的人重複該過程，從下一個人開始，朝同一方向跳過相同數量的人，直到只剩下一個人，並被釋放。

問題即，給定人數、起點、方向和要跳過的數字，選擇初始圓圈中的位置以避免被處決。

基本介紹

• 中文名：約瑟夫斯問題
• 學科：計算機

歷史

這個問題是以弗拉維奧·約瑟夫命名的，它是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;}