自己实现集合框架:利用顺序表解决约瑟夫环问题

这是系列文章，目的是通过模拟集合框架的简单实现，从而对常用的数据结构和java集合有个大概的了解。当然实现没有java集合的实现那么复杂，功能也没有那么强大，但是可以通过这些简单的实现窥探到底层的一些共性原理。

一. 什么是约瑟夫环?

约瑟夫环问题的起源是这样的：古代有一位法官想要判决n个犯人的死刑,但是他指定了一条荒唐的法律,将犯人围成一个圆圈,从第s个人开始计数,每次数到第d个犯人就拉出来处决,然后再从下一个开始数d个,数到的人再处决,一直循环往复,直到剩下最后一个犯人予以赦免。当n=5,s=1,d=2时的约瑟夫环问题执行过程如下图所示：

二.算法描述

使用上一节实现的顺序表类SeqList求解约瑟夫环问题的算法思路描述如下：

1. 创建一个有n个元素的顺序表对象seqList。
2. 从第s个元素开始计数,每数到d就将对应位置的元素删除。
3. 重复计数并删除元素,直到剩下最后一个元素为止。

设seqList是一个顺序表类的对象,其存储结构草图如下所示,其中数组和对象都是引用数据类型。

设index表示顺序表的元素序号,在计数的时候,让index按照如下规律变化,则顺序表可以被看成是环形结构:(找到这个规律是关键)

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

三.程序实现

package org.light4j.dataStructure.linearList.seqList;

import org.light4j.dataStructure.linearList.LList;

public class Josephus {
    private LList<String> seqList;
    private int distance;

    // 创建约瑟夫环并求解,参数指定环长度,起始位置,计数
    public Josephus(int number, int distance) {
        if(number<=0||distance<=0){
            throw new RuntimeException("number或distance参数输入不合法");
        }
        this.distance=distance;
        this.seqList = new SeqList<String>(number);// 顺序表元素类型是字符串,指定容量
        for (int i = 0; i < number; i++) {
            this.seqList.add((char) ('A' + i) + "");// 添加字符串对象
        }
        System.out.print("约瑟夫环(" + number + "," + distance + "), ");
        System.out.println(this.seqList.toString());// 显示顺序表所有对象的字符串表示
    }

    public void sentence(int start) {
        int index=start-1;
        while (this.seqList.length() > 1) {
            index = (index + this.distance - 1) % this.seqList.length();
            System.out.print("删除" + this.seqList.remove(index).toString() + ", ");// 删除指定位置元素对象
            System.out.println(this.seqList.toString());
        }
        System.out.println("被赦免者是"+this.seqList.get(0).toString());
    }

    public static void main(String[] args) {
        new Josephus(5,2).sentence(1);
    }
}

程序运行结果如下所示：

四.源代码示例

github地址：点击查看
码云地址：点击查看

打赏

微信扫一扫，打赏作者吧～

欢迎关注人生设计师的微信公众账号
公众号ID：longjiazuoA

未经允许不得转载：人生设计师 » 自己实现集合框架:利用顺序表解决约瑟夫环问题