约瑟夫问题1
题目描述
约瑟夫问题是一个非常著名的趣题,即由n个人坐成一圈,按顺时针由1开始给他们编号。然后由第一个人开始报数,数到m的人出局。现在需要求的是最后一个出局的人的编号。
给定两个int n和m,代表游戏的人数。请返回最后一个出局的人的编号。保证n和m小于等于1000。
测试样例:
5 3
返回:4
主要思路
参考链接:https://blog.nowcoder.net/n/81a858b422804183a1a51dbfd4084ebc
代码如下
//递归实现 class Joseph { public: int getResult(int n, int m) { if(n < 1 || m < 1){ return 0; } return lastInCycle(n, m) + 1; } int lastInCycle(int n, int m){ if(n == 1){ return 0; } return (lastInCycle(n - 1, m) + m) % n; } }; //迭代逆推实现 public int getResult(int n, int m) { // write code here /* * 存在递推公式: * f(n,m)表示n个人报数m的离开,最后留下来的人的初始号码 * f(n,m) = (f(n-1,m)+m)%n; */ if(n < 1 || m < 1){ return -1; } int last = 0; if(n == 1){ return last;//最后一轮出局的人肯定是最后轮的第0个,要找到其初始号码 } for(int i = 2; i <= n; i++){ last = (last + m) % i;//最后出来的人在倒数第i轮的号码是last } return last+1;//注意编号是1-n编号的,而算法是从0~n-1排序的 }
约瑟夫问题2
题目描述
约瑟夫问题是一个著名的趣题。这里我们稍稍修改一下规则。有n个人站成一列。并从头到尾给他们编号,第一个人编号为1。然后从头开始报数,第一轮依次报1,2,1,2…然后报到2的人出局。接着第二轮再从上一轮最后一个报数的人开始依次报1,2,3,1,2,3…报到2,3的人出局。以此类推直到剩下以后一个人。现在需要求的即是这个人的编号。
给定一个int n,代表游戏的人数。请返回最后一个人的编号
测试样例:
5
返回:5
主要思路一(数学推导实现)
比较难以想到
数学推导得出:参考链接
代码如下
//递归实现 class Joseph { public: int getResult(int n) { // write code here if(n < 1){ return 0; } int result = lastInCycle(n, 2); return result + 1; } int lastInCycle(int n, int m){ if(n <= m){ return 0; } int temp = n % m == 0 ? n / m : n / m + 1; return (lastInCycle(temp, m + 1) + temp - 1) % temp * m; } };
主要思路二(链表实现)
链表实现:参考链接
解题思路例子:
- 由于涉及到频繁的删除操作,故数据结构应该选择链表,这里选择LinkedList,其底层实现是循环双链表。
- 每一轮报数完毕之后,将链表尾部节点移动到链表首部,开始新一轮的报数。
- 链表中仅剩一个节点,程序结束。
- 举个例子:假设n = 24,第一个人编号为1。
(1)第一轮:依次报1,2,1,2…然后报到2的人出局,则第一轮过后未出局的编号为1、3、5、7、9、11、13、15、17、19、21、23;
(2)第二轮:从上一轮最后一个报数的人开始依次报1,2,3,1,2,3…报到2,3的人出局。我这里做的处理是,先将上一轮最后一个报数的编号移动到最前面,即23、1、3、5、7、9、11、13、15、17、19、21;然后开始第二轮报数,未出局的编号为23、5、11、17;
(3)第三轮:从上一轮最后一个报数的人开始依次报1,2,3,4,1,2,3,4…报到2,3,4的人出局。同样,我这里做的处理是,先将上一轮最后一个报数的编号移动到最前面,即17、23、5、11;然后开始第三轮报数,未出局的编号为17,此时链表中仅剩一个节点,故程序结束。
代码如下
/** * 核心数据结构:双链表 */ public int getResult(int n) { if (n < 1) return -1; LinkedList<Integer> list = new LinkedList<Integer>(); int round = 2, i, curr = 0; for (i = 1; i <= n; i++) { list.add(i); } while (list.size() > 1) { i = 0; while (list.size() > 1 && i < list.size()) { //当还有大于1个人存活的时候游戏继续 curr = (curr + 1) % round; //每一轮的round都会+1,从2开始递增 if (curr != 1) { //筛选数据 list.remove(i); } else { i++; } } round++; // 下一轮的最大报数 curr = 0; // 表示还未开始报数 if (list.size() > 1) {// 将最后报数的元素移动到链表首部,即确保每次报数从链表首部开始。 int last = list.removeLast(); list.addFirst(last); } } return list.pop();// 返回最后一个元素 }