`
datoplay
  • 浏览: 1605533 次
文章分类
社区版块
存档分类
最新评论

约瑟夫问题

 
阅读更多

约瑟夫问题大意就是给你n个人,编号为1-n。从第一个人开始报数,报到m时候,第m个人出列。然后下个人从1开始报数,逢m出列。问最后出列的人的编号。


刚开始用的是循环链表,纯模拟做法。发现当n很大时,铁定TLE。所以上网搜了下,发现有数学方法解决这个问题。

思路就是递推,发现子问题,然后由子问题的解推总问题的解。

公式就是:

f(1) = 0;

f(i) = (f(i - 1) + m) % i; (i > 1)

公式的含义我解释一下:

f(1)代表就一个人玩游戏,所以不需要踢人,第一个人就是获胜者,但为什么是0不是1本身呢?接着看。。。。。

f(i)代表剩i个人时要踢的人,f(i - 1)代表剩i - 1时踢掉的人,从这个人的下一个即(f(i - 1) + 1)开始,数m个人,但是从(f(i - 1) + 1)开始时,(f(i - 1) + 1)已经有一个人,所以下一次要踢掉的人就是(f(i - 1) + 1) + m - 1.。。这个应该可以理解。。。。那结果就是f(i - 1) + m。。因为可以把约瑟夫问题看成一个圈圈,所以取余是必要的,防止出界。加入n = 8, 那么要踢掉第10个人,其实就是踢掉 10 mod 8 = 2,第二个人。。。。

然后比较容易错的地方就是刚才那个问题,为什么f(1)不是1而是0呢?因为f(i)代表剩i个人时要踢的人,而1个人玩的时候就不需要踢人。同理,下面f(i)踢掉了一个人,这样,到最后,一共踢掉n-1个人,这个游戏就结束了,获胜者就是踢掉最后一个人之后剩下的那个。因为踢掉一个n就-1,所以最后剩2个人,踢掉一个之后需要+1 mod n(总人数)。这样,就可以求出获胜者。

结果就是:

1个人时候,结果为 f(1) + 1.

大于一个人的时候,结果为f(n) + 1;

至此,这个问题就解决了。。。。。。。。大笑

代码如下:



分享到:
评论

相关推荐

    数据结构 约瑟夫问题

    用循环单向链表解决约瑟夫问题 原题: 设有n个人站成一圈,每个人持有一个密码(正整数)。现从第t个人开始,按顺时针方向“1,2,3,4,…”循环报数,数到m1(第t个人所持密码)的人出列,然后从出列者的下一个人重新...

    数据结构中双向约瑟夫问题

    已知n个人(不妨分别以编号1,2,3,…,n 代表 )围坐在一张圆桌周围,首先从编号为 k 的人从1开始顺时针报数,1, 2, 3, ...,记下顺时针数到 m 的那个人,同时从编号为 k ...数据结构中经典的双向约瑟夫问题c语言代码

    约瑟夫问题代码,约瑟夫问题代码

    约瑟夫问题代码,约瑟夫问题代码

    java链表实现约瑟夫问题

    约瑟夫问题,通过类实现的链表,并加以改进,做成双向链表

    约瑟夫问题的两种求解方法

    约瑟夫问题的两种求解方法,顺序存储和链表

    约瑟夫问题(C++)

     约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的人的序号为5,4,6,2,3。最后剩下1号。  假定在圈子里前K个为好人,后K...

    约瑟夫问题的解答

    约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。 分析: (1)由于对于每个人只有死和活两种...

    约瑟夫问题C++做法

    用链表与循环完成约瑟夫问题 while (cin>>x>>y) { node *p, *q; //建立循环链表 for (i = 1; i ; i++) { if (i == 1) { list->head = new node; list->head->data = i; q = list->head; ...

    Josephus 约瑟夫问题(POJ)

    Josephus 约瑟夫问题(POJ)相关习题的源代码(1012,2359,1781,2244,3517,2939,2800)

    C++_循环链表实现约瑟夫问题

    C++_循环链表实现约瑟夫问题 vc2008 课堂作业!

    约瑟夫问题相关代码

    该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n个人围坐一圈,用链表中的每一个结点代表一个人和他所代表的序号。在输入初始序号m后,对该链表进行遍历,直到第m个结点,令该结点的序号值作为新的序号值,...

    利用循环链表实现约瑟夫问题的求解

    利用循环链表实现约瑟夫问题的求解。 约瑟夫问题如下:已知n个人(n>=1)围坐一圆桌周围,从1开始顺序编号。从序号为1的人开始报数,顺时针数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依...

    约瑟夫问题C语言 .

    约瑟夫问题C语言

    数据结构解决约瑟夫问题

    解决约瑟夫问题,数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构...

    stl 解决约瑟夫问题

    利用STL解决约瑟夫问题,可以接受数据的不同存储方式,比如vector ,list 等。

    约瑟夫问题循环链表实现.

    约瑟夫问题循环链表实现代码

    约瑟夫问题的由来和简介

    约瑟夫问题的来历 约瑟夫问题的一般形式: 约瑟夫问题的另外一个有名的例子: 猴子选大王 笔算解决约瑟夫问题

    约瑟夫问题java求解

    算法实现源程序java代码实现约瑟夫问题

Global site tag (gtag.js) - Google Analytics