这是系列文章,目的是通过模拟集合框架的简单实现,从而对常用的数据结构和
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

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