/** * 数三退一 * @author Lei * @version 创建时间:2009-8-17 上午11:13:18 */public class Count3Quit { public static void main(String[] args) { KidCircle kc = new KidCircle(500); int kidNumber = 0; Kid kid = kc.first; while(kc.count > 1) { kidNumber ++; if(kidNumber ==3) { kidNumber = 0; kc.delKid(kid); } kid = kid.rightKid; } System.out.println(kc.first.id); }}
class Kid { int id; Kid leftKid;//左边的人 Kid rightKid;//右边的人}
class KidCircle { int count = 0; Kid first, last;//第一个人和最后一个人 public KidCircle(int kidNumber) { for(int i = 0; i< kidNumber; i ++) { addKid(); } } public void addKid() { Kid kid = new Kid(); kid.id = count; if(count <= 0) { first = kid; last = kid; kid.leftKid = kid; kid.rightKid = kid; } else { last.rightKid = kid; kid.leftKid = last; kid.rightKid = first; first.leftKid = kid; last = kid; } count ++; } public void delKid(Kid kid) { if(count <= 0) { return; }else if(1 == count) { first = last = null; } else { kid.rightKid.leftKid = kid.leftKid; kid.leftKid.rightKid = kid.rightKid; if(first == kid) { first = kid.rightKid; } else if(last == kid) { last = kid.leftKid; } } count --; }}