Java解决约瑟夫问题代码实例

代码如下:

package list;

import java.util.ArrayList;

/**
 * Java约瑟夫问题: n个人(不同id)围成一个圈,从startId(任意数)个开始报数m(任意数)个数,数m的人出列排成新队列,m清零,
 * 然后又从下一个人开始数m个数开始,数到m就出列接在新队列尾部,如此重复,知道所有人都出列为止。
 * 打印 出列后的新队列
 *
 * eg
 * int n = 10;//总人数
 * int m = 3;   //报数个数
 * int startIndex = 1;  //起点位置
 * @author Hulk   2014  03 20
 *
 */
public class JosephListTest {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        JosephListTest test = new JosephListTest();
        int n = 10; //总人数
        int m = 3; //报数个数
        int startIndex = 12; //起点位置
        System.out.println("JosephListTest: n= " + n + ", m= " + m +
            ", startIndex= " + startIndex + "\n\nQUEUE RESULT:");

ArrayList<Person> queueList = test.queuePreson(n, m, startIndex);

for (Person person : queueList) {
            System.out.println("OUT person: " + person);
        }

System.out.println("use time= " +
            (System.currentTimeMillis() - startTime));
    }

private ArrayList<Person> queuePreson(int n, int m, int startIndex) {
        ArrayList<Person> queueList = null;
        PersonList list = createList(n);

//list.search();
        if ((list != null) && (list.head != null)) {
            queueList = new ArrayList<JosephListTest.Person>();

PNode pNode = list.head;

if (startIndex > 0) {
                startIndex = startIndex % n;
                pNode = list.getNode(startIndex);
            } else {
                pNode = list.head;
            }

int count = 1;

while (list.size > 0) {
                Person outPerson = null;

//find
                if (count == (m - 1)) {
                    //delete next node
                    Person prev = pNode.person;
                    outPerson = list.remove(prev);
                    queueList.add(outPerson);
                    //System.out.println("OUT person: " + outPerson + ", size= " + list.size);
                    count = 0;
                }

pNode = pNode.next;
                count++;
            }
        }

return queueList;
    }

private PersonList createList(int n) {
        PersonList list = new PersonList();

for (int i = 0; i < n; i++) {
            Person person = new Person(i, "name_" + (i + 1));
            list.add(i, person);
        }

return list;
    }

public class PersonList {
        PNode head = null;
        int size = 0;

public PersonList() {
        }

public PersonList(Person person) {
            head = new PNode(person, head);
            size++;
        }

public PersonList(PNode head) {
            this.head = head;
            head.setNext(head);
            size++;
        }

public PNode getHead() {
            return head;
        }

public void setHead(PNode head) {
            this.head = head;
        }

public int getSize() {
            return size;
        }

public void setSize(int size) {
            this.size = size;
        }

public void size(int size) {
            this.size = size;
        }

public boolean isEmpty() {
            return this.size <= 0;
        }

public void initHead(Person person) {
            if (size == 0) {
                head = new PNode(person, head);
            } else {
                PNode no = head;
                head = new PNode(person, no);
            }

size++;
        }

public void add(int index, Person person) {
            if (size == 0) {
                head = new PNode(person, head);
                head.setNext(head);

//System.out.println("head: " + head);
            } else {
                if (index < 0) {
                    index = 0;
                }

if (index > size) {
                    index = size;
                }

PNode no = head;

for (int i = 0; i < (index - 1); i++) {
                    no = no.next;
                }

PNode newNode = new PNode(person, no.next);
                no.next = newNode;
            }

size++;
        }

public Person delete(int index) {
            PNode pNode = remove(index);

if ((pNode != null) && (pNode.next != null)) {
                return pNode.next.person;
            }

return null;
        }

public PNode remove(int index) {
            if (size == 0) {
                return null;
            } else {
                if ((index < 0) || (index >= size)) {
                    return null;
                }
            }

PNode no = head;

for (int i = 0; i < (index - 1); i++) {
                no = no.next;
            }

no.next = no.next.next;
            size--;

if ((no != null) && (no.next != null)) {
                return no.next;
            }

return null;
        }

/**
        * remove next node of person node, and return the deleted person
        * @param prePerson
        * @return  removed Person
        */
        public Person remove(Person prePerson) {
            if (prePerson == null) {
                return null;
            }

if (size == 0) {
                return null;
            }

PNode preNode = head;
            int index = -1;

for (int i = 0; i < size; i++) {
                if (preNode.person.id == prePerson.id) {
                    index = i;

break;
                } else {
                    preNode = preNode.next;
                }
            }

Person remPerson = null;

if (size <= 1) {
                //only one node, get its person and set it as null
                remPerson = preNode.person;
                preNode = null;
            } else {
                //preNode.next.person is dest one
                remPerson = preNode.next.person;
                preNode.next = preNode.next.next;
            }

size--;

//System.out.println("deleteing index= " + index + " :  " + remPerson + ", size= " + size);
            return remPerson;
        }

public int update(Person src, Person dest) {
            if (src == null) {
                return -1;
            }

int index = -1;
            PNode no = head;

for (int i = 0; i < size; i++) {
                if (src.id == no.person.id) {
                    no.person = dest;

break;
                } else {
                    no = no.next;
                }
            }

return index;
        }

public boolean set(int index, Person person) {
            if (person == null) {
                return false;
            }

if (size == 0) {
                return false;
            } else {
                if ((index < 0) || (index >= size)) {
                    return false;
                }
            }

PNode no = head;

for (int i = 0; i < index; i++) {
                no = no.next;
            }

no.person = person;

return true;
        }

public Person get(int index) {
            PNode no = getNode(index);

if (no != null) {
                return no.person;
            }

return null;
        }

public PNode getNode(int index) {
            if (size == 0) {
                return null;
            } else {
                if ((index < 0) || (index >= size)) {
                    return null;
                }
            }

PNode no = head;

for (int i = 0; i < index; i++) {
                no = no.next;
            }

return no;
        }

public void search() {
            int sizeLong = size;
            PNode no = head;

for (int i = 0; i < sizeLong; i++) {
                System.out.println("search index= " + i + ",   " + no);
                no = no.next;
            }
        }
    }

public class PNode {
        Person person;
        PNode next = null;

public PNode() {
        }

public PNode(Person person) {
            this.person = person;
        }

public PNode(Person person, PNode next) {
            this.person = person;
            this.next = next;
        }

@Override
        public String toString() {
            return "PNode [person=" + person.id + ", next=" + next.person.id +
            "]";
        }

public Person getPerson() {
            return person;
        }

public void setPerson(Person person) {
            this.person = person;
        }

public PNode getNext() {
            return next;
        }

public void setNext(PNode next) {
            this.next = next;
        }
    }

public class Person {
        int id = 0;
        String name = "";

public Person() {
        }

public Person(int id, String name) {
            super();
            this.id = id;
            this.name = name;
        }

@Override
        public String toString() {
            return "Person [id=" + id + ", name=" + name + "]";
        }
    }
}

(0)

相关推荐

  • Java使用递归解决算法问题的实例讲解

    解释:程序调用自身的编程技巧叫做递归. 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量.递归的能力在于用有限的语句来定义对象的无限集合. 递归的三个条件: 1.边界条件 2.递归前进段 3.递归返回段 当边界条件不满足时,

  • Java递归算法经典实例(经典兔子问题)

    题目:古典问题:3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 分析:首先我们要明白题目的意思指的是每个月的兔子总对数:假设将兔子分为小中大三种,兔子从出生后三个月后每个月就会生出一对兔子, 那么我们假定第一个月的兔子为小兔子,第二个月为中兔子,第三个月之后就为大兔子,那么第一个月分别有1.0.0,第二个月分别为0.1.0, 第三个月分别为1.0.1,第四个月分别为,1.1.1,第五个月分别为2.1.2,第六个月分别为3.2.3,第

  • java基于递归算法实现汉诺塔问题实例

    本文实例讲述了java基于递归算法实现汉诺塔问题.分享给大家供大家参考,具体如下: package test; import java.util.List; import java.util.ArrayList; import java.util.Scanner; import sun.net.www.content.audio.x_aiff; /** * @author 年浩 * */ public class test { public static void move(char x,cha

  • 使用java实现LIS算法,出操队形的问题

    假设有序列:2,1,3,5,求一个最长上升子序列就是2,3,5或者1,3,5,长度都为3. LIS算法的思想是: 设存在序列a. ① 如果只有一个元素,那么最长上升子序列的长度为1: ② 如果有两个元素,那么如果a[1]>a[0],则最长上升子序列的长度为2,a[1]为该最长上升子序列的最后一个元素;若a[1]<a[0],则最长上升子序列的长度为1,a[0]和a[1]均为  其最长上升子序列的最后一个元素. ③ 如果由三个元素,那么如果a[2]>a[0],a[2]>a[1],则a[

  • Java基于循环递归回溯实现八皇后问题算法示例

    本文实例讲述了Java基于循环递归回溯实现八皇后问题.分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @author Administrator * */ public interface Piece { abstract boolean isRow(int line); abstract boolean isCol(int line,int col); } 棋盘类: /** * 棋盘 * @author Administrator * */ public

  • java 实现约瑟夫环的实例代码

    复制代码 代码如下: import java.io.BufferedInputStream;import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Josephus {    private static class Node{        int No;        Node next;        public Node(int No){            this

  • 浅谈java实现背包算法(0-1背包问题)

    0-1背包的问题 背包问题(Knapsack problem)是一种组合优化的NP完全问题.问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高.问题的名称来源于如何选择最合适的物品放置于给定背包中. 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放. 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值.则其状态转移方程便是: f[i][v]=max{ f[i-1][v], f

  • Java数据结构及算法实例:汉诺塔问题 Hanoi

    /** * 汉诺塔大学的时候就学过,但是根本没搞明白,唯一知道的就是要用递归的方法来求解. * 问题描述: * 有三根杆子A,B,C.A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小. * 要求按下列规则将所有圆盘移至C杆: * 1.每次只能移动一个圆盘: * 2.大盘不能叠在小盘上面. * 提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆, * 但都必须尊循上述两条规则. * 问:如何移?最少要移动多少次? * 解决方法: * 假设只有2个盘子,柱子分别是A, B, C柱

  • Java简单实现约瑟夫环算法示例

    本文实例讲述了Java简单实现约瑟夫环算法.分享给大家供大家参考,具体如下: 1.算法背景: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数 仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止. 约瑟夫和他的朋友并不想自杀,于是约

  • Java采用循环链表结构求解约瑟夫问题

    本文实例讲述了Java采用循环链表结构求解约瑟夫问题的方法.分享给大家供大家参考.具体分析如下: 这是第一次java考试的试题,对于没看过链表的同学来说就不会做,现在回头看看,还真不难. 约瑟夫问题: 有n个人,其编号分别为1,2,3,-,n.这n个人按顺序排成一个圈.现在给定s和d,从第s个人开始从1依次报数,数到d的人出列,然后又从下一个人开始又从1开始依次报数,数到d的人又出列,如此循环,直到最后所有人出列为止.要求定义一个节点类,采用循环链表结构求解约瑟夫问题. 以下java版的答案:

随机推荐