约瑟夫斯问题

维基百科,自由的百科全书
跳转至: 导航搜索

约瑟夫斯问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环

个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。

问题是,给定了,一开始要站在什么地方才能避免被处决?

历史[编辑]

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

解法[编辑]

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

Python版本[编辑]

//参考: http://www.cnblogs.com/tudas/p/joseph-cycle-issue.html
# 单链表节点
class LinkNode:
	def __init__( self, value ):
		self.value = value
		self.next = None

# 创建循环单链表,值从1开始
def create_cycle( total ):
	head = LinkNode( 1 )
	prev = head
	index = 2
	while total - 1 > 0:
		curr = LinkNode( index )
		prev.next = curr
		prev = curr
		index += 1
		total -= 1
	curr.next = head
	return head

# 模拟约瑟夫环过程,从1开始计数
def run( total, tag ):
	assert total >= 0, 'total lq 0'
	assert tag >= 0, 'tag lt 0'
	node = create_cycle( total )
	prev = None
	start = 1
	index = start
	while node and node.next:
		if index == tag:
			print( node.value )
			if tag == start:
				prev = node.next
				node.next = None
				node = prev
			else:
				prev.next = node.next
				node.next = None
				node = prev.next
		else:
			prev = node
			node = node.next
			index += 1

run( 5, 999999 )

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

数学推导解法[编辑]

我们将明确解出时的问题。对于的情况,我们在下面给出一个一般的解法。

为一开始有个人时,生还者的位置(注意:最终的生还者只有一个)。走了一圈以后,所有偶数号码的人被杀。再走第二圈,则新的第二、第四、……个人被杀,等等;就像没有第一圈一样。如果一开始有偶数个人,则第二圈时位置为的人一开始在第个位置。因此位置为的人开始时的位置为。这便给出了以下的递推公式:

如果一开始有奇数个人,则走了一圈以后,最终是号码为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是留下的量。显然,表格中的值满足这个方程。我们用数学归纳法给出一个证明。

定理:如果,则

证明:应用数学归纳法的情况显然成立。我们分别考虑是偶数和是奇数的情况。

如果是偶数,则我们选择,使得,且。注意。我们有,其中第二个等式从归纳假设推出。

如果是奇数,则我们选择,使得,且。注意。我们有,其中第二个等式从归纳假设推出。证毕。

答案的最漂亮的形式,与的二进制表示有关:把的第一位移动到最后,便得到。如果的二进制表示为,则。这可以通过把表示为来证明。

在一般情况下,这个问题的最简单的解决方法是使用动态规划。利用这种方法,我们可以得到以下的递推公式:

如果考虑生还者的号码从是怎样变化的,则这个公式是明显的。这种方法的运行时间,但对于较小的和较大的,有另外一种方法,这种方法也用到了动态规划,但运行时间为。它是基于把杀掉第k、2k、……、2个人视为一个步骤,然后把号码改变。

程式實現

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

注释[编辑]

  1. ^ The War of the Jews 3.387-391

参考文献[编辑]

外部链接[编辑]