约瑟夫环问题链表实现(Java)

约瑟夫环问题链表实现(Java)面试中可能经常会遇到约瑟夫环问题,逻辑上很简单,就是看怎么实现了,一般而言,最简单最直观的就是利用链表,然后构建一个循环结构,正好是环,最后计算出结果。遍历环形链表会是一个无限循环,如果链表中的数据逐渐减少,不控制终究会一个不剩,这又不满足我们问题的求解,因此我们需要定义出循环结束的条件,按照约瑟夫环的规则,只剩下一个的时候就结束,在环形链表结构中,那就是结点本身的下一个节点就…

大家好,又见面了,我是你们的朋友全栈君。

    面试中可能经常会遇到约瑟夫环问题,逻辑上很简单,就是看怎么实现了,一般而言,最简单最直观的就是利用链表,然后构建一个循环结构,正好是环,最后计算出结果。

    遍历环形链表会是一个无限循环,如果链表中的数据逐渐减少,不控制终究会一个不剩,这又不满足我们问题的求解,因此我们需要定义出循环结束的条件,按照约瑟夫环的规则,只剩下一个的时候就结束,在环形链表结构中,那就是结点本身的下一个节点就是它自己。这样就可以结束遍历了。最后打印出剩下的结点,问题解决。

这里给出Java版本的实现:

package com.xxx.algorithm.wh;
//约瑟夫环java实现
//约瑟夫环问题的起源来自犹太历史学家约瑟夫和他的朋友以及39其余的犹太人,总共41人为了躲避敌人,藏在一个山洞中,
//39个犹太人决定宁愿死也不被敌人抓到,于是决定自杀,所有人排成一个圈,由第一个人开始报数,每当数到3,就自杀。
//这个游戏接着从自杀的位置开始,还是从1数到3。依次类推,约瑟夫将朋友和自己安排在了16和31的位置,最后顺利逃过了
//自杀这一劫,因为最后就剩他一个人了。
public class JosefCircleMain {
	
	public static void count(int n){
		//数到3出局,中间间隔两个人
		int k = 3;
		//头结点不存储数据
		Node head = new Node();
		Node cur = head;
		//循环构造这个链表
		for(int i=1;i<=n;i++){
			Node node = new Node(i);
			cur.next = node;
			cur = node;
		}
		//链表有数据的部分首尾相连形成一个环。
		cur.next = head.next;
		//统计开始的时候,刨去头结点,然后从第一个有数据的结点开始报数
		Node p = head.next;
		//循环退出的条件是最后只剩一个结点,也就是这个结点的下一个结点是它本身
		while(p.next!=p){
			//正常报数的遍历逻辑
			for(int i=1;i<k-1;i++){
				p = p.next;
			}
			//当数到3的时候,出局
			System.out.print(p.next.data+"->");
			p.next = p.next.next;
			p = p.next;
		}
		//最后剩下的一个结点
		System.out.println("(left:"+p.data+")");
	}

	public static void main(String[] args) {
		//以4个人为例,1234 : 最先出局的是3,然后剩下412,接着2出局,剩下41,这时候就是4出局,最后剩下1.
		count(4);
		//41个人为例,就是约瑟夫环的本身了,最后剩下的是31
		count(41);
	}

}

class Node{
	int data;
	Node next;
	public Node(){}
	public Node(int data){this.data = data;}
}

    一般的链表,如果没有特别的说明,头结点是有数据的,但是这里情况比较特殊,我们构建了一个头结点没有数据的空节点,然后将链表的首尾相连,这个首其实也不是头结点,而是头结点的下一个结点,用图表示就是如下:

约瑟夫环问题链表实现(Java)

    首次遍历的时候,我们是从1开始的,所以代码中有这样的一句:

约瑟夫环问题链表实现(Java)

运行程序,打印结果:

3->2->4->(left:1)
3->6->9->12->15->18->21->24->27->30->33->36->39->1->5->10->14->19->23->28->32->37->41->7->13->20->26->34->40->8->17->29->38->11->25->2->22->4->35->16->(left:31)

打印结果既验证了只有4个结点的情况,也验证了约瑟夫环的本身的结论。 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136160.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 浅谈软件性能提升相关的概念

    浅谈软件性能提升相关的概念浅谈软件性能提升相关的概念原文链接为<Makingyourprogramrunfaster:thekeyconceptsofsoftwareperformance-Jo

  • linux下载文件命令sz_linux下载整个文件夹命令

    linux下载文件命令sz_linux下载整个文件夹命令wget是linux下一个从网络上自动下载文件的常用自由工具。它支持HTTP,HTTPS和FTP协议,可以使用HTTP代理。一般的使用方法是:wget+空格+参数+要下载文件的url路径,例如:1wget http://www.linuxsense.org/xxxx/xxx.tar.gz-c参数,这个也非常

  • SVN使用 IDEA集成SVN SVN简介 SVN使用详解 SVN学习之路

    SVN使用 IDEA集成SVN SVN简介 SVN使用详解 SVN学习之路文章目录SVN介绍与使用一、SVN引入1.SVM服务器搭建2.需要了解的关键词3.如何让系统共享信息,并且不互相干扰。4.SVN架构二、SVN的操作1.安装tortoisesSvn2.初始化拉去仓库3.提交4.拉取服务器上最新版本5.解决冲突三、Idea集成SVN3.1配置3.2关联服务器仓库SVN介绍与使用一、SVN引入SVN==Subversion它是一个自由/开源的集中式版本控制系统,一组文件存放在中心版本库,记录每一次文件和目录的修改,Subversion允许把数据

    2022年10月11日
  • 接口-DAO模式代码阅读及应用

    接口-DAO模式代码阅读及应用

  • excel右键不出菜单_哈希校验码下载

    excel右键不出菜单_哈希校验码下载推荐阅读:这套Github上40K+star学习笔记,可以帮你搞定95%以上的Java面试毫不夸张的说,这份SpringBoot学习指南能解决你遇到的98%的问题给跪了!这套万人期待的SQL成神之路PDF,终于开源了最近遇到这么一件事:我在官网下载软件安装包,准备安装的时候被提示说是有病毒,不让安装。当时我就纳闷了,这官网下载的文件怎么会有病毒呢?于是我找到官网标注的文件Hash…

  • sctp介绍「建议收藏」

    sctp介绍「建议收藏」SCTP介绍转自:http://www.ibm.com/developerworks/cn/linux/l-sctp/SCTP(STREAM CONTROL TRANSMISSION PROTOCOL 流控制传输协议)是IETF新定义的一个传输层transport layer协议(2000年)。是提供基于不可靠传输业务的协议之上的可靠的数据报传输协议。SCTP的设计用于通过IP网传输S

发表回复

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

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