就是N个人围成一圈,从某个人开始报数,到3的那个人退出,然后从他的下一个重新数,如此循环,直到剩下最后一个人。他讲的数组的那个方法我很容易理解了,可是这个面向对象的这个方法我一头雾水。谁能给我稍微从算法给我解释下这个程序,尤其是里面Kid left,right和Kid first,last是代表什么意思?是Kid的一个属性还是?public class Count3Quit2 {
public static void main(String[] args) {
KidCircle kc = new KidCircle(500);
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(kc.first.id);
}
}class Kid {
int id;
Kid left;
Kid right;
}class KidCircle {
int count = 1;
Kid first, last;
KidCircle(int n) {
for(int i=0; i<n; i++) {
add();
}
}
void add() {
Kid k = new Kid();
k.id = count;
if(count <= 1) {
first = k;
last = k;
k.left = k;
k.right = 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 if (count == 1) {
first = last = null;
} else {
k.left.right = k.right;
k.right.left = k.left;
if(k == first) {
first = k.right;
} else if( k == last) {
last = k.left;
}
}
count --;
}
}
public static void main(String[] args) {
KidCircle kc = new KidCircle(500);
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(kc.first.id);
}
}class Kid {
int id;
Kid left;
Kid right;
}class KidCircle {
int count = 1;
Kid first, last;
KidCircle(int n) {
for(int i=0; i<n; i++) {
add();
}
}
void add() {
Kid k = new Kid();
k.id = count;
if(count <= 1) {
first = k;
last = k;
k.left = k;
k.right = 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 if (count == 1) {
first = last = null;
} else {
k.left.right = k.right;
k.right.left = k.left;
if(k == first) {
first = k.right;
} else if( k == last) {
last = k.left;
}
}
count --;
}
}
Kid 是“个人类”,其中left表示其左边的人,right表示其右边的人,id表示自己的编号
算法是这样的:
在创建所有人的类的对象的时候,这样子new KidCircle(500);
在这个对象构造的时候,会依次生成500个Kid类的对象,
并把left,right,id这几个属性正确的初始化
看KidCircle中的add()方法这样500个人的圈圈就准备好了
之后对这个圈圈进行循环每数3个人,把这个人从圈圈里去掉,
然后把这个人的左右两个的left和right属性更新
比如原来是这样
3.right--->4
3.left--->2
2.right--->3
4.left--->3
现在3去掉了
变成这样:
2.right--->4
4.left--->2
这样在下次扫描到2之后就会直接跳过3了
具体看KidCircle 的 delete(Kid k)方法最后当KidCircle 的count为1的时候,把剩下的那个人的id输出其实这个算法并不好
生成了这么多的对象和引用很耗内存的
我把圈子数改成11111500的时候就jvm就报内存溢出了(默认heap有16MB呢)
楼主可以自己想一个更好的算法
围成一圈,从第一个人开始数数,countNum是计数的,没当countNum为3时,将数到3的那个人从队列删除,同时再将countNum=0,重新开始计数。如此循环,最后将剩下的那个人输出。
last.right = k;
k.left = last;
k.right = first;
first.left = k;
last = k;
}
这个我不是太懂,如果count>1,那就最后一个人的右边是k,k的左边是最后一个人,k的右边是第一个人,第一个人的左边是k,k是最后一个人,那不是只有一个人了么?
last.right = k;//原最后一个人的右边是k
k.left = last;;//k的左边是原最后一人
k.right = first;//k的右边是第一人
first.left = k;//第一人的左边是k
last = k;//k变成现在最后一人仔细看看发现什么没有?
怎么会只有1个人,
第一人的右边是谁?
原最后一人的左边又是谁?
这些有没有被覆盖掉