java编程约瑟夫问题实例分析
一、简介
约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）
例子：
len个人围成一个圈，玩丢手绢游戏。从第k个人开始，从1开始数数，当数到m时，数m的人就退出圈子，当圈子只剩下一个人为止。
问题分析与算法设计
约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
题目中len个人围成一圈，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向第一个孩子的头节点，另一个为作为判断的节点temp（负责跑龙套）。
具体代码如下：
package demo11;
/**
* 约瑟夫问题， 化为丢手绢
*
* @author tianq 思路：建立一个Child类 一个循环列表类CyclLink
*/
public class demo11 {
public static void main(String[] args) {
CyclLink cyclink = new CyclLink();
cyclink.setLen(15);
cyclink.createLink();
cyclink.setK(2);
cyclink.setM(2);
cyclink.show();
cyclink.play();
}
}
// 先建立一个孩子类
class Child {
// 孩子的标识
int no;
Child nextChild;
// 指向下一个孩子
public Child(int no) {
// 构造函数给孩子一个id
this.no = no;
}
}
class CyclLink {
// 先定义一个指向链表第一个小孩的引用
// 指向第一个小孩的引用，不能动
Child firstChild = null;
Child temp = null;
int len = 0;
// 表示共有几个小孩
int k = 0;
//开始的孩子
int m = 0;
//数到几推出
// 设置m
public void setM(int m) {
this.m = m;
}
// 设置链表的大小
public void setLen(int len)
{
this.len = len;
}
// 设置从第几个人开始数数
public void setK(int k) {
this.k = k;
}
// 开始play
public void play() {
Child temp = this.firstChild;
// 1.先找到开始数数的人
for (int i = 1; i < k; i++) {
temp = temp.nextChild;
}
while (this.len != 1) {
// 2.数m下
for (int j = 1; j < m; j++) {
temp = temp.nextChild;
}
// 找到要出圈的前一个小孩
Child temp2 = temp;
while (temp2.nextChild != temp) {
temp2 = temp2.nextChild;
}
// 3.将数到m的小孩，退出
temp2.nextChild = temp.nextChild;
// 让temp指向下一个数数的小孩
temp = temp.nextChild;
// this.show();
this.len--;
}
// 最后一个小孩
System.out.println("最后出圈" + temp.no);
}
// 初始化环形链表
public void createLink() {
for (int i = 1; i <= len; i++) {
if (i == 1) {
// 创建第一个小孩
Child ch = new Child(i);
this.firstChild = ch;
this.temp = ch;
} else {
if (i == len) {
// 创建第一个小孩
Child ch = new Child(i);
temp.nextChild = ch;
temp = ch;
temp.nextChild = this.firstChild;
} else {
// 继续创建小孩
Child ch = new Child(i);
temp.nextChild = ch;
temp = ch;
}
}
}
}
// 打印该环形链表
public void show() {
Child temp = this.firstChild;
do {
System.out.print(temp.no + " ");
temp = temp.nextChild;
}
while (temp != this.firstChild);
}
}
结果：
总结
以上就是本文关于java编程约瑟夫问题实例分析的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
相关推荐
-
java递归算法实例分析
递归算法设计的基本思想是: 对于一个复杂的问题,把原问题分解为若干个相对简单类同的子问题,继续下去直到子问题简单到能够直接求解,也就是说到了递推的出口,这样原问题就有递推得解. 在做递归算法的时候,一定要把握住出口,也就是做递归算法必须要有一个明确的递归结束条件.这一点是非常重要的.其实这个出口是非常好理解的,就是一个条件,当满足了这个条件的时候我们就不再递归了. 关键要抓住的是: (1)递归出口 (2)地推逐步向出口逼近 递归就是方法自身调用自身的行为,注意要写好递归头,也就是什么时候退出递归
-
Java递归算法遍历部门代码示例
递归是一个非常有用的知识点.写点实例帮助自己记忆 中间有过程代码 首先一个javapojo类 package com.qcf.po; import java.util.HashSet; import java.util.Set; public class Depart { private long id; private String name; private String destion; //用户 Set<User> users=new HashSet<User>(); //
-
Java实现的双向匹配分词算法示例
本文实例讲述了Java实现的双向匹配分词算法.分享给大家供大家参考,具体如下: 目前比较流行的几大分词算法有:基于字符串匹配的分词方法.基于理解的分词方法和基于统计的分词方法.本文采用的是基于字符串匹配法. 正向最大匹配分词: 该算法是基于分词词典实现,从字符串左侧进行分割匹配,如果词典存在则返回分割出来的词语并将该词从之前的字符串中切除,循环进行切割直到字符串大小为0. 例如:str = "我们都是西北农林科技大学信息工程学院的学生.",(假设我们定义最大切割长度max = 8,也就
-
Java笛卡尔积算法原理与实现方法详解
本文实例讲述了Java笛卡尔积算法原理与实现方法.分享给大家供大家参考,具体如下: 笛卡尔积算法的Java实现: (1)循环内,每次只有一列向下移一个单元格,就是CounterIndex指向的那列. (2)如果该列到尾部了,则这列index重置为0,而CounterIndex则指向前一列,相当于进位,把前列的index加一. (3)最后,由生成的行数来控制退出循环. public class Test { private static String[] aa = { "aa1", &q
-
基于Java实现的一层简单人工神经网络算法示例
本文实例讲述了基于Java实现的一层简单人工神经网络算法.分享给大家供大家参考,具体如下: 先来看看笔者绘制的算法图: 2.数据类 import java.util.Arrays; public class Data { double[] vector; int dimention; int type; public double[] getVector() { return vector; } public void setVector(double[] vector) { this.vect
-
K均值聚类算法的Java版实现代码示例
1.简介 K均值聚类算法是先随机选取K个对象作为初始的聚类中心.然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心.聚类中心以及分配给它们的对象就代表一个聚类.一旦全部对象都被分配了,每个聚类的聚类中心会根据聚类中现有的对象被重新计算.这个过程将不断重复直到满足某个终止条件.终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小. 2.什么是聚类 聚类是一个将数据集中在某些方面相似的数据成员进行分类组织
-
Java分治归并排序算法实例详解
本文实例讲述了Java分治归并排序算法.分享给大家供大家参考,具体如下: 1.分治法 许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题.这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解. 分治模式在每层递归时都有三个步骤: (1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例. (2)解决这些子问题,递归地求解各子问题.然而,
-
Java实现特定范围的完数输出算法示例
本文实例讲述了Java实现特定范围的完数输出算法.分享给大家供大家参考,具体如下: 题目内容: 一个正整数的因子是所有可以整除它的正整数.而一个数如果恰好等于除它本身外的因子之和,这个数就称为完数. 例如6=1+2+3(6的因子是1,2,3). 现在,你要写一个程序,读入两个正整数n和m(1<=n<m<1000),输出[n,m]范围内所有的完数. 提示:可以写一个函数来判断某个数是否是完数. 输入格式: 两个正整数,以空格分隔. 输出格式: 其间所有的完数,以空格分隔,最后一个数字后面没
-
JAVA实现感知器算法
简述 随着互联网的高速发展,A(AI)B(BigData)C(Cloud)已经成为当下的核心发展方向,假如三者深度结合的话,AI是其中最核心的部分.所以如果说在未来社会,每个人都必须要学会编程的话,那么对于程序员来说,人工智能则是他们所必须掌握的技术(科技发展真tm快). 这篇文章介绍并用JAVA实现了一种最简单的感知器网络,不纠结于公式的推导,旨在给大家提供一下学习神经网络的思路,对神经网络有一个大概的认识. 感知器网络模型分析 首先看一张图 如果稍微对神经网络感兴趣的一定对这张图不陌生,这张
-
java编程约瑟夫问题实例分析
一.简介 约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题.在计算机编程的算法中,类似问题又称为约瑟夫环.又称"丢手绢问题".) 例子: len个人围成一个圈,玩丢手绢游戏.从第k个人开始,从1开始数数,当数到m时,数m的人就退出圈子,当圈子只剩下一个人为止. 问题分析与算法设计 约瑟夫问题并不难,但求解的方法很多:题目的变化形式也很多.这里给出一种实现方法. 题目中len个人围成一圈,因而启发我们用一个循环的链来表示,可以使用结构数组来构成一个循环链.结构中有
-
Java集合ArrayDeque类实例分析
Java集合ArrayDeque类实例分析 前言 ArrayDeque类是双端队列的实现类,类的继承结构如下面,继承自AbastractCollection(该类实习了部分集合通用的方法,其实现了Collection接口),其实现的接口Deque接口中定义了双端队列的主要的方法,比如从头删除,从尾部删除,获取头数据,获取尾部数据等等. public class ArrayDeque<E> extends AbstractCollection<E> implements Deque&
-
Java编程BigDecimal用法实例分享
Java中提供了大数字(超过16位有效位)的操作类,即 java.math.BinInteger 类和 java.math.BigDecimal 类,用于高精度计算. 其中 BigInteger 类是针对大整数的处理类,而 BigDecimal 类则是针对大小数的处理类. BigDecimal 类的实现用到了 BigInteger类,不同的是 BigDecimal 加入了小数的概念. float和Double只能用来做科学计算或者是工程计算;在商业计算中,对数字精度要求较高,必须使用 BigIn
-
java编程多线程并发处理实例解析
本文主要是通过一个银行用户取钱的实例,演示java编程多线程并发处理场景,具体如下. 从一个例子入手:实现一个银行账户取钱场景的实例代码. 第一个类:Account.java 账户类: package cn.edu.byr.test; public class Account { private String accountNo; private double balance; public Account(){ } public Account(String accountNo,double
-
java中object类实例分析
问:什么是Object类? 答:Object类存储在java.lang包中,是所有java类(Object类除外)的终极父类.当然,数组也继承了Object类.然而,接口是不继承Object类的,Object类不作为接口的父类. 下面,我们就通过实例,对object进行分析 public class ObjectStu { /*Object类:java里所有类的父类,顶层的类 *equals:判断两个对象是否"相等"; *hashcode:返回一个对象的哈希码值,是一个整数 *因为之后
-
Java编程guava RateLimiter实例解析
本文主要研究的是Java编程guava RateLimiter的相关内容,具体如下. 令牌桶算法(token bucket algorithm) 场景1 在流量监管中的应用 约定访问速率(CAR)是流量监管常用技术之一,可以应用在端口进和出方向,一般应用在入方向,它的监管原理如图1所示. a. 按特定的速率向令牌桶投放令牌 b. 根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送: c. 符合匹配规则的报文,则需要令牌桶进行处理.当桶中有足够的令牌则报文可以
-
Java中递归原理实例分析
本文实例分析了Java中递归原理.分享给大家供大家参考.具体分析如下: 解释:程序调用自身的编程技巧叫做递归. 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量.递归的能力在于用有限的语句来定义对象的无限集合. 递归的三
-
Java接口和抽象类实例分析
本文实例讲述了Java的接口和抽象类.分享给大家供大家参考.具体分析如下: 对于面向对象编程来说,抽象是它的一大特征之一.在Java中,可以通过两种形式来体现OOP的抽象:接口和抽象类.这两者有太多相似的地方,又有太多不同的地方.很多人在初学的时候会以为它们可以随意互换使用,但是实际则不然.今天我们就一起来学习一下Java中的接口和抽象类. 若有不正之处,请多多谅解并欢迎批评指正,不甚感激. 一.抽象类 在了解抽象类之前,先来了解一下抽象方法.抽象方法是一种特殊的方法:它只有声明,而没有具体的实
-
java实现屏幕共享功能实例分析
本文实例讲述了java实现屏幕共享功能的方法.分享给大家供大家参考.具体分析如下: 最近在做软件软件工程的课程设计,做一个用于实验室的屏幕监控系统,参考各种前人代码,最后领悟之后要转换自己的代码,初学者都是这样模仿过来的. 说到屏幕监控系统,有教师端和学生端,教师端就是Server端,学生端就做Client端.系统里比较有趣的一个地方应该算是屏幕广播与屏幕监控吧,其余什么点名签到,锁屏,定时关机的,就相对来说简单点. 屏幕广播,在功能实现上面,说白了,就是教师端的机器不断截取屏幕信息,以图片的形
-
Android编程自定义Notification实例分析
本文实例讲述了Android编程自定义Notification的用法.分享给大家供大家参考,具体如下: Notification是一种让你的应用程序在不使用Activity的情况下警示用户,Notification是看不见的程序组件警示用户有需要注意的事件发生的最好途径. 作为UI部分,Notification对移动设备来说是最适合不过的了.用户可能随时都带着手机在身边.一般来说,用户会在后台打开几个程序,但不会注意它们.在这样的情形下,当发生需要注意的事件时,能够通知用户是很重要的. Noti