约瑟夫问题

发表于 | 分类于 | |
字数统计: 830 | 阅读时长 ≈ 3

问题来源

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

问题抽象

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=4，M=2，被杀掉的人的序号为2,4,3。最后剩下1号。

JosephusDecimation

解法

关于约瑟夫问题的求解，可以利用循环链表来处理，但是这样是比较麻烦的。这里给出的是一种数学上的解法。

依旧假设N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后只会剩下一个。现在的问题是这个人要在最初的时候编号为多少，才能到最后不被杀呢。我们可以往前推理，由于这个人活着，那么可以得到上一轮这个人的编号，继而得到上上一轮的编号，最终我们会得到这个唯一活着的人的最初的编号。

推理是这么推，但是貌似这个也不太好计算啊！下面我们就来理解推导一下这个递推的公式。

首先第一轮有N个人（给出他们的编号）： 0,1,2,……,N-2,N-1;

当杀掉了一个人后，还剩下了M-1个人，那么这些人要重新编号。其中杀一个人表示一轮，而不是绕完一圈的轮。

JosephusDecimation1

现在我们假设第二轮中这个人的编号为k，那么他在第一轮中的编号为 (k+M)%N; 更一般的公式为 (k+M)%i，2<=i<=N;

下面来解释一下这个公式是怎么来的。取余运算的本质目的并不是要知道余数，而是为了得到按照周期排列的顺序，就像64%10，得到4是指如果每一个编一次号的话，64的编号是4。因此假设对于上面的问题，一个人编号为k（k<M）,由于杀掉了第M个人（编号为M-1，因为我们是从0开始）那么（k+M）就是上一轮的排在这个人前面的人（包括此人），那么（k+M）%i就是这个人在上一轮的编号。有了这个公式就可以递推求解了。

编程实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namespace std;

void main()
{
	int n,s,i,ss;
	int m = 3;
	while(cin>>n)
	{
		s=0;
		for(i=2;i<=n;i++)
		     s = (s+m)%i;
		ss = s+1;
		cout<<ss<<endl;

	}
}

4） 结论
当遇到一个问题时，如果能够抽象出数学模型，那么会比暴力式的方法快捷省心无数倍。

显示 Gitment 评论