约瑟夫环(Josephus)问题:古代某法官要判决n个犯人的死刑,他有一条荒唐的法律,将犯人站成一个圆圈,从第s个人开始数起,每数到第d个犯人,就拉出来处决,然后再数d个,数到的人再处决……直到剩下的最后一个可赦免。当n=5,s=1,d=2,时:
第一步:定义节点Node
public class Node<T> {
public T data;
public Node<T> next;
public Node(T data,Node<T> next){
this.data=data;
this.next=next;
}
public Node(){
this(null,null);
}
}
第二步:定义单链表SingleLinkedList<T>
public class SingleLinkedList<T> implements LList<T> {
private Node<T> head;
public SingleLinkedList(){
this.head=new Node<T>();
}
public SingleLinkedList(SingleLinkedList<T> list){
Node<T> p=list.head.next;
Node<T> rear=this.head;
while(p!=null){
rear.next=new Node<T>(p.data,null);
rear=rear.next;
p=p.next;
}
}
public SingleLinkedList(T[] element){
this();
Node<T> rear=this.head;
for(int i=0;i<element.length;i++){
rear.next=new Node<T>(element[i],null);
rear=rear.next;
}
}
public boolean isEmpty(){
return this.head.next==null;
}
public int length(){
int i=0;
Node<T> p=this.head.next;
while(p!=null){
i++;
p=p.next;
}
return i;
}
public T get(int i){
if(i>=0){
Node<T> p=this.head.next;
for(int j=0;p!=null&&j<i;j++){
p=p.next;
}
if(p!=null)
return p.data;
}
return null;
}
public void set(int i,T x){
if(x==null){
return;
}
if(i>=0){
Node<T> p=this.head.next;
for(int j=0;p!=null&&j<i;j++){
p=p.next;
}
if(p!=null)
p.data=x;
}else{
throw new IndexOutOfBoundsException();
}
}
public void insert(int i,T x){
if(x==null)
return;
Node<T> p=this.head;
for(int j=0;p.next!=null&&j<i;j++){
p=p.next;
}
p.next=new Node<T>(x,p.next);
}
public void append(T x){
insert(Integer.MAX_VALUE,x);
}
public T remove(int i){
if(i>=0){
Node<T> p=this.head;
for(int j=0;p.next!=null&&j<i;j++){
p=p.next;
}
if(p.next!=null){
T old =p.next.data;
p.next=p.next.next;
return old;
}
}
return null;
}
public void removeAll(){
this.head.next=null;
}
public T search(T key){
int index=this.indexOf(key);
Node<T> p=this.head.next;
if(index>=0){
for(int j=0;p!=null&&j<index;j++){
p=p.next;
}
if(p!=null){
return p.data;
}
}
return null;
}
public int indexOf(T key){
Node<T> p=this.head.next;
int i=-1;
while(p!=null){
i++;
if(p.data.equals(key)){
return i;
}
}
return -1;
}
public String toString(){
String str="(";
Node<T> p=this.head.next;
while(p!=null){
str+=p.data.toString();
if(p.next!=null)
str+=",";
p=p.next;
}
str+=")";
return str;
}
public static<T> void reverse(SingleLinkedList<T> list){
Node<T> p=list.head.next,succ=null,font=null;
while(p!=null){
succ=p.next;
p.next=font;
font=p;
p=succ;
}
list.head.next=font;
}
public boolean isEquals(Object o){
if(this==o)
return true;
if(!(o instanceof SingleLinkedList)){
return false;
}else{
Node<T> p=this.head.next;
Node<T> q=((SingleLinkedList<T>)o).head.next;
while(p!=null&&q!=null&&p.data.equals(q.data)){
p=p.next;
q=q.next;
}
return p==null&&q==null;
}
}
}
第三步定义约瑟夫环并求解:
public class Josephus {
public Josephus2(int number,int start,int distance){
SingleLinkedList<String> list=new SingleLinkedList<String>();//自定义的单链表
for(int i=0;i<number;i++){
list.append((char)('A'+i)+"");
}
//list.reverse(list);//单链表逆转
System.out.print("约瑟夫环("+number+","+start+","+distance+"),");
System.out.println(list.toString());
int i=start;
while(list.length()>1){
i=(i+distance-1)%list.length();
System.out.print("删除的元素:"+list.remove(i).toString()+",");
System.out.println(list.toString());
}
System.out.println("被赦免的罪犯是:"+list.get(0).toString());
}
public static void main(String[] args) {
new Josephus2(5,0,2);
}
}
第四步:输出结果如下
约瑟夫环(5,0,2),(A,B,C,D,E)
删除的元素:B,(A,C,D,E)
删除的元素:D,(A,C,E)
删除的元素:A,(C,E)
删除的元素:E,(C)
被赦免的罪犯是:C