约瑟夫问题_公式原理详解

一、约瑟夫问题：

在计算机编程的算法中，类似问题又称为约瑟夫环
约瑟夫环：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。
例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。
如图：

二、公式原理

同例：N个人围成一圈，从第一个开始从1报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

如果我们从N个人开始一个一个的将被杀死的取出，我们要不断的循环遍历约瑟夫环，时间复杂度高达O（M*N）

假设我们反向推导，从只有一个人参与这个游戏开始，递推出N个人参加游戏的结果，就会变得简单多了，推导原理如下：

总人数：1人
	F（1,5）=0，假设存活人的序号为x
总人数：2人：
	假设另外一个被杀的人的序号是a，则报数顺序是一定的
	报数顺序：a x a x a (一死一活，已知x号是存活者，则第五个报数人必死)
	假设我们每次都是从位置0处开始报数的，则可知排序位置：序号[位置]
	排序位置：a[0] x[1];
总人数：3人
	假设第二位被杀的人的序号是b，则报数顺序依然确定
	报数顺序：x b a x b（俩个条件确定顺序：1、第五个一定是b死；2、b死后总人数为2的排序已知）
	排序位置：x[0] b[1] a[2]
总人数：4人
	假设第三位被杀的人的序号是c，则报数顺序依然确定
	报数顺序：c x b a c（同理）
	排序位置：c[0] x[1] b[2] a[3]
总人数：5人
	假设第四位被杀的人的序号是d，则报数顺序依然确定
	报数顺序：c a b 1 d（同理）
	排序位置：c[0] x[1] b[2] a[3] d[4]
总人数：6人
	假设第五位被杀的人的序号是e，则报数顺序依然确定
	报数顺序：c a b 1 e（e插入1和d之间）
	排序位置：x[0] b[1] a[2] d[3] e[4] c[5]

最后推导出存活者的位置，从而得出存活者序号=当前位置+1

如图：

三、公式递推

假设：
存活者位置 = F（N，M）；

例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。可知：
存活者位置 = F（6，5）；

给出例子中求存活者位置的递推过程
F（1，5）= 0
F（2，5）= （F（1，5）+5）% 2 = 1
F（3，5）= （F（2，5）+5）% 3 = 0
F（4，5）= （F（3，5）+5）% 4 = 1
F（5，5）= （F（4，5）+5）% 5 = 1
F（6，5）= （F（5，5）+5）% 6 = 0

思考：为什么加5取余？

例：F（3，5）= （F（2，5）+5）% 3 = 0

<mark>第一：加五是因为每报五个数就杀一人</mark>
<mark>第二：取余是因为只有3个人的位置</mark>

1、因为在两个人的基础上多了一个人，而这个多出来的一个人一定是报第五个数而被杀的人，所以存活者的位置增加了五个位置单位，
2、此时总共才三个人，也就只有0、1、2三个位置，而要增加五个单位，例如三个人的位置分别为[0] 、[1]、[2]，增加五个位置单位，[1]->[2]->[0]->[1]->[2]->[0]，也就是环形遍历约瑟夫环，得出最后停在[0]的位置，这也是取3的余数得出的结果。

最后我们得出公式
F（N，M）=（F（N-1，M）+M）%N

C语言代码

#include<stdio.h>
int main()
{
	int n,m;
	while(scanf("%d %d",&n,&m)!=-1)
	{
		int p=0;
		for(int i=2;i<=n;i++)
			p=(p+m)%i;
		printf("%d\n",p+1);
	}
	return 0;
}