最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 经典算法数学光看剑指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;
    }
    

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 经典算法数学光看剑指offer书上(Josephuse)(组图)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论