你的位置:首页 > Java教程

[Java教程]Josephus环类问题,java实现


  写出一个双向的循环链表,弄一个计数器,我定义的是到三的时候,自动删除当前节点,很简单。

  

package Com;import java.util.Scanner;/* * 约瑟夫环问题,有n个人组成的圈,数到3的那个人出列,下个人继续从一开始 */public class Josephus {    public static void main(String[] args) {    Scanner s = new Scanner(System.in);    int n = Integer.parseInt(s.nextLine());    Node first = new Josephus().startRun(n );    int count = 1;    while(first.next != first) {      first = first.next;      count++;      if(count == 3) {        first.previous.next = first.next;        first.next.previous = first.previous;        first = first.next;        count = 1;      }    }    System.out.println("最后剩下来的数字为:"+first.n);  }    public Node startRun(int n) {    Node first = new Node();    first.previous = null;    first.n = n ;  //这里给链表赋值,倒叙    Node current = first;    Node last = first;    while((--n)>0) {      current.next = new Node();      current = current.next;      current.n = n;      current.previous = last;      last = current;    }    current.next = first;    first.previous = current;    return first;  }  class Node {    int n ;     Node next;    Node previous;  }}