问题：1~n个人围成一圈，从1开始报数，每次数到m这个人就出列，问最后剩下的是几号？
做法：递归。
假设剩下的是f(n)号，那么要找f(n)与f(n-1)等的关系，又因为这个游戏是过程式的，可以发现：n个人，出列一个之后，就是n-1个人，我们把编号改一下的话，就f(n-1)这个问题完全一样了：
1 2 3 ... (m) m+1 m+2 ... n
... ( ) 1 2 .....
这个n-1的问题里面， 每个编号都是原来编号 + m，再mod n。所以，要求的那个人的编号也是这个：
f(n) = (f(n-1) + m)%n
约瑟夫环问题约瑟夫环描述：约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围...
约瑟夫环
题目：100名学生围成一个圈， 编号从1到100，从第一名学生开始报数，从1-9报数 每报出9就退出，直到所有学生...
问题：1~n个人围成一圈，从1开始报数，每次数到m这个人就出列，问最后剩下的是几号？ 做法：递归。 假设剩下的是f...
解法一 用一个list模拟删除过程 解法二 数学公式，推到过程还没看懂
之前去面试的时候遇到这个问题，作为一只算法渣渣，自然带着恐惧的心情，然后自己瞎捣鼓了好长时间终于拼凑出来了一个很菜...
复习一下关于约瑟夫环的实现原理： 如果用Ｃ来写的话，也会有许多的方法，比如１：采用链表（双向链表）２：递归３：队列...
公式法循环 公式法递归 链表法
本文标题：约瑟夫环
本文链接：https://www.haomeiwen.com/subject/ktnhkxtx.html
网友评论