好贷网好贷款

使用顺序表求解约瑟夫环问题 (自定义顺序表)

发布时间:2016-12-5 8:38:31 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"使用顺序表求解约瑟夫环问题 (自定义顺序表)",主要涉及到使用顺序表求解约瑟夫环问题 (自定义顺序表)方面的内容,对于使用顺序表求解约瑟夫环问题 (自定义顺序表)感兴趣的同学可以参考一下。

约瑟夫环(Josephus)问题:古代某法官要判决n个犯人的死刑,他有一条荒唐的法律,将犯人站成一个圆圈,从第s个人开始数起,每数到第d个犯人,就拉出来处决,然后再数d个,数到的人再处决……直到剩下的最后一个可赦免。当n=5,s=1,d=2,时: 第一步:定义一个顺序表SeqList<T>: public class SeqList<T> implements LList<T>{ private Object[] element; private int len; public SeqList(int size){ this.element=new Object[size]; this.len=0; } public SeqList(){ this(64); } public SeqList(SeqList<T> list){//拷贝构造方法(深度拷贝) this.len=list.len; this.element=new Object[list.element.length]; for(int i=0;i<list.element.length;i++){ this.element[i]=list.element[i]; } } public boolean isEmpty(){ return this.len==0; } public int length(){ return this.len; } public T get(int i){ if(i>=0&&i<this.len) return (T)this.element[i]; return null; } public void set(int i,T x){ if(x==null) return; if(i>=0&&i<this.len) this.element[i]=x; else throw new IndexOutOfBoundsException(i+""); } public void insert(int i,T x){ if(x==null) return; if(this.len==this.element.length){ Object[] temp=this.element; this.element=new Object[this.element.length*2]; for(int j=0;j<temp.length;j++){ this.element[j]=temp[j]; } } if(i<0){ i=0; } if(i>this.len){ i=this.len; } for(int j=this.len-1;j>=i;j--){ this.element[j+1]=this.element[j]; } this.element[i]=x; this.len++; } public void append(T x){ insert(this.len,x); } public T remove(int i){ if(this.len==0||i<0||i>=this.len) return null; T old=(T)this.element[i]; for(int j=i;j<this.len-1;j++){ this.element[j]=this.element[j+1]; } this.element[this.len-1]=null; this.len--; return old; } public void removeAll(){ this.len=0; } public T search(T key){ int index=this.indexOf(key); return index==-1?null:(T)this.element[index]; } public int indexOf(T key){ if(key!=null){ for(int i=0;i<this.len;i++){ if(this.element[i].equals(key)){ return i; } } } return -1; } public boolean contain(T key){ return this.indexOf(key)>=0; } public boolean equals(Object o){ if(this==o) return true; if(o instanceof SeqList){ SeqList<T> list=(SeqList<T>)o; if(list.length()==this.length()){ for(int i=0;i<list.length();i++){ if(!this.get(i).equals(list.get(i))) return false; } return true; } } return false; } public String toString(){ String str="("; if(this.len>0){ for(int i=0;i<this.len;i++){ if(i<this.len-1) str+=this.element[i].toString()+","; else str+=this.element[i].toString(); } } return str+")"; } } 第二步:定义一个约瑟夫环并求解: public class Josephus { public Josephus(int number,int start,int distance){ SeqList<String> list=new SeqList<String>(number); for(int i=0;i<number;i++){ list.append((char)('A'+i)+""); } 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 Josephus(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

上一篇:10. 搜索操作指南 (4)
下一篇:每天拿出来2小时浪费(文/王路) 作者: 王路

相关文章

相关评论