双向回环链表的实现.
声明一下,这个是看马士兵老师的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));
}
}
[解决办法]
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));
}
}