約瑟夫環(huán)問(wèn)題

已知 100 圍坐在一張圓桌周?chē)?。從編號?1 的人開(kāi)始報數，數到 m 的那個(gè)人出列；他的下一個(gè)人又從 1 開(kāi)始報數，數到 m 的那個(gè)人又出列；依此規律重復下去，直到圓桌周?chē)娜松儆?m 個(gè)數，輸出圓桌上人的原始編號。

寫(xiě)了個(gè)很挫的遞歸算法(也可以改成循環(huán)，懶得改),然后 case 是全部跑通過(guò)了。

編程答案

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int m = in.nextInt();
            if (m <=1 || m>=100){
                System.out.println("ERROR!");
                continue;
            }
            Map<Integer, Integer> numList = new HashMap<>();
            for (int i=1;i<=100;i++){
                numList.put(i, i);
            }
            count(numList, m, 1, numList.size());
        }
    }

    private static void count(Map<Integer, Integer> numList, int m, int step, int maxSize){
        if (maxSize < m){
            // 打印結果
            StringBuilder sb = new StringBuilder();
            for (Integer i =1;i<= maxSize;i++){
                sb.append(numList.get(i)).append(",");
            }
            System.out.println(sb.toString().substring(0,sb.lastIndexOf(",")));
            return;
        }
        int s = 1;
        for (int i=1;i<= maxSize;i++){
            if (step == m){
                step = 1;
                continue;
            }
            numList.put(s, numList.get(i));
            step ++;
            s ++;
        }
        count(numList, m, step, s-1);
    }
}

最后祝我等到華為面試，并且面試順利。