鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 网站制作教程 > JSP > >

Josephus环类问题,java实现

来源:互联网 作者:佚名 时间:2016-06-19 10:27
写出一个双向的循环链表,弄一个计数器,我定义的是到三的时候,自动删除当前节点,很简单。 package Com; import java.util.Scanner; /* * 约瑟夫环问题,有n个人组成的圈,数到3的那个人出列,下个人继续从一开始 */ public class Josephus { public stati

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

  

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;
    }
}

 


网友评论
<