约瑟夫环问题(圆圈中最后剩下的数字)的数学推理解法

╰半橙微兮° 2022-03-08 08:52 739阅读 0赞

## 问题描述 ##

> 约瑟夫环（Josephuse）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

## 假设 ##

假设编号从 0 开始，每次删除第  m m m 个节点。

举例说明： ( 0 , 1 , 2 , 3 , 4 ) (0, 1, 2,3,4) (0,1,2,3,4)这 5 个数字组成圆环，每次删除第 3 个节点。第一个删除的是  2 2 2，圆环变成  ( 0 , 1 , 3 , 4 ) (0,1,3,4) (0,1,3,4)；从被删除的节点的下一位开始，也就是从节点 3 开始报数，此时序列可以看作  ( 3 , 4 , 0 , 1 ) (3,4,0,1) (3,4,0,1)，删除第三个节点，也就是  0 0 0。以此类推，删除的顺序为  2 → 0 → 4 → 1 2 \\to 0 \\to 4 \\to 1 2→0→4→1，最后剩下的数字是  3 3 3。

## 常见的两种解法 ##

1.  使用链表数据结构模仿环。
2.  数学推理寻找递推公式。

## 数学推理解法 ##

本节主要介绍求取递推公式解决的方法。

1.  对于 n 个数字 ( 0 , 1 , . . . , n − 1 ) (0,1,...,n-1) (0,1,...,n−1)中删除第 m 个数字的问题，最终剩下的那个数字可以表示为  f ( n , m ) f(n,m) f(n,m)。注意， **f ( n , m ) f(n,m) f(n,m)是该问题的解，是一个数字**。
2.  删除第一个数字，被删除的必定是  ( m − 1 ) % n (m-1)\\%n (m−1)%n，将  ( m − 1 ) % n (m-1)\\%n (m−1)%n 记作  k k k。
3.  此时，序列可以改写为  ( k + 1 , k + 2 , . . . , n − 1 , 0 , 1 , . . . , k − 1 ) (k+1,k+2,...,n-1,0,1,...,k-1) (k\+1,k\+2,...,n−1,0,1,...,k−1)，从节点  k + 1 k+1 k\+1开始报数。
4.  删除一个节点后问题规模减  1 1 1。最终剩下的那个数字不能直接表示为  f ( n − 1 , m ) f(n-1,m) f(n−1,m)，因为此时序列不再是从  0 0 0 开始，也就是函数  f f f 不满足。我们可以将这个数字表示为另一个函数，如  g ( n − 1 , m ) g(n-1,m) g(n−1,m)。
5.  因为最终剩下的那个数字是固定的，所以  f ( n , m ) = g ( n − 1 , m ) f(n,m) = g(n-1,m) f(n,m)=g(n−1,m)。
6.  我们需要将序列  ( k + 1 , k + 2 , . . . , n − 1 , 0 , 1 , . . . , k − 1 ) (k+1,k+2,...,n-1,0,1,...,k-1) (k\+1,k\+2,...,n−1,0,1,...,k−1) 作一个映射，以便可以继续用函数  f f f 表示这个  ( n − 1 ) (n-1) (n−1) 规模问题的解，从而找到  f ( n , m ) f(n,m) f(n,m) 与  f ( n − 1 , m ) f(n-1,m) f(n−1,m)之间的递推关系，映射如下：  
     k + 1    →    0 k+1 \\ \\ \\to \\ \\ 0 k\+1  →  0  
     k + 2    →    1 k+2 \\ \\ \\to \\ \\ 1 k\+2  →  1  
    …  
     n − 1    →    n − k − 2 n-1 \\ \\ \\to \\ \\ n-k-2 n−1  →  n−k−2  
     0           →    n − k − 1 0 \\ \\ \\ \\ \\ \\ \\ \\ \\ \\to \\ \\ n-k-1 0         →  n−k−1  
     1           →    n − k 1 \\ \\ \\ \\ \\ \\ \\ \\ \\ \\to \\ \\ n-k 1         →  n−k  
    …  
     k − 1    →    n − 2 k-1 \\ \\ \\to \\ \\ n-2 k−1  →  n−2  
    此时序列从 0 开始，将这个映射关系定义为  p ( x ) = ( x − k − 1 ) % n p(x) = (x-k-1)\\%n p(x)=(x−k−1)%n，有  p ( g ( n − 1 , m ) ) = f ( n − 1 , m ) p(g(n-1,m)) =f(n-1,m) p(g(n−1,m))=f(n−1,m)。
7.  这个映射的逆映射是  p − 1 ( x ) = ( x + k + 1 ) % n p^\{-1\}(x) = (x+k+1)\\%n p−1(x)=(x\+k\+1)%n，即  g ( n − 1 , m ) g(n-1,m) g(n−1,m) =  p − 1 ( f ( n − 1 , m ) ) = ( f ( n − 1 , m ) + k + 1 ) % n p^\{-1\}(f(n-1,m))=(f(n-1,m)+k+1)\\%n p−1(f(n−1,m))=(f(n−1,m)\+k\+1)%n 。
8.  将  k = ( m − 1 ) % n k=(m-1)\\%n k=(m−1)%n代入得到递推公式， f ( n , m ) = g ( n − 1 , m ) = ( f ( n − 1 , m ) + m ) % n f(n,m) = g(n-1,m) = (f(n-1,m)+m)\\%n f(n,m)=g(n−1,m)=(f(n−1,m)\+m)%n。
9.  考虑 n 为 1 的情况，此时序列只有 1 个节点，所以最后剩下的数字必定就是 0。

通过上面的分析，我们已经可以得到完整的递推公式：

f ( n , m ) = 0 ,    n = 1 \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ f(n,m) = 0, \\ \\ n = 1               f(n,m)=0,  n=1  
                f ( n , m ) = ( f ( n − 1 , m ) + m ) % n    ,   n > 1 \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ f(n,m) = (f(n-1,m)+m)\\%n \\ \\ ,\\ n \\gt 1               f(n,m)=(f(n−1,m)\+m)%n  , n>1

## 代码实现 ##

获得递推公式之后，使用循环或者递归都很简单，下面是《剑指offer》中C++实现的循环解法（懒得写了～～～）。

int lastRemaining(int n, int m){ 
    	if(n < 1 || m < 1)
    		return -1;
    	
    	int last = 0;
    	for(int i = 2; i <= n; i++){ 
    		last = (last + m) % i;
    	}
    	return last;
    }

--------------------

正文结束，欢迎留言讨论。