/**
   * N个人围成一圈依次从1报数，报到rem的人出局，下一个人重新从1开始报数，直至剩下一个人。
   *
   * @param N 总人数
   * @param rem 数到rem的人出局（注：从1开始数）
   * @param printable 标示是否打印中间过程
   * @return
   */
  public static int getBestPosition2(int N, int rem, boolean printable){
    int positions[] = new int[N];
    for(int i = 0; i < N; i++){
      positions[i] = i + 1;
    }
    int bestNumber = 1;
    int count = 0;
    while(true){
      for(int i = 0; i < N; i++){
        if(positions[i] != 0){//跳过标记为0的数
          count++;
        }
        if(count == rem){
          positions[i] = 0; //出局的数设定为0作标记
          count = 0;
          if(printable){
            print(i, positions);
          }
        }
      }
      if(count == 1){
        for (int i = 0; i < N; i++){ // 从结果中取出最好的数
          if(positions[i] != 0){
            bestNumber = positions[i];
          }
        }
        break;
      }
    }
    return bestNumber;
  }

  public static int getBestPosition(int N, int rem, boolean printable){
    List<Integer> positions = new ArrayList<Integer>();
    for(int i = 0; i < N; i++){
      positions.add(i+1);
    }

    int toRemove = (rem - 1) % N; //下标从0开始
    positions.remove(toRemove);
    if(printable){
      print(toRemove, positions);
    }
    int removed = 1;
    while(removed < N - 1){
      toRemove += rem - 1;//继续数数，减1是因为数据减少了一个
      toRemove %= positions.size();//进行规整
      positions.remove(toRemove);
      removed++;
      if(printable){
        print(toRemove, positions);
      }
    }
    return positions.get(0);
  }

  public static void print(int toRemove, int[] nums) {
    System.out.print((toRemove+1)+" : ");
    for (int i = 0; i < nums.length; i++){
      if(nums[i] == 0)continue;
      System.out.print(nums[i]);
    }
    System.out.println();
  }

  public static void print(int toRemove, List<Integer> list) {
    System.out.print((toRemove+1)+" : ");
    for (int pos : list){
      if(pos == 0)continue;
      System.out.print(pos);
    }
    System.out.println();
  }