java编程约瑟夫问题实例分析
作者:Mu_TQ 发布时间:2022-04-05 22:32:08
标签:算法,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);
}
}
结果:
来源:http://blog.csdn.net/tianqingdezhuanlan/article/details/52304263
0
投稿
猜你喜欢
- 1.1、获取http请求参数是一种刚需我想有的小伙伴肯定有过获取http请求的需要,比如想前置获取参数,统计请求数据做服务的接口签名校验敏感
- 什么是线程池是一种基于池化思想管理线程的工具。池化技术:池化技术简单点来说,就是提前保存大量的资源,以备不时之需。比如我们的对象池,数据库连
- 整理文档,搜刮出一个spring boot实现过滤器和 * demo ,稍微整理精简一下做下分享。 * 定义:@WebServletpubl
- 原因:feign传值出错无法接收到传值由于是POST所以添加@RequestBody进行尝试解决:错误原因是未添加@RequestBody尝
- Map集合和Collection集合的区别Map集合是有Key和Value的,Collection集合是只有Value。Collection
- 刚接触了一个微服务架构的项目,了解到了启动方式,记录一下1、找到workspace.xml2.打开workspace.xml,找到其中的配置
- 前言异步调用几乎是处理高并发,解决性能问题常用的手段,如何开启异步调用?SpringBoot中提供了非常简单的方式,就是一个注解@Async
- 一、参数管理在编程系统中,为了能写出良好的代码,会根据是各种设计模式、原则、约束等去规范代码,从而提高代码的可读性、复用性、可修改,实际上个
- mybatis foreach嵌套if标签代码实现:Mapper.java文件List<Map<String, Object&g
- 一、原理1、不变模式(不可变对象)在并行软件开发过程中,同步操作似乎是必不可少的。当多线程对同一个对象进行读写操作时,为了保证对象数据的一致
- 成员内部类1.定义成员内部类是直接定义在类中,不加任何修饰符的(特指不加static修饰的)的内部类,可以类比着成员变量来理解,如下面这个代
- 在开发应用过程中,客户端与服务端经常需要进行数据传输,涉及到重要隐私信息时,开发者自然会想到对其进行加密,即使传输过程中被“有心人”截取,也
- 高快省的排序算法有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。假设我们现在对“6 1
- 二维数组实现数字拼图,供大家参考,具体内容如下二维数组可以自己随意定义大小,通过方法判断来实现对所有的数字进行随机打乱,并可以通过移动来正确
- 一:什么是classpath?classpath指的就是 *.java文件,资源文件等编译后存放的位置,对于maven项目就是指 targe
- Java 开发语言中实现HTTP请求的方法主要有两种:一种是JAVA的标准类HttpUrlConnection,比较原生的实现方法;另一种是
- 目前较常用的分页实现办法有两种:1.每次翻页都修改SQL,向SQL传入相关参数去数据库实时查出该页的数据并显示。2.查出数据库某张表的全部数
- 对于静态变量、静态初始化块、变量、初始化块、构造器,它们的初始化顺序依次是(静态变量、静态初始化块)>(变量、初始化块)>构造器
- SqlssionFactory1.SqlSessionFactory是MyBatis的关键对象,它是个单个数据库映射关系经过编译后的内存镜像
- 限流器算法目前常用限流器算法为两种:令牌桶算法和漏桶算法,主要区别在于:漏桶算法能够强行限制请求速率,平滑突发请求,而令牌桶算法在限定平均速