Loading AI tools
来自维基百科,自由的百科全书
約瑟夫斯置換是一個出現在電腦科學和數學中的問題。在計算機編程的演算法中,類似問題又被稱為約瑟夫環。
人們站在一個等待被處決的圈子裡。 計數從圓圈中的指定點開始,並沿指定方向圍繞圓圈進行。 在跳過指定數量的人之後,處刑下一個人。 對剩下的人重複該過程,從下一個人開始,朝同一方向跳過相同數量的人,直到只剩下一個人,並被釋放。
問題即,給定人數、起點、方向和要跳過的數字,選擇初始圓圈中的位置以避免被處決。
這個問題是以弗拉維奧·約瑟夫斯命名的,他是1世紀的一名猶太歷史學家。他在自己的日記中寫道,他和他的40個戰友被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘,最終決定自殺,並以抽籤的方式決定誰殺掉誰。約瑟夫斯和另外一個人是最後兩個留下的人。約瑟夫斯說服了那個人,他們將向羅馬軍隊投降,不再自殺。約瑟夫斯把他的存活歸因於運氣或天意,他不知道是哪一個。[1]
比較簡單的做法是用迴圈單鏈結串列類比整個過程,時間複雜度是O(n*m)。如果只是想求得最後剩下的人,則可以用數學推導的方式得出公式。且先看看類比過程的解法。
# -*- coding: utf-8 -*-
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
def 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 head
n = 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)
#include <iostream>
#include <cstdlib>
#include <cstdio>
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("%d\n", 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() {
if (argc < 3) return -1;
run(atoi(argv[1]), atoi(argv[2]));
return 0;
}
我們將明確解出時的問題。對於的情況,我們在下面給出一個一般的解法。
設為一開始有個人時,生還者的位置(注意:最終的生還者只有一個)。走了一圈以後,所有偶數號碼的人被殺。再走第二圈,則新的第二、第四、……個人被殺,等等;就像沒有第一圈一樣。如果一開始有偶數個人,則第二圈時位置為的人一開始在第個位置。因此位置為的人開始時的位置為。這便給出了以下的遞推公式:
如果一開始有奇數個人,則走了一圈以後,最終是號碼為1的人被殺。於是同樣地,再走第二圈時,新的第二、第四、……個人被殺,等等。在這種情況下,位置為的人原先位置為。這便給出了以下的遞推公式:
如果我們把和的值列成表,我們可以看出一個規律:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
從中可以看出,是一個遞增的奇數數列,每當n是2的冪時,便重新從開始。因此,如果我們選擇m和l,使得且,那麼。注意:2^m是不超過n的最大冪,l是留下的量。顯然,表格中的值滿足這個方程。我們用數學歸納法給出一個證明。
定理:如果且,則。
證明:對應用數學歸納法。的情況顯然成立。我們分別考慮是偶數和是奇數的情況。
如果是偶數,則我們選擇和,使得,且。注意。我們有,其中第二個等式從歸納假設推出。
如果是奇數,則我們選擇和,使得,且。注意。我們有,其中第二個等式從歸納假設推出。證畢。
答案的最漂亮的形式,與的二進制表示有關:把的第一位移動到最後,便得到。如果的二進制表示為,則。這可以通過把表示為來證明。
一般情況下,考慮生還者的號碼從到的變化, 我們可以得到以下的遞推公式(編號從0開始):
,
這種方法的執行時間是。
程式實現(C++)
#include <iostream>
using namespace std;
//編號從0開始,也就是說如果編號從1開始結果要加1
int josephus(int n, int k) { //非遞回版本
int s = 0;
for (int i = 2; i <= n; i++)
s = (s + k) % i;
return s;
}
int josephus_recursion(int n, int k) { //遞回版本
return n > 1 ? (josephus_recursion(n - 1, k) + k) % n : 0;
}
int main() {
for (int i = 1; i <= 100; i++)
cout << i << ' ' << josephus(i, 5) << ' ' << josephus_recursion(i, 5) << endl;
return 0;
}
對於,可以將上述方法推廣,將殺掉第k、2k、……、個人視為一個步驟,然後把號碼改變,可得如下遞推公式, 執行時間為。
程式實現(C++)
#include <cstdio>
using namespace std;
//編號從1開始,結果要加1
int josephus(int n, int k) {
if (k == 1) return n - 1;
int ans = 0;
for (int i = 2; i <= n; ) {
if (ans + k >= i) {
ans = (ans + k) % i;
i++;
continue;
}
int step = (i - 1 - ans - 1) / (k - 1); //向下取整
if (i + step > n) {
ans += (n - (i - 1)) * k;
break;
}
i += step;
ans += step * k;
}
return ans;
}
int main() {
int n, k;
while (scanf("%d%d", &n, &k) == 2)
printf("%d\n", josephus(n, k) % n + 1);
return 0;
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.