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

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 + "]";
        }
    }
}