黑马程序员技术交流社区

标题: 【约瑟夫环】约瑟夫环的具体实现 [打印本页]

---

作者: 可以假装看不见    时间: 2016-3-25 16:33
标题: 【约瑟夫环】约瑟夫环的具体实现
做了一道试题关于100个人围圈报数的，不明白怎么定义指针进行报数，必须要用到约瑟夫环，或者有没有其他方法可以实现。求解啊大神们！！

---

作者: 可以假装看不见    时间: 2016-3-25 19:50
没人给解释下吗？

---

作者: xanx14710    时间: 2016-3-25 20:30
package com.heima08;

public class Test2  
{  
    public static void main(String[] args)  
    {  
        //头结点  
        Node root = new Node(1);  
        int[] order = build(root,9,5);  
        for(int i =0;i<order.length;i++)  
        {  
            System.out.print(order[i]+" ");  
        }  
    }  
    //将约瑟夫环建成一个链表  
    public static int[] build(Node root,int n, int m)  
    {  
        Node current = root;  
        for(int i = 2; i<=n; i++)  
        {  
            Node node = new Node(i);  
            current.next = node;  
            current = node;  
        }  
        current.next = root;  
        int[] order = come(root,n,m);  
        return order;  
    }  
    //出队列  
    //结束条件：只有一个结点时，这个结点的next是它自身  
    //将出来的数，放在一个数组中，遍历数组就是出队序列  
    public static int[] come(Node root,int n, int m)  
    {  
        int[] order = new int[n];  
        int j = 0;  
        Node p = root;  
        while(p.next!=p)  
        {  
            int i = 1;  
            while(i<m-1)  
            {  
                p=p.next;  
                i++;  
            }  
            if(i==m-1)  
            {  
                order[j]=p.next.data;  
                j++;  
                p.next = p.next.next;  
                p=p.next;  
            }  
        }  
        order[j]=p.data;  
        return order;  
    }  
}  
class Node  
{  
    int data;  
    Node next;  
    public Node(int data)  
    {  
        this.data = data;  
        next= null;  
    }  
}  

---

作者: 可以假装看不见    时间: 2016-3-25 21:07

xanx14710 发表于 2016-3-25 20:30
package com.heima08;

public class Test2  

多谢大神了

---

作者: xanx14710    时间: 2016-3-26 21:58
package com.heima09;
import java.util.ArrayList;
public class Test {
public static void main(String[]args){
         ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=1;i<=9;i++){
                list.add(i);
        }
   int[]a=new int[9];
   int j=0;
   int b=1;
   while(true){
           for(int i=0;i<list.size();i++){
                   if(b%5==0){
                           a[j]=list.remove(i);
                          
                           j++;
                           i--;
                if(list.size()==1){
                                   a[j]=list.get(0);
                           }
                          
                   }
                   b++;
           }
           if(list.size()==0){
                   break;
           }
   }
   for(int i=0;i<a.length;i++){
           System.out.print(a[i]+" ");
   }
}
}
我还想出一个方法

---

作者: 可以假装看不见    时间: 2016-3-28 16:22

xanx14710 发表于 2016-3-26 21:58
package com.heima09;
import java.util.ArrayList;
public class Test {

多谢 多谢 厉害

---

作者: w310822336    时间: 2016-3-28 18:45
表示有点看不懂

---

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

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