双向回环链表的实现.解决方法

双向回环链表的实现.
声明一下,这个是看马士兵老师的java视频教程的时候看到的例子,感觉有趣就拿出来大家做做,思路很明确的给了出来,就是让大家实现一下整个类,另外构造一个测试的类给搞出来就over了.

鸡肋型问题.高手不惜的做,因为我就肯花十分.我们新手确实有难度,就是大家锻炼下.

小孩玩游戏,手拉手围成一个圈,然后数数.每次数到3的时候这个小孩退出,下一个从1开始再数.
试问,如果有500个小孩,最后剩下的小孩是原来的第多少个小孩.
要求:面向对象程序设计实现.

简析:
两个类:小孩,圈.
class Kid {
  int id;
  Kid left;
  Kid right;
}

class KidCircle {
  int count;
  Kid first,last;

  KidCircle(int n) {
  count = n;
  }

  void add() {}
  void delete() {}
}



[解决办法]
确切的名字叫做 ： 约瑟夫环问题
典型的做法是模拟一个环形数组，即arr[i%N]
另一个做法只需要一个数学公式，一句话就可以得出答案，非常精炼。

确实有兴趣可以讨论下。
[解决办法]
看下人家的解决办法
public class Josephus {

public static void main(String[] args) {
if(args.length<2){
System.out.println("Input N and M.");
return;
}
int n = Integer.parseInt(args[0]);
int m = Integer.parseInt(args[1]);
int point=0,number=1;
List<Integer> list = new ArrayList<Integer>();
for(int i=1;i<=n; i++){
//初始化链表
list.add(i);
}

while(list.size()>1){
if(number%m==0){
list.remove(point);
--point;
}
++point;//指针后移
++number;
if(point>list.size()-1){
//指针越界重新开始
point=0;
}
}


System.out.println(list.get(0));

}
}
[解决办法]

Java code

public class Kie {    int id;    Kie left;    Kie right;    public Kie()    {            }    public Kie(int id)    {        this.id=id;    }    public int getId() {        return id;    }    public void setId(int id) {        this.id = id;    }    public Kie getLeft() {        return left;    }    public void setLeft(Kie left) {        this.left = left;    }    public Kie getRight() {        return right;    }    public void setRight(Kie right) {        this.right = right;    }    public static void main(String []args)    {        Kie head=null;        Kie last=null;        Kie newF = null;        for(int i=1;i<8;i++)        {            newF = new Kie(i);            if(head==null)            {                head=newF;                last = head;            }else            {                last.right=newF;                last = newF;            }        }        head.left=last;        last.right=head;//        Kie k =head;//        while(k.right!=head)//        {//            System.out.println(k.id);//            k = k.right;//        }//                Kie node = head;        while(node.left!=node.right||node.left==node.right&&node.left!=node)        {            node.right.right=node.right.right.right;            node.right.right.left=node.right;            node=node.right.right;            //System.out.println(node.id);        }        System.out.println(node.id);    }}
[解决办法]
你还真拿对象造个环哦......

下面是我做的。
package KidsGame;

import java.util.ArrayList;

public class Kids {
  int nowNumber=0;
public int GetNumber(){

 return nowNumber++;

}
public void CallBack(){
nowNumber=1;
}
}
----------------------------------分割线---------------------------------

package KidsGame;

import java.util.ArrayList; 
 

public class Ring {
ArrayList ring;
 int thisPoint = 0;

Ring(ArrayList ring) {
this.ring = ring;
}

public void ringRun(Kids kid) {

if (thisPoint > ring.size() - 1) {
thisPoint = 1;
}

if (kid.GetNumber() == 3) {
kid.CallBack();
ringDwindle();
}else {
thisPoint++;
}

//System.out.println("下标指向"+thisPoint);

}

private void ringDwindle() {
//System.out.println("正在移出"+ring.get(thisPoint));
ring.remove(thisPoint);

}

public static void main(String[] args) {
Kids kid = new Kids();
for (int i = 0; i < 10; i++) {
if (kid.GetNumber() == 3) {
kid.CallBack();

}
}
}
}
----------------------------------分割线---------------------------------
package KidsGame;

import java.util.ArrayList;

public class Test {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
int ringSize=8;
for(int i=0;i<ringSize+1;i++){
list.add("我是第"+i+"号");

}

Ring ring=new Ring(list);
Kids kid=new Kids();

while (ring.ring.size()>2)
 {
ring.ringRun(kid);

}
    System.out.println("最后"+ring.ring.get(1));


}
}