5730人阅读
& & & & &昨天刚做了约瑟夫环问题，发现不会做了，还是上网搜了一下约瑟夫环的解法才过的。在网上转载了一下约瑟夫环问题的数学做法，感觉别的方法太麻烦，而且时间复杂度也比较高。
约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
& & & & 问题描述：n个人（编号0~(n-1))，从0开始报数，报到m-1的退出
　　，剩下的人继续从0开始报数。求胜利者的编号。
　　我们知道第一个人(编号一定是(m-1)%n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
　　k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
　　并且从k开始报0。
　　现在我们把他们的编号做一下转换：
　　k --& 0
　　k+1 --& 1
　　k+2 --& 2
　　k-3 --& n-3
　　k-2 --& n-2
　　序列1： 0, 1, 2, 3 … n-2, n-1
　　序列2： 0, 1, 2, 3 … k-1, k+1, …, n-2, n-1
　　序列3： k, k+1, k+2, k+3, …, n-2, n-1, 1, 2, 3,…, k-2,
　　序列4：0, 1, 2, 3 …, 5, 6, 7, 8, …, n-3, n-2
　　变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解 & & & & & & & 吗？！！变回去的公式很简单，相信大家都可以推出来：
　　∵ k=m%n;
　　∴ x' = x+k = x+ m% 而 x+ m%n 可能大于n
　　∴x'= (x+ m%n)%n = (x+m)%n
　　得到 x‘=(x+m)%n
　　如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下 & & & & & 面写递推公式：
　　令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n].
　　递推公式:
　　f[1]=0;
　　f[i]=(f[i-1]+m)%i; (i&1)
　　有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。我们输出f[n]由于是逐级递推，不需要保存每个，程序也是异常简单：(注意编号是0 -- n-1)
　　#include &stdio.h&
　　int main(void)
　　int n, m, i, s=0;
　　printf (&N M = &);
　　scanf(&%d%d&, &n, &m);
　　for (i=2; i&=n; i++)
　　s=(s+m)%i;
　　printf (&The winner is %d\n&, s);
　　return 0 ;
　　时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且 & & & & & 往往会成倍地提高算法执行效率。
　　参照上面提供的思路，我认为可以类似的得到一个更易于明白的方法，设有（1,2,3，……，k-1，k，k+1，……，n）n个数，当k出列时，那么有
　　k+1 --&1
　　k+2 --&2
　　n --&n-k
　　1 --&n-k+1
　　k-1 --&n-1
　　由上面一组式子可以推出，若知道新产生的n-1个数中某个数x，那么很显然可以推出x在原数列里的位置，即x‘=（x+k）%n,由此，我们可以得到一个递推公式
　　f[1]=1
　　f[n]=(f[n-1]+k)%n （n&1）
　　如果你认为上式可以推出约瑟夫环问题的解，很不幸，你错了，上面的递推公式中，在某种情况下，f[n-1]+k会整除n，如n=2，k=3，这时我们修要对上式进行修正，
　　f[n]=(f[n-1]+k)%n;if(f[n]==0)f[n]=n;
　　问题得解。 程序代码如下：
　　#include&stdio.h&
　　int main()
　　int n,k,s=1;
　　scanf(&%d%d&,&n,&k);
　　for(int i=2;i&=n;i+=1)
　　s=(s+k)%i;
　　if(s==0)s=i;
　　printf(&ans=%d\n&,s);
　　return 0;
　　当然，我们还可以用递归方法解决此问题：
　　#include&stdio.h&
　　int main()
　　int jos(int n,int k);
　　int n,k,s;
　　scanf(&%d%d&,&n,&k);
　　s=jos(n,k);
　　printf(&ans=%d\n&,s);
　　return 0;
　　int jos(int n,int k)
　　if(n==1)x=1;
　　else {x=(jos(n-1,k)+k)%n;if(x==0)x=n;}
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：14840次
排名：千里之外
原创：12篇约瑟夫问题的数学解法理解
转载了一个，在下面。还有维基百科中文版给出的K=2情况理解了。对于其他K，下面这个可能更好理解。
约瑟夫问题
现有的对约瑟夫问题的数学解法中 递推出的x'=(x+k) mod n 是怎么得到的~
22:18匿名&|&分类：&|&浏览210次
我有更好的答案
22:08|四级
将这些人从0到n编号，假设除去第k个人。
0, 1, 2, 3, ..., k-2, k-1, k, ..., n-1　　//original sequence (1)
0, 1, 2, 3, ..., k-2,
, k, ..., n-1　　//get rid of kth person (2)
k, k+1, ..., n-1,
..., k-2　　//rearrange the sequence (3)
..., n-k-1, n-k, n-k+1, ..., n-2　　//the n-1 person (4)
我们假设f(n)的值为n个人中最后存活的人的序号，则
注意到(2)式(3)式(4)式其实是同一个序列。
注意(1)式和(4)式，是同一个问题，不同的仅仅是人数。
对比(3)(4)两式，可以看出(3)中的编号x'与(4)中的编号x对应关系即为x'=(x+k) mod n
&百度百科给出了k=3的一个例子的数学解法。没看懂
维基百科的解法
约瑟夫斯问题[]
维基百科，自由的百科全书
约瑟夫斯问题（有时也称为约瑟夫斯置换），是一个出现在和中的问题。在计算机的算法中，类似问题又称为约瑟夫环。
有个囚犯站成一个，准备处决。首先从一个人开始，越过个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。
问题是，给定了和，一开始要站在什么地方才能避免被处决？
这个问题是以命名的，它是的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。
我们将明确解出时的问题。对于的情况，我们在下面给出一个一般的解法。
设为一开始有个人时，生还者的位置。走了一圈以后，所有偶数号码的人被杀。再走第二圈，则新的第二、第四、……个人被杀，等等；就像没有第一圈一样。如果一开始有偶数个人，则第二圈时位置为的人一开始在第个位置。因此位置为的人开始时的位置为。这便给出了以下的递推公式：
如果一开始有奇数个人，则走了一圈以后，最终是号码为1的人被杀。于是同样地，再走第二圈时，新的第二、第四、……个人被杀，等等。在这种情况下，位置为的人原先位置为。这便给出了以下的递推公式：
如果我们把和的值列成表，我们可以看出一个规律：
从中可以看出，是一个递增的奇数数列，每当n是2的幂时，便重新从开始。因此，如果我们选择m和l，使得且，那么。显然，表格中的值满足这个方程。我们用数学归纳法给出一个证明。
定理：如果且，则。
证明：对应用。的情况显然成立。我们分别考虑是偶数和是奇数的情况。
如果是偶数，则我们选择和，使得，且。注意。我们有，其中第二个等式从归纳假设推出。
如果是奇数，则我们选择和，使得，且。注意。我们有，其中第二个等式从归纳假设推出。证毕。
答案的最漂亮的形式，与的二进制表示有关：把的第一位移动到最后，便得到。如果的二进制表示为，则。这可以通过把表示为来证明。
在一般情况下，这个问题的最简单的解决方法是使用。利用这种方法，我们可以得到以下的递推公式：
如果考虑生还者的号码从到是怎样变化的，则这个公式是明显的。这种方法的是，但对于较小的和较大的，有另外一种方法，这种方法也用到了动态规划，但运行时间为。它是基于把杀掉第k、2k、……、2个人视为一个步骤，然后把号码改变。
&The War of the Jews
参考文献[]
,&,&, and&.&, Second Edition. MIT Press and McGraw-Hill,
2001.&. Chapter 14: Augmenting Data Structures,
外部链接[]
上的（Java
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:& k& k+1& k+2& ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。现在我们把他们的编号做一下转换：k&&&& --& 0k+1&& --& 1k+2&& --& 2......k-2&& --& n-2k-1&& --& n-1解x' & &----& 解为x注意&x’就是最终的解&变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！下面举例说明：假设现在是6个人（编号从0到5）报数，报到（2-1）的退出，即&m=2&。那么第一次编号为1的人退出圈子，从他之后的人开始算起，序列变为2,3,4,5,0，即问题变成了这5个人报数的问题，将序号做一下转换：2 --&03&--&14&--&25&--&30&--&4现在假设x为0,1,2,3,4的解，x'设为那么原问题的解（这里注意，2,3,4,5,0的解就是0,1,2,3,4,5的解，因为1出去了，结果还是一个），根据观察发现，x与x'关系为x'=(x+m)%n，因此只要求出x，就可以求x'。x怎么求出呢？继续推导吧。0,1,2,3,4,，同样是第二个1出列，变为（2,3,4,0），转换下为2 --&03 --&14 --&20 --&3很简单，同样的道理，公式又出来了，x=(x''+m)%5，这里变成5了。即求n-1个人的问题就是找出n-2的人的解，n-2就是要找出n-3，等等因此，就可以回去看上面的推导过程了。好了，思路出来了，下面写递推公式：令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]递推公式f[1]=0;f[i]=(f[i-1]+m)%i;& (i&1)有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：&1&#include&&stdio.h&&2&int&main()&3&{&4&&&&&int&n,&m,&i,&s&=&0;&5&&&&&printf&("N&M&=&");&6&&&&&scanf("%d%d",&&n,&&m);&7&&&&&for&(i&=&2;&i&&=&n;&i++)&8&&&&&{&9&&&&&&&&&s&=&(s&+&m)&%&i;10&&&&&}11&&&&&printf&("\nThe&winner&is&%d\n",&s+1);12&}这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。相比之下，解法二的优越性不言而喻，同时说明数学确实很重要。在问题的基础上再演变一下，如果是个人编号 先去掉第 个数然后从 个开始报 报到 的退出剩下的人继续从 开始报数求胜利者的编号这样的话，其实和原题基本解法是一样的，把去掉第m个数之后第m+1个数看成第一个就可以了，所以需要转换一下，于是程序为：
阅读(9612)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'约瑟夫环问题的简单解法（数学公式法）（加个人润色，感谢原作者）',
blogAbstract:'关于约瑟夫环问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:8,
publishTime:9,
permalink:'blog/static/',
commentCount:3,
mainCommentCount:2,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'0',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}一个“四岛三桥”问题的四种解法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
一个“四岛三桥”问题的四种解法
上传于||暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
你可能喜欢}