经典算法(Java)

标签: 约瑟夫环问题  魔术师发牌  数据结构与算法

约瑟夫环问题

问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,报到m的人出圈;如此往复,直到所有人出圈。(模拟此过程,输出出圈的人的序号)

解析:根据题目要求,假设我们现在20个人,数到3的人出圈,可以看出这是一个单向循环链表。我们可以先来看看有什么规律,如图所示,我们可以设置一个临时结点p,让p指向出圈元素的前驱。从1数到3的时候,p就得前进一步指向2的位置,接下来从4接着数,数三下到6的位置,此时p还是得前进一步到5的位置,以此类推。。。我们可以用循环解决这个问题。

那我们在这个过程当中有没有特殊情况呢?当然是有的,就比如图中现在这种情况,当删除1的时候,我们发现1是表头,删掉了就得移动head到2的位置。同样,当我们删除的是尾后,rear就得往后移动(假如删掉20,rear后移指向19)。还有一种情况,当表中只有一个元素的时候,我们直接让head=null、rear=null即可。

代码实现:

 

    /**
	 * 约瑟夫问题
	 * @param number 总数
	 * @param step 步数
	 * @return 出圈顺序
	 * 
	 *	1.先判断输入的参数是否合法
	 *	2.在将1~number的数加入链表当中
	 *	3.从1数开始,数三下到3的位置,p指到2的位置,p移动了一步
	 *	    接着从4开始数三下到6的位置,p指向5的位置,p移动了一步,循环条件就是step-2
	 *	4.删除元素是有4种情况:
	 *	    表中只剩一个元素时
	 *	    删除元素是head时
	 *    删除元素是rear时
	 *    删除元素是中间元素
	 *  5.将出圈顺序存入LinkedList,将其输出
	 */
	public LinkedList<Integer> josephusLoop(int number,int step){
		//判断输入的参数是否合法
		if(number<=0||step<=0){
			throw new IllegalArgumentException("参数不合法");
		}
		clear();//清空链表
		//将1~number的数加入链表当中
		for (int i = 1; i <=number; i++) {
			addLast((E)new Integer(i));
		}
		//出圈顺序用LinkedList存储
		LinkedList<Integer> list = new LinkedList<Integer>();
		Node p =head;//临时结点,用来遍历,始终指向出圈元素的前驱
		while(true){
			//临时结点移动的步数
			for (int i = 0; i < step-2; i++) {
				p=p.next;
			}
			Node del=p.next;
			list.addLast((Integer)del.data);//将删除的元素加入LinkedList中
			if(size==1){ //链表中只有一个元素
				size--;
				head=null;
				rear=null;
				break;
			}
			if(del==head){//当删除的元素是头时
				head=head.next;
				rear.next = head;
				size--;
				p=head;
			}else if(del==rear){  //当删除的元素是尾时
				
				p.next=rear.next;
				rear=p;
				size--;
				p=head;
			}else{
				p.next=del.next;
				del.next=null;
				del=null;
				size--;
				p=p.next;
			}
		}
		return list;
	}


魔术师发牌

 问题描述:魔术师手里一共有13张牌,全是黑桃,1~13. 
 魔术师需要实现一个魔术:这是十三张牌全部放在桌面上(正面向下), 
 第一次摸出第一张,是1,翻过来放在桌面上。 
 第二次摸出从上往下数第二张,是2,翻过来 放在桌面上,(第一张放在最下面去,等会儿再摸), 
 第三次摸出从上往下数第三张,是3,翻过来放在桌面上,(第一张和第二张 放在最下面去,等会儿再摸) 
 以此类推 最后一张就是13 

解析:根据题意,我们发现这也是一个单向循环列表的问题。我们可以先定义一个长度为13的链表,按发牌的顺序往进存放。当存5时,我们开始数到第五张,此时数到表尾我们让它再从表头开始,注意只能数没有存牌的格子,所以5的位置就在2的后面。以此类推。。。

我们可以总结出,当我们数牌时,如果遇到格子里有牌就选择跳过。

代码实现:

    /**
	 * 魔术师发牌
	 * 1.先定义一个长度为13,都存放0的链表
	 * 2.进行读牌,读一个存进去一个
	 * 3.注意当遇到格子里有牌时,要跳过。
	 */
	public void magicPoker(){
		clear();//清空表
		//表中13个格子都存0
		for (int i = 0; i < 13; i++) {
			addLast((E) new Integer(0));
		}
		Integer pokerNumber=1; //放入的牌,从1开始
		Node p =rear;
		while(true){
			for (int i = 0; i < pokerNumber;) {
				p=p.next;
				if(p.data.equals(0)){ //如果格子中元素为0,说明可以存元素,否则跳过
					 i++;
				}
			}
			p.data=(E) pokerNumber;  //将元素存入表中
			pokerNumber++; //牌数+1
			if(pokerNumber==14){ //如果牌数为14时,说明13张牌都已存入,循环结束。
				break;
			}
		}
		System.out.println(this);
	}

 

版权声明:本文为qq_43137918原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43137918/article/details/100978850

智能推荐

ActiveMQ学习4-ActiveMQ的安全机制和集群模式

ActiveMQ的安全机制和集群模式 20 ActiveMQ安全机制 20.1 Web 控制台安全 20.2 消息服务器Broker安全 21 ActiveMQ主从集群 21.1 使用集群的重要性 20.2 主从集群的方式 20.2.1 shared filesystem Master-Slave方式主从集群 20.2.2 shared database Master-Slave方式主从集群 20...

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

猜你喜欢

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...