人生设计师
这是系列文章，目的是通过模拟集合框架的简单实现，从而对常用的数据结构和
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);
}
}
程序运行结果如下所示：
四.源代码示例
公众号ID：longjiazuoA
未经允许不得转载：人生设计师 » 自己实现集合框架:利用顺序表解决约瑟夫环问题