经典算法数学光看剑指offer书上(Josephuse)(组图)

问题描述

Title: 0,1,…,n-1 n个数字排成一圈，从数字0开始，每次从这个圈子中删除第m个数字，找到圈内最后一个数字。

比如0、1、2、3、4，这五个数字组成一个圆圈，从0开始每次删除第三个数字，前四个要删除的数字是2、0、4、1 最后剩下的数是3

解决方案

这个问题就是著名的约瑟夫斯问题。解决问题一般有两种方法：

用循环链表模拟圆的经典算法，分析每次删除数的规律，直接计算出圆内的数。最后剩下的数字经典算法数学解法

offer book 里面还有很多我没有完全理解的信息。想了半天，和同学讨论后被这位博主给启发了：

我们举个例子来说明这个方法

假设n=9，m=3：有n个孩子，从1数到m的出队，最后剩下的孩子获胜。

每次向m报告后m环想细解法，必须从出列child的下一个位置重新开始计数，然后我们要重新映射，也就是书籍和很多文章中的分析：

我们的目的是找到胜利孩子的位置！使用inverse方法，只从一个child开始分析，下图中m=3，第一列是新开始的起点

从只有1个孩子到2个孩子的位置确定：m=3

从 2 到 3：

以此类推，我们用f(n)来表示获胜者在n个孩子中的位置m环想细解法，那么获胜者在n+1个孩子中的位置是f(n+1)=(f(n)+m)% (n+1)，已知f(1)=0，迭代方程出来后，我们可以用递归或者循环来解决这个问题

循环解决：

int lastRemaining(unsigned int n,unsigned m){
	if(n < 1 ||m < 1){

		return -1;
	}
	int winner=0;
	for(int i=2;i<=n;i++){
		winner=(winner + m)% i;
	}
	return winner;
}

递归解：

int lastRemaining(unsigned int n,unsigned m){
	if(n < 1 ||m < 1){
		return -1;
	}
	if(n == 1){
		return 0;
	}else
	return (lastRemaining(n - 1, m)+m)%n;
}