大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
//看了帖子后认为有趣就实现了一把递归的约瑟夫算法
package test; /** * 500个小孩围成一圈,从第一个開始报数:1,2,3,1,2,3,1,2,3,……每次报3的小孩退出 问最后剩下的那个小孩,在曾经500人里是第几个??? */ public class Test { /** * 约瑟夫标准循环非递归解法 * @param n * @param m * @return */ public static int f2(int n, int m){ int index = 0; for (int i = 2; i <= n; i++) { index = (index + m) % i; } return index +1; } /** * 约瑟夫递归算法 * @param n * @param m * @return 返回的结果+1 = 终于结果 */ public static int f(int n,int m){ int t = 0; if(n==1){ return t; }else{ t = ( f(n-1, m) + m)%n; } return t; } public static void main(String[] args) { // int n = 500; int m = 3; //约瑟夫标准循环非递归解法 System.out.println(f2(n, m));//此方法来自帖子 /* (函数)index表示(变量)n个人玩游戏报(常量)m退出最后胜利者的编号.则有递推公式: index(1) = 0; index(n) = (index(n-1) + m)%n; (n>1) 这个公式不是仅仅考虑一种场景得出的结果,而是抽象出普遍的n得出的结论, */ /* *f(1) = 0;//第0个 *f(2) = 1;//第1个 *f(3) = 1;//第2个 * */ //參考上面的提示写了下约瑟夫的递归算法 System.out.println(f(n, m)+1); } }
今天看到一个LinkedList版本号的,測试了,结果一样,补充上:
public static int removeNM(int n, int m) { LinkedList ll = new LinkedList(); for (int i = 0; i < n; i++) ll.add(new Integer(i + 1)); int removed = -1; while (ll.size() > 1) { removed = (removed + m) % ll.size(); System.out.println("出列:"+(ll.get(removed))); ll.remove(removed--); } return ((Integer) ll.get(0)).intValue(); }
打印结果:
436
436
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118457.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...