【基础试题】约瑟夫环问题怎么做

【基础试题】约瑟夫环问题

Time Limit:1000MS Memory Limit:65536K
Total Submit:421 Accepted:281

Description

　　有M个人，其编号分别为1－M。这M个人按顺序排成一个圈（如图）。现在给定一个数N，从第一个人开始依次报数，数到N的人出列，然后又从下一个人开始又从1开始依次报数，数到N的人又出列．．．如此循环，直到最后一个人出列为止。

Input

　　输入只有一行，包括2个整数M，N。之间用一个空格分开(0 < n <= m <= 100)。

Output

　　输出只有一行，包括M个整数

Sample Input

　　8 5
Sample Output

　　5 2 8 7 1 4 6 3
Source

xinyue

public class test2 {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("请输入总人数：");

int totalNum = scanner.nextInt();

System.out.print("请输入报数的大小：");

int cycleNum = scanner.nextInt();

yuesefu(totalNum, cycleNum);

}

public static void yuesefu(int totalNum, int countNum) {

// 初始化人数

List start = new ArrayList();

for (int i = 1; i <= totalNum; i++) {

start.add(i);

}

//从第K个开始计数

int k = 0;

    while (start.size() >0) {  
        k = k + countNum;  
        //第m人的索引位置  
        k = k % (start.size()) - 1;  
       // 判断是否到队尾  
        if (k < 0) {  
            System.out.println(start.get(start.size()-1));  
            start.remove(start.size() - 1);  
            k = 0;  
        } else {  
            System.out.println(start.get(k));  
            start.remove(k);  
        }  
    }  
}  

}

写了个比较笨的方法

    public static void showMessage(int m,int n){
        if(n>m)return;
        String info = "";
        for(int i=1;i<=m;i++){
            for (int j = 1; j <= m; j++) {
                info+=j;
            }
        }
        for (int i = 0; i < m; i++) {
            String reslt =info.substring(n-1, n);
            info = info.substring(n)+info.substring(0, n-1);
            info = info.replaceAll(reslt, "");
            System.out.print(reslt+" ");
        }

    }

 /**
     * 
     * @param n 几只猴
     * @param k 数到几
     * @param begin 从第几只开始
     */
    public static void test(int n, int k, int begin) {

        List<String> list = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            list.add(String.valueOf(i + 1));
        }

        int lastChuju = 0;
        boolean isBegin = true;

        while (list.size() > 1) {
            int size = list.size();

            if (isBegin) {
                isBegin = false;
                lastChuju = k + begin;
            } else {
                lastChuju = lastChuju + k;
            }

            if (lastChuju > size) {
                lastChuju = lastChuju % size;
            }
            lastChuju -= 1;
            System.out.println("猴子出局： " + list.get(lastChuju));
            list.remove(lastChuju);

        }

        System.out.println("猴子大王：" + list.get(0));

    }