首页 > 代码库 > 【Java程序】约瑟夫环
【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程序】约瑟夫环
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。