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

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

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

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

  

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)


相关推荐

  • leetcode题目分类_最长前缀匹配例题

    leetcode题目分类_最长前缀匹配例题原题链接编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 “”。示例 1:输入:strs = [“flower”,”flow”,”flight”]输出:”fl”示例 2:输入:strs = [“dog”,”racecar”,”car”]输出:””解释:输入不存在公共前缀。 提示:0 <= strs.length <= 2000 <= strs[i].length <= 200strs[i] 仅由小写英文字母组成题解分

  • oracle分页查询的三种常见方式

    oracle分页查询的三种常见方式oracle分页查询的三种常见方式分页写法:–分页查询一select*from(selectrownumr,e1.*from(select*fromemporderbysal)e1whererownum&lt;=8)wherer&gt;=5;–分页查询二selecte1.*from…

  • bigtable是什么_BigTable

    bigtable是什么_BigTableBigtable是一个用来管理结构化数据的分布式存储系统,具有很好的伸缩性,能够在几千台应用服务器上处理PB数量级数据。谷歌有许多项目都把数据存储在Bigtable中,包括webindexing,G

  • Django(23)Django限制请求装饰器

    Django(23)Django限制请求装饰器前言有时候,我们想要限制访问的请求方法,比如我们希望用户只能通过get方式请求,post不允许,那么我们可以采用装饰器的方式,django已经为我们提供了内置的装饰器限制请求装饰器Django内

  • TCP和UDP协议的区别_朋友关系

    TCP和UDP协议的区别_朋友关系在解释两者之间的关系之前,我们必须从宏观的角度了解互联网的整个交互模型。因为当了解互联网在大体上是如何运作时,我们才能了解HTTP和TCP存在的意义,包括他们所要解决的问题是。 (此图来自Udacity的网络协议教程)互联网的模型被分为4层,从上至下每一层都依赖其底层协议。换言之,Application(应用层)的协议操作成功的前提是Transport(运输层)的存在。没有运输层就没有应…

  • JAVA面试题库_jpa面试题

    JAVA面试题库_jpa面试题Shiro可以做哪些工作?Shiro可以帮助我们完成:认证、授权、加密、会话管理、与Web集成、缓存等shiro有哪些组件?Authentication:身份认证/登录,验证用户是不是拥有相应的身份;Authorization:授权,即权限验证,验证某个已认证的用户是否拥有某个权限;即判断用户是否能做事情,常见的如:验证某个用户是否拥有某个角色。或者细粒度的验证某个用户对某个资源是否具有某个权限;SessionManager:会话管理,即用户登录后就是一次会话,在没有退出之前,它的所有信息都在会

    2022年10月14日

发表回复

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

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