跳至內容

約瑟夫問題

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

約瑟夫斯置換是一個出現在電腦科學數學中的問題。在計算機編程的演算法中,類似問題又被稱為約瑟夫環

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

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

歷史

這個問題是以弗拉維奧·約瑟夫斯命名的,他是1世紀的一名猶太歷史學家。他在自己的日記中寫道,他和他的40個戰友被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘,最終決定自殺,並以抽籤的方式決定誰殺掉誰。約瑟夫斯和另外一個人是最後兩個留下的人。約瑟夫斯說服了那個人,他們將向羅馬軍隊投降,不再自殺。約瑟夫斯把他的存活歸因於運氣或天意,他不知道是哪一個。[1]

解法

比較簡單的做法是用迴圈單鏈結串列模擬整個過程,時間複雜度是O(n*m)。如果只是想求得最後剩下的人,則可以用數學推導的方式得出公式。且先看看模擬過程的解法。

Python版本

# -*- 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)

C++版本

#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;
}

對於,可以將上述方法推廣,將殺掉第k2k、……、個人視為一個步驟,然後把號碼改變,可得如下遞推公式, 執行時間為

程式實現(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;
}

註釋

  1. ^ The War of the Jews 3.387-391

參考文獻

外部連結