顺序表之约瑟夫环（josephus）

本文主要是介绍顺序表之约瑟夫环（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）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---