双向回环链表的实现.

Question

声明一下,这个是看马士兵老师的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() {}
}

Answer 1

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

Answer 2

看下人家的解决办法
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));
        
    }
}

Answer 3

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);
}
}

Answer 4

上边的while循环主是处理的过程,只要是left!=right表示不是只一个结点,那么就要继续循环
有一个种情况就是left==right的,但不只一个结点,也就是当只有两个结点的时候left==rigth,如果只有一个结点的时候left将会是等于它本身.

Answer 5

class Kid {
  int id;
  Kid left;
  Kid right;
}class KidCircle {
  int count = 0;
  Kid first;
  Kid last;  KidCircle(int n) {
    for(; count<n;) {
      count++;
      add();
    }
  }  void add() {
    Kid k = new Kid;
    k.id = count;
    
    if(count == 1) {
      k.left = k.right = first = last = k;
    } else {
    last.right = k;
    k.left = last;
    k.right = first;
    first.left = k;
    last = k;
    }    count++; 
  }  void delete(Kid k) {
    if(count <= 0) {
      return;
    } else(count == 1) {
      first = last = null;
    } else {
      k.right.left = k.left;
      k.left.right = k.right;      if(k == first) first = k.right;
      else if(k == last) last = k.left;
    }
    count--;
  }
}

Answer 6

public class Test {
  public static void main(String[] args) {
    if(args.length>1)System.out.println("This program only have one argument.");
    KidCircle kc = new KidCircle(args[0]);
    int countNum = 0;
    Kid k = kc.first;
    
    while(kc.count > 1) {
      countNum++;
      if(countNum == 3) {
        countNum == 0;
        kc.delete(k);
      }
      k = k.right;
    }    System.out.println("If have " + args[0] +"children ," + "the last child is the child whoes id is: " + kc.first.id);
  }
}

Answer 7

你还真拿对象造个环哦......下面是我做的。
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));
}
}

Answer 8

报数退出问题，我有个很不错的例子，算法很精妙。有兴趣的可以去我 CSDN blog看看