有500个小朋友拉成一个圆圈，从其中一个小朋友开始依次编号1－500，从1号小朋友开始循环1－3报数，数到3的小朋友就退出。编写一个Java应用程序，计算出最后一个小朋友的号码是多少？
------解决方案--------------------------------------------------------
- Java code
package com.test.csdn;public class Count3Quit { public static void main(String[] args) { boolean[] persons = new boolean[500]; for (int i = 0; i < persons.length; i++) { persons[i] = true; } // 剩下的人数 int leftCount = persons.length; // 计数器 int curCount = 0; // 当前索引 int index = 0; while (leftCount > 1) { if (persons[index] == true) { curCount++; if (curCount == 3) { leftCount--; persons[index] = false; curCount = 0; } } index++; if (index == persons.length) { index = 0; } } for (int i = 0; i < persons.length; i++) { if (persons[i] == true) { System.out.println("最后一位的编号为: " + (i + 1)); } } }}
------解决方案--------------------------------------------------------
明明就是约瑟夫问题
- Java code
class Josephus { public static int[] arrayOfJosephus(int number, int per) { int[] man = new int[number]; for (int count = 1, i = 0, pos = -1; count <= number; count++) { do { pos = (pos + 1) % number; // 环状处理 if (man[pos] == 0) i++; if (i == per) { // 报数为3了 i = 0; break; } } while (true); man[pos] = count; } return man; } public static void test() { int[] man = Josephus.arrayOfJosephus(500, 3); int alive = 3; System.out.println("约琴夫排列："); for (int i = 0; i < man.length; i++) System.out.print(man[i] + " "); System.out.println("\nL表示3个存活的人要放的位置："); for (int i = 0; i < man.length; i++) { if (man[i] > alive) System.out.print("D"); else System.out.print("L"); if ((i + 1) % 5 == 0) System.out.print(" "); } System.out.println(); }}