逢三退一（双向回环链表算法） 中的疑惑~
** 用面向对象方法实现（双向回环链表算法）
*
* 逢三退一：一个头和尾相连的圆形数字队列，从第一个开始数，数到三，
* 就把三的那个去掉，然后接着数，如此循环，逢三退一。
* 直到最后一个为止，求最后一个是数字队列中的第几个？
*/
public class Count3Quit2
{
public static void main(String[] args)
{
KidCircle kc = new KidCircle(500);
int num = 0;
Kid k = kc.first; //从第一个开始数数
while (kc.count > 1)
{
num++; //数数
if (num == 2) // 从0开始的，数到2就是第三个数字了
{
kc.delete(k); //删除当前的k
num = 0; //重新数数
}
k = k.right; //k右孩子赋给k
}
System.out.println(kc.first.id); // 打印最后的一个孩子的id
}
}
class Kid
{
int id = 0; // 孩子号码
Kid left; // 左边的孩子
Kid right; // 右边的孩子
}
class KidCircle
{
int count = 0;
Kid first;
Kid last;
// 构造函数，构造n个孩子围成的圈
public KidCircle(int n)
{
for (int i = 0; i < n; i++)
{
add(); // 调用add方法，循环一次增加一个孩子
}
}
// 添加孩子
public void add()
{
Kid k = new Kid();
k.id = count;
if (count <= 0)
{
first = k; // 只有一个孩子
last = k;
k.left = k;
k.right = k;
}
else
{
last.right = k; // 从最后的节点开始，k成为last的右边孩子
k.left = last; // last成为k的左边孩子
k.right = first; // k成为first的右边孩子
first.left = k; // k成为first的左边孩子
last = k; // 这时候k变成了最后一个
}
count++;
}
// 删除孩子
public void delete(Kid k)
{
if (count <= 0) // 没有孩子
{
return;
}
else if (count == 1) // 只剩一个孩子
{
first = last = null;
}
else
{
k.left.right = k.right; // k的右孩子成为 k的左孩子 的右边孩子
k.right.left = k.left; // k的左孩子成为 k的右孩子 的左边孩子
if (k == first) // 如果k是第一个孩子first
{
first = k.right;
}
else if (k == last) // 如果k是第一个孩子last
{
last = k.left;
}
}
count--;
}
}
=====================================================================
我想问的是：
while (kc.count > 1)
{
num++; //数数
if (num == 2) // 从0开始的，数到2就是第三个数字了
{
kc.delete(k); //删除当前的k
num = 0; //重新数数
}
k = k.right; //k右孩子赋给k
}
System.out.println(kc.first.id); // 打印最后的一个孩子的id
}
这段代码表达的意思我不太理解，很难把它想象成一个具体的动态图形。
这是不是说first是KidCircle中一个固定的位置，每count一个Kid，该Kid就向前走一步，后面的跟上。数到3时，first位置的孩子就会被删除？
--------------------编程问答--------------------
--------------------编程问答--------------------
public class Count3Quit {
public static void main(String[] args) {
boolean[] a = new boolean[500];
for (int i = 0; i < a.length; i++) {
a[i] = true;
}
int index;
int count = 0;
int len = a.length;
for (index = 0; len > 1; index++) {
if (a[index] == true) {
count++;
if (count == 3) {
count = 0;
a[index] = false;
len--;
}
}
if (index == a.length - 1) {
index = -1;
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] == true) {
System.out.print(i + 1);
}
}
}
}
这个不是另一种方法么。。。我想问的不是这个。。。
补充：Java , Java SE
