顺序表之约瑟夫环(josephus)

2024-03-31 11:32

本文主要是介绍顺序表之约瑟夫环(josephus),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.问题描述

        n个犯人站成一个圈,从第s个人开始数起,每数到第d个犯人,就拉出来斩了,然后再从下一个开始数d个,数到的人再处决,………………,直到剩下最后一个犯人就予以赦免。

2.算法描述

          创建一个具有n个元素的顺序表对象list。

          从第s个元素开始,依次计数,每数到d,就将对应的元素删除。

          重复计数并删除元素,知道剩下一个元素。

3.算法的java实现

package linearList;public class Josephus {private LList<String> list;//创建顺序表,用来存储元素/** 创建约瑟夫环并求解,指定其长度、起始位置、计数*/public Josephus(int number,int start,int distance){this.list = new SeqList<String>(number);//创建指定容量的的顺序表for(int i=0;i<number;i++){this.list.add(new String((char)('A'+i)+""));//添加字符串对象}System.out.print("约瑟夫环("+number+","+start+","+distance+"),");System.out.println(this.list.toString());//显示字符串int index = start-1;//计数起始位置while(this.list.length()>1){//只有在多余一个对象时才执行删除操作index = (index+distance-1)%this.list.length();System.out.print("删除"+this.list.remove(index).toString()+",");System.out.println(this.list.toString());}System.out.println("被赦免者是:"+list.get(0).toString());}public static void main(String[] args) {new Josephus(5,1,2);}}
程序运行结果

          约瑟夫环(5,1,2),(A,B,C,D,E)
          删除B,(A,C,D,E)
          删除D,(A,C,E)
         删除A,(C,E)
         删除E,(C)
         被赦免者是:C

4.实现过程分析

     成员变量list声明为LList(线性表概括)接口的变量,声明如下:

                       private LList<String> list;

    list可被赋值为实现LList接口的类(线性表之顺序表)的对象。即

                      this.list = new SeqList<String>(number);

    index表示顺序表元素符号,由于约瑟夫环是一个环形结构,所以顺序表也要是环形的,这就要求计数时,index应该执行取余操作,即

                    index = (index+distance-1)%this.list.length();

5.效率分析

       由于涉及到添加和删除操作,所以用顺序表来实现约瑟夫环不是太理想,时间复杂度为O(n),因此我们需要寻找其他的结构来实现,后面我们会随着数据结构的深入学习,尝试用其他算法求解并进行比较,如下是用顺序表求解时消耗的时间

public static void main(String[] args) {long startTime = System.currentTimeMillis();for(int i=0;i<10;i++)new Josephus(5,1,2);long endTime = System.currentTimeMillis();System.out.println("程序运行时间:"+(endTime-startTime)+"ms");}
程序运行时间:32ms

      



这篇关于顺序表之约瑟夫环(josephus)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/864225

相关文章

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹

PHP约瑟夫环问题

#循环 function circle($arr,$idx,$k){for($i=0;$i<$idx;$i++){$tmp = array_shift($arr);array_push($arr,$tmp);}$j = 1;while(count($arr) > 0){$tmp = array_shift($arr);if($j++%$k == 0){echo $tmp."\n";}else{a

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表,允许插入的一端叫做队尾(rear),允许删除的一端叫做队首(front)。 队列具有FIFO的性质 队列的存储表示也有两种方式:基于数组的,基于列表的。基于数组的叫做顺序队列,基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示:只提供了接口和显式的默认构造函数和析构函数,在派生类中调用。 #i

[数据结构]栈之顺序栈的类模板实现

栈的数组实现形式,采用动态分配数组,不够时可以调整栈的大小。 Stack.h文件:主要定义栈的抽象基类,提供公共的接口函数。 #ifndef STACK#define STACK//栈的抽象基类template<class T>class Stack{public:Stack(){}~Stack(){}virtual void Push(const T& x)=0;virt

C++中类的构造函数调用顺序

当建立一个对象时,首先调用基类的构造函数,然后调用下一个派生类的 构造函数,依次类推,直至到达派生类次数最多的派生次数最多的类的构造函数为止。 简而言之,对象是由“底层向上”开始构造的。因为,构造函数一开始构造时,总是 要调用它的基类的构造函数,然后才开始执行其构造函数体,调用直接基类构造函数时, 如果无专门说明,就调用直接基类的默认构造函数。在对象析构时,其顺序正好相反。

七、Maven继承和聚合关系、及Maven的仓库及查找顺序

1.继承   2.聚合   3.Maven的仓库及查找顺序

线性表中顺序表的合并

对两个顺序表进行合并,算法的复杂度为O(La.size+Lb.size)。 已知: 顺序线性表La和Lb的元素按值非递减排列 归并La和Lb得到的顺序线性表Lc,Lc的元素也按值非递减排列。 代码定义: void mergeList(SeqList *La,SeqList *Lb,SeqList *Lc){Lc->capacity = La->size + Lb->size;Lc->b

理解C++全局对象析构顺序与 IPC 资源管理:避免 coredump

文章目录 0. 概述1. 问题背景2. 问题分析3. 解决方案:手动释放资源4. 深入剖析:为什么手动调用 `reset()` 有效?5. 延伸思考:如何避免全局对象带来的问题?6. 总结 0. 概述 在编写 C++ 程序时,使用全局或静态对象有时可能会导致不可预期的崩溃(如 coredump)。这类崩溃通常源于对象的析构顺序、资源的管理方式,以及底层资源(如 IPC 通道或共