java数据结构题之约瑟夫问题

约瑟夫问题:转载自    约瑟夫问题

据说着名犹太历史/数学家约瑟夫(Josephus)有过以下的故事:在罗马人占领乔塔帕特後,40个犹太士兵与约瑟夫躲到一个洞中,眼见脱逃无望,一群人决定集体自杀,约瑟夫建议自杀方式,41个人排成圆圈,由第1个人开始报数,每报数到5的人就必须自杀,然後由下一个重新报数,直到所有人都自杀身亡为止。如果你是约瑟夫,你应该在哪个位置才能活下来(最后只剩下你)?

我的答案:

package p1;

import java.util.LinkedList;
import java.util.List;

public class KillSelf {
	//构造链式列表,用来模拟人。
	private static List<String> list = new LinkedList<String>();
	//记忆自杀那个人前后的人集合有序子列表
	private static List<String> listBefore,listAfter;
	//自杀那个人的编号从1开始
	private static String killedNum = null;
	private static  int KILL_INDEX = 4;
	//记录自杀的总人数
	private static int sum = 0;
	public static void main(String[] args) {

		//记住每个从最开始的编号
		for(int i = 1;i <= 41;i++)
		{
			list.add(i+"");
		}
		//其实自杀的过程,是一个循环的过程,所以用循环来解决。
		while(true)
		{
			//获取自杀位置前后的子集
			if(list.size()>=5)	//当人数大于等于5个人时
			{
				listBefore = new LinkedList<String>(list.subList(0, KILL_INDEX));	//不能直接用subList的返回值,要包装一下
				listAfter = new LinkedList<String>(list.subList(KILL_INDEX+1, list.size()));
			}else if(list.size() > 1 && list.size() < 5)		//当人数多于1个人但是少于5个人时
			{
				KILL_INDEX = 5%list.size()-1;	//这个判断很巧妙
				if(KILL_INDEX > 0 && KILL_INDEX <list.size()-1)
				{
					listBefore = new LinkedList<String>(list.subList(0, KILL_INDEX));	//不能直接用subList的返回值,要包装一下
					listAfter = new LinkedList<String>(list.subList(KILL_INDEX+1, list.size()));
				}else if(KILL_INDEX == 0)
				{
					listBefore.clear();
					listAfter = new LinkedList<String>(list.subList(KILL_INDEX+1, list.size()));
				}else if(KILL_INDEX == list.size()-1)
				{
					listBefore = new LinkedList<String>(list.subList(0, KILL_INDEX));
					listAfter.clear();
				}

			}else
				break;
			//将子集的后与前连接起来,更新总的集合
			killedNum = list.get(KILL_INDEX);
			sum++;
			System.out.println("编号" + killedNum + "已自杀!-----自杀总人数达" + sum);
			//更新list
			list.clear();
			list.addAll(listAfter);
			list.addAll(listBefore);
			System.out.println("剩余人员编号:"+list);
			System.out.println("");
		}
		System.out.println("");
		System.out.println("结论:处在"+list.get(0)+"号才不会自杀");
	}
}

但是网上的帖子,几行代码就解决问题了,这就是算法的魅力!

时间: 06-03

java数据结构题之约瑟夫问题的相关文章

Java数据结构之二叉搜索树

Java数据结构之二叉搜索树 1.二叉搜索树组成 二叉搜索树又称为二叉排序树,它或者是一颗空树,或者是一颗具有如下特性的非空二叉树,需要满足一下三个条件: (1)若它的左子树非空,则左子树上所有结点的关键字均小于根结点的关键字: (2)若它的右子树非空,则右子树上所有结点的关键字均大于(可以等于)根结点的关键字. (3)左子树右子树本身又各是一颗二叉搜索树 在算法描述中,均以结点值的比较来代表其关键字的比较,因为若结点的值为类类型时,该类必须实现系统提供的java.lang.comparable

Java数据结构和算法之递归

四.递归 递归是函数调用自身的一种特殊的编程技术,其应用主要在以下几个方面:   阶乘 在java当中的基本形式是: Public  void  mothed(int n){//当满足某条件时: Mothed(n‐1): } 递归二分查找 Java二分查找实现,欢迎大家提出交流意见.  /** *名称:BinarySearch *功能:实现了折半查找(二分查找)的递归和非递归算法. *说明: *     1.要求所查找的数组已有序,并且其中元素已实现Comparable<T>接口,如Integ

树和二叉树-第6章-《数据结构题集》习题解析-严蔚敏吴伟民版

习题集解析部分 第6章 树和二叉树 ——<数据结构题集>-严蔚敏.吴伟民版        源码使用说明  链接??? <数据结构-C语言版>(严蔚敏,吴伟民版)课本源码+习题集解析使用说明        课本源码合辑  链接??? <数据结构>课本源码合辑        习题集全解析  链接??? <数据结构题集>习题解析合辑       相关测试数据下载  链接? 数据包       本习题文档的存放目录:数据结构\▼配套习题解析\▼06 树和二叉树  

Java数据结构和算法(二)——数组

数组的用处是什么呢?--当你需要将30个数进行大小排列的时候,用数组这样的数据结构存储是个很好的选择,当你是一个班的班主任的时候,每次要记录那些学生的缺勤次数的时候,数组也是很有用.数组可以进行插入,删除,查找等. 1)创建和内存分配 Java中有两种数据类型,基本类型和对象类型,也有人称为引用类型,Java中把数组当成对象,创建数组时使用new操作符. int array[] = new int[10]; 既然是对象,那么array便是数组的一个引用,根据Java编程思想(一) -- 一切都是

一道很有意思的java线程题

这几天看结城浩的<java多线程设计模式>,跟着做一些习题,有几道题目很有意思,记录下自己的体会. 首先是题目(在原书212页,书尾有解答): public class Main { public static void main(String[] args) { try { Blackhole.enter(new Object()); } catch (InterruptedException e) { e.printStackTrace(); } } } public class Blac

Java数据结构与算法之集合

线性表.链表.哈希表是常用的数据结构,在进行Java开发时,SDK已经为我们提供了一系列相应的类来实现基本的数据结构.这些类均在java.util包中. 一.Collection接口 Collection是最基本的集合接口,一个Collection代表一组Object.一些Collection允许相同元素而另一些不行.一些能排序而另一些不行.Java  SDK不提供直接继承自Collection的类,Java  SDK提供的类都是继承自Collection的"子接口"如List和Set

Java数据结构和算法之栈与队列

二.栈与队列 1.栈的定义 栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表. (1)通常称插入.删除的这一端为栈顶(Top),另一端称为栈底(Bottom). (2)当表中没有元素时称为空栈. (3)栈为后进先出(Last In First Out)的线性表,简称为LIFO表. 栈的修改是按后进先出的原则进行. 每次删除(退栈)的总是当前栈中"最新"的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除. 图1 [示例]元素是以a1,a2,-,a

Java数据结构和算法之数组与简单排序

一.数组于简单排序 数组 数组(array)是相同类型变量的集合,可以使用共同的名字引用它.数组可被定义为任何类型,可以是一维或多维.数组中的一个特别要素是通过下标来访问它.数组提供了一种将有联系的信息分组的便利方法. 一维数组 一维数组(one‐dimensional array )实质上是相同类型变量列表.要创建一个数组,你必须首先定义数组变量所需的类型.通用的一维数组的声明格式是: type var‐name[ ]; 获得一个数组需要2步: 第一步,你必须定义变量所需的类型. 第二步,你必

Java数据结构和算法之链表

三.链表 链结点 在链表中,每个数据项都被包含在'点"中,一个点是某个类的对象,这个类可认叫做LINK.因为一个链表中有许多类似的链结点,所以有必要用一个不同于链表的类来表达链结点.每个LINK对象中都包含一个对下一个点引用的字段(通常叫做next)但是本身的对象中有一个字段指向对第一个链结点的引用. 单链表 用一组地址任意的存储单元存放线性表中的数据元素. 以元素(数据元素的映象)  + 指针(指示后继元素存储位置)  = 结点(表示数据元素 或 数据元素的映象) 以"结点的序列&q

Java数据结构和算法之哈希表

五.哈希表 一般的线性表.树中,记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系,在结构中查找记录时需进行一系列和关键字的比较.这一类查找方法建立在"比较"的基础上,查找的效率与比较次数密切相关.理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应.因而查找时,只需根据这个对应关系f找到给定值K的像f(K).若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上,由此不需