【Java程序】约瑟夫环

今天看视频教程无意间看到了一个数3减1的问题，百度之发现叫约瑟夫环问题，于是写了程序，问题大致描述如下：

一群带有编号的孩子手拉手围成一个圈报数，开始的孩子数1，他右边数2，再右边数3，数到n的孩子out，接着从下一个孩子开始继续数1，数到n的孩子out，如此循环...问最后留下来的孩子是原来的多少号？

我这里用Java写了一个双向回环链表代表围成的圈，其中的Kid是一个链表节点，他有一个左同胞，一个右同胞，还有一个id。双向会还链表定义了添加节点方法add()，删去节点方法delete()；队首孩子firstKid，队尾孩子LastKid，还有表的长度count。

class Kidcircle{

    private int count;

    Kid firstKid;

    Kid LastKid;

    Kidcircle(int num){

        count = 0;

        for(int i=0;i<num;i++){

            add();

        }

    }

    private void add(){

        Kid k = new Kid();

        k.id = count+1;

        if(count==0){

            LastKid = k;

            firstKid = k;

        } else {

            k.left = LastKid;

            k.right = firstKid;

            LastKid.right = k;

            firstKid.left = k;

            LastKid = k;

        }

        count++;

    }

    public void delete(Kid k){

        if(count<=1){

            return;

        } else {

            count--;

            k.left.right = k.right;

            k.right.left = k.left;

            if(k == firstKid){

                firstKid = k.right;

            }else if(k==LastKid){

                LastKid = k.left;

            }

        }

    }

    public int getSize(){

        return count;

    }

}

Kid类如下：

class Kid{

    Kid left;

    Kid right;

    int id;

}

然后main方法中这么写的，我假设的是数到3淘汰一个孩子，然后一共500人：

public class count3quit {

    public static void main(String[] args){

        Kidcircle Kc = new Kidcircle(500);

        Kid currentKid = Kc.firstKid;

        while(Kc.getSize()>1){

            Kc.delete(currentKid.right.right);

            currentKid = currentKid.right.right;

        }

        System.out.println(Kc.firstKid.id);

    }

}

最后结果：436。

有时间还是要多回顾数据结构中的东西。

巴特西

【Java程序】约瑟夫环

最新文章

热门文章