Java算法之数3退1

方法一： //数3退1： 假设有500个人 手拉手围成一圈 从第一个人开始数 每数到3则退出 求最后剩余的人的原来站的位置 public class TestCount3Quit { public static void main(String [] args) { boolean[] arr = new boolean[500]; for (int i = 0; i < arr.length; i++) { arr[i] = true; } //圈里还剩的人数 int leftCount = arr.length; //计数用 每增加到3 退1 int countNum = 0; //位置 int index = 0; while (leftCount > 1) { if (arr[index] == true) { countNum++; if (countNum == 3) { arr[index] = false;//该位置的人变为false leftCount--;//圈里的人数少1 countNum = 0; //计数从0开始 } } index++; if (index == arr.length) { index = 0;//位置到500后从头开始数 } } //最后将圈里还是true的位置找出来 打印出来 for (int i = 0; i < arr.length; i++) { if (arr[i] == true) { System.out.println(i); } } } }

 

方法二： 面向对象的编程思想

 

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 = 0; 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<=0){ 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 --; } }