首页 > 代码库 > 约瑟夫环问题
约瑟夫环问题
题目描述约瑟夫问题是一个非常著名的趣题，即由n个人坐成一圈，按顺时针由1开始给他们编号。然后由第一个人开始报数，数到m的人出局。现在需要求的是最后一个出局的人的编号。 给定两个int n和m，代表游戏的人数。请返回最后一个出局的人的编号。保证n和m小于等于1000。 测试样例： 5 3 返回：4 |
据说著名犹太历史学家Josephus在罗马人占领了乔塔帕特之后，39个犹太人与Josephus及他的朋友躲到山洞，39个犹太人决定宁愿死都不要被敌人抓到，于是决定了一种自杀的方式，41个人排成一个圈子，
由第一个人开始报数，报到3的人就自杀。然后再由下一个人开始重新报1，报到3的再自杀,这样再一直下去，直到最后一个人，那个人就可以自己决定自己的命运。这就是著名的约瑟夫问题。
那么怎样才能决定自己的命运呢？就是一开始41人时就要占据有利的位置。那么哪个位置是有利的位置？ 不说了，直接上代码!
此方法比较字节用数组模拟环形链表，在一个一个删除节点：
class Joseph {public: int getResult(int n, int m) { vector<int> a(n); int cur = 0; int pre = n-1; int count = 0; int allPeopleCount = n; int i; for(i = 0; i < n-1;i++){ a[i] = i+1; } while(allPeopleCount){ if(++count >= m) { allPeopleCount--; count = 0; a[pre] = a[cur]; //类似指针 } else pre = cur; cur = a[cur]; } return cur+1; }};
另一种方法就是找出递归的关系式我们已知递归的出口是getResult(1,m) = 1; m代表报到那个数字自杀的人
通过推到我们可以知道 getResult(i,m) = (getResult(i-1,m)+m-1)%i+1; 这是用递归就很简单了。
//#define a[i] (a[i-1]+m-1)%i+1 class Joseph {public: int getResult(int n, int m) { if(n == 1) return 1; return (getResult(n-1,m)+m-1)%n + 1; } };
约瑟夫环问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。