约瑟夫算法(数学分析法)

约瑟夫算法(数学分析法)

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

//看了帖子后认为有趣就实现了一把递归的约瑟夫算法

  

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账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号