日期:2014-05-20  浏览次数:20747 次

请教一个java应用程序
有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();
    }
}