算法24约瑟夫环n个数字(0,1,,n1)形成一个圆圈,从数字0开始......
-
资源ID:193224139
资源大小:88.88KB
全文页数:4页
- 资源格式: PDF
下载积分:10积分
快捷下载
会员登录下载
微信登录下载
微信扫一扫登录
友情提示
2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
|
算法24约瑟夫环n个数字(0,1,,n1)形成一个圆圈,从数字0开始......
算法 24约瑟夫环n 个数字(0,1,n-1)形成一个圆圈,从数字 0 开始.http:/ 题目:n 个数字(0,1,n-1)形成一个圆圈,从数字 0 开始,每次从这个圆圈中删除第 m 个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第 m 个数字。求出在这个圆圈中剩下的最后一个数字。分析:我们完全可以用计算机来模拟上述过程,每找到一个要删除的数,需要扫描 m 次,总共删除 n-1 个数,所以总得扫描次数为 m*(n-1)。这是一个平方级的复杂度,下面来考虑如何对它进行改进。改进:上述模拟过程效率低的原因是,每次找到要删除的数都要进行 m 次的查找,怎么来减少查找次数?可我们又注意到,可以通过计算来找到那个要删除的数,比如第一次删除,(m-1)%n 的结果即为要删除的数。可删除了该数以后怎么办呢?下面的计算应当怎么进行呢?归纳:假设在某一时刻删除的数为第 k 个,并且知道 k 前面有 A 个数,k 后面有 B 个数,那么可以对 A,B 进行运算而求得下一次应当删除的数是哪一个?现在问题变为,如何统计 A,B 的信息。导致上述归纳行不通的原因自己分析如下:1.归纳基础不恰当 2.这样归纳下去得到的结果是想要的吗?3.信息不够,导致分析不能继续进行下去,所以得从题目中挖掘出更多的信息,明确题目最终要求的是什么。如何来过掉这道坎?再归纳:题目要求最后剩下的一个数(用 last 表示),也就是这个数是第几个,在(0,1,n-1)的位置是多少。明确了题目中的信息,所以我们要对这个数进行归纳。假设知道这个数在剩下的 k 个数中的位置,怎么来求得它在剩余 K+1 个数中的位置,这样一步一步推导出它在有 n 个数中的位置,即为所求。为什么能这样归纳,因为这个最后剩下的数在所有删除过程中有幸存活下来,只不过每次删除了一个数,它的位置就变了,知道最后,它的位置为 0(只剩一个数了)。现在来分析删除第一个数后,last 这个数的位置已之前有什么样的关系。在这 n 个数字中,第一个被删除的数字是(m-1)%n,为简单起见记为 k。那么删除 k 之后的剩下 n-1 的数字为 0,1,k-1,k+1,n-1,并且下一个开始计数的数字是k+1。相当于在剩下的序列中,k+1 排到最前面,从而形成序列 k+1,n-1,0,k-1。k+1 ->0 k+2 ->1 n-1 ->n-k-2 0 ->n-k-1 k-1 ->n-2 现在我们知道了有 n-1 个数时 last 的位置,记为 f(n-1,m),那么如何来求得 f(n,m)关于 f(n-1,m)之间的关系?用 X,Y 来表示,如下:Y X k+1 ->0 k+2 ->1 n-1 ->n-k-2 0 ->n-k-1 k-1 ->n-2 y=(x+k+1)%n k=(m-1)%n 所以 y=(x+m)%n,最终关系如下:0 n=1 f(n,m)=f(n-1,m)+m%n n>1 参考代码:int LastRemaining(unsigned int n,unsigned 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;代码来源于:http:/