面向对象模拟约瑟夫问题

最普遍的就是39个犹太人自杀,先定义一个要数的数,和开始数数的位置,开始数,数到了就自杀,最后一个人幸免,怎么做呢?

什么是约瑟夫问题

最普遍的就是39个犹太人自杀,先定义一个要数的数,和开始数数的位置,开始数,数到了就自杀,最后一个人幸免,怎么做呢?

1.面向对象模拟环形链表

用面向对象设计犹太人类 ,类中包含编号和下一个犹太人

class Child{
	private int no;
	private Child next;

    public Child( int no) {
        this.no=no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public Child getNext() {
        return next;
    }
    public void setNext(Child next) {
        this.next = next;
    }
    @Override
    public String toString() {
        return "Child [no=" + no + "],";
    }
 }

先设计39个结点的环形链表

定义链表添加,展示原链表方法

class CircleLinked{
	Child first=new Child(0);
	public void  add(int num) {
		if (num<0) {
			System.out.println("数字不符合");
		}
		Child cur=null;
		for (int i =1; i <= num; i++) {
			Child child=new Child(i);
			if (i==1) {
				first=child;
				child.setNext(child);
				cur=child;
			}else {
				cur.setNext(child);
				cur.getNext().setNext(first);
				cur=child;
			}
			
		}
	}
	public void  show() {
		Child cur=first;
		if (cur==null) {
			System.out.println("为空");
		}
		
		while (true) {
			if (first==cur.getNext()) {
				System.out.println(cur.toString());
			
				break;
			}
			System.out.println(cur.toString());
			cur=cur.getNext();
		}
	}
}

删除结点思路


//startNo开始位置,count常数标志,size 总共小孩个数
	public void  outChild (int startNo,int count,int size) {
		if (startNo>size||count>size) {
			System.out.println("数字不符合");
			return;
		}
		//header永远在first 的前一个位置
		//也就是说header.next=header
		Child header=null;
		//现让first指向startNo编号的位置,再让header指向first前边的那个
		while(true) {
			if (startNo==first.getNext().getNo()) {
				break;
			}
			first=first.getNext();
		}
		header=first;
		while(true) {
			if (header.getNext()==header) {
				break;
			}
			
			//count数几次,目的让first和header指向对应的正确位置
			for (int i = 0; i < count-1; i++) {
				first=first.getNext();
				header=header.getNext();
			}
			//把first指向的Child拿出来
			//把header.next指向first的下一个
			System.out.printf("%d->" ,first.getNo());
			header.setNext(first.getNext());
			first=first.getNext();
		}
	
	}

测试类


public static void main(String[] args) {
		CircleLinked circleLinked=new CircleLinked();
		circleLinked.add(39);
		circleLinked.outChild(3,4,39);
	}

/*
5->9->13->17->21->25->29->33->37->2->6->11->16->22->27->32->38->4->10->18->24->31->39->7->15->26->35->5->19->30->3->20->36->14->1->28->23->34->12
*/

那么最后一个12位置的人就幸免于难了

数据结构
算法
  • 作者:张洪祥(联系作者)
  • 发表时间:2019-11-26 16:16:14
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载请声明本文链接!
  • 评论