黑马程序员技术交流社区

标题: Java 数据结构 实现约瑟夫问题的算法 [打印本页]

---

作者: 范贞亮    时间: 2012-10-26 10:23
标题: Java 数据结构 实现约瑟夫问题的算法
总结了下， 当做日记了
package recursion;

public class YusefuQuestion {
        public static void main(String[] args) {
                LinkedList ll = new LinkedList();
                ll.init(5);
                //ll.print();
                ll.play(ll, 2, 2);
        }
}

class Child
{
        public int number;
        public Child next;
       
        public Child(int number) {
                this.number = number;
        }
}

class LinkedList
{
        public Child firstChild;
        public Child temp;
        public int length;
        public void init(int length)
        {
                this.length = length;
                for(int i=1;i<=length; i++)
                {
                        if(i==1)
                        {
                                //说明这里是第一个孩子
                                Child child = new Child(i);
                                firstChild = child;
                                temp = child;
                        }
                        else if(i==length)
                        {
                                Child child = new Child(i);
                                temp.next = child;
                                temp = child;
                                temp.next = firstChild;
                        }
                        else
                        {
                                Child child = new Child(i);
                                temp.next =child;
                                temp = child;
                        }
                }
        }
       
        public void print()
        {
                Child temp  = this.firstChild;
                do
                {
                        System.out.println(temp.number);
                        temp = temp.next;
                }while(temp != firstChild);
        }
        int k=1;
        public void play(LinkedList ll  , int x , int y)
        {
                Child temp = ll.firstChild;
                //先找到第x 个孩子
                for(int i=1 ; i< x ; i++)
                {
                        //注意， 这里的次数 , 因为数数是从自己开始数起的 ， 而temp = temp.next 是一数1的时候就到了2那里
                        //所以要减一次 ,
                        temp = temp.next;
                }
                //for 循环完了之后temp 中存储的就是那个开始的人
               
                //下面就是要开始玩的游戏
                while(length > 0)
                {
                        if(length == 1)
                        {
                                System.out.println("最后出列的孩子是: " + temp.number);
                                return;
                        }
//                        先数y下 ， 同上找到第x 个孩子
                        for(int i=1 ; i< y ; i++)
                        {
                                //注意， 这里的次数 , 因为数数是从自己开始数起的 ， 而temp = temp.next 是一数1的时候就到了2那里
                                //所以要减一次 ,
                                temp = temp.next;
                                System.out.println("第" +k++ +"个出列的孩子是" + temp.number);
                        }
                        //当这个循环出来之后呢， temp 中就是要删除的小孩子了 ，要让此小孩子出列 就是要
                        //让这个temp的上一个小孩子的next变量指向 temp下一个小孩子
                        //我们先保存下要出列的小孩子即 temp
                        Child tempFront = temp;
                        //然后循环找出temp 的上一个小孩子
                        while(tempFront.next != temp)
                        {
                                tempFront = tempFront.next;
                        }
                        //循环玩之后tempFront 中 就是temp的前一个小孩子
                        //然后再将tempFront.next -> temp.next
                        tempFront.next = temp.next;
                        //最后将temp 重新 -> 下一个孩子 即temp.next
                        temp = temp.next;
                        length--;
                        //跟着继续循环
                }
        }
       
}

---

作者: 杨华东    时间: 2012-10-26 10:40
路过   兄弟加油哈。。。。。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2