剑指offer：理解约瑟夫环问题的数学解法（圆圈中最后剩下的数字）

素颜马尾好姑娘i 2022-02-25 06:06 334阅读 0赞

# 问题描述 #

题目：0,1，…，n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字，求出这个圆圈里剩下的最后一个数字。  
例如，0,1,2,3,4,这五个数字组成一个圆圈，从0开始每次删除第3个数字，则删除的前四个数字依次为2、0、4、1最后剩下的数字是3  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70]

# 解题思路 #

这道题是有名的约瑟夫环（Josephuse）问题，解题一般有两种方法：

1.  用环形链表模拟圆圈的经典算法
2.  分析每次被删除的数字的规律，直接计算出圆圈中最后剩下的数字

# 经典算法 #

*  用数据结构来模拟这个圆圈，常用的有环形链表。我们可以自定义一个n个节点的环形链表，每次在这个链表中删除第m个节点，最后剩下的结点就是我们求的结果。
 *  可以用C++的stl库中的list，每次迭代器扫描到链表尾部，就把迭代器移动到链表头部，做一个循环，代码就不贴了，原理很简单
 *  这种方法需要遍历很多次，花费时间复杂度为O(nm)—m步+n个数字，空间复杂度为O(n)—辅助链表开销。

# 数学解法 #

光看剑指offer书上还有很多资料都没有理解透彻，思考了很久，和同学讨论之后还是在这位博主这得到启发：[https://blog.csdn.net/u011500062/article/details/72855826][https_blog.csdn.net_u011500062_article_details_72855826]  
我们拿一个例子来说明这个方法  
**假设n=9，m=3：有n个孩子，从1开始报数到m的出列，最后剩下的孩子胜利**  
每次报到m之后都要从出列的孩子的下一个位置重新开始报数，那么我们要重新做映射，也就是书本上和很多文章上的解析：  
![在这里插入图片描述][20190401022950480.png]  
我们的目的是要找到那个胜利的孩子的位置！采用逆推法，从只有一个孩子开始分析，下图的m=3，第一列为新开始的起点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 1]  
从只有1个孩子到2个孩子胜利者的位置确定：m=3  
![在这里插入图片描述][20190401023834713.png]  
从2个到3个：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 2]  
依次类推，我们用f(n)表示n个孩子中胜利者的位置，那么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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70]: /images/20220225/a0448cf135c145068837a813463b1ed9.png
[https_blog.csdn.net_u011500062_article_details_72855826]: https://blog.csdn.net/u011500062/article/details/72855826
[20190401022950480.png]: /images/20220225/dbb6d175970644e6a075652d51266b55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 1]: /images/20220225/d94cb9850554464a8181db5fc09aa2a0.png
[20190401023834713.png]: /images/20220225/bcbc9f3987d949f1902f7eb51b124535.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2ODA0MzYz_size_16_color_FFFFFF_t_70 2]: /images/20220225/a0babed1d3ee463193e96f213dcdfda4.png