package test.t20080618;

public class Position {

  /**
   * @param args
   */
  public static void main(String[] args) {
    int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int rem = 5;

    int lastNum = getBestPosition(nums, rem);
    System.out.println(lastNum);
  }

  public static int getBestPosition(int[] allPositions, int removePosition) {

    int index;
    while (true) {
      if (allPositions.length == 1) {
        break;
      }
      // get the position of the element which should be removed
      if (allPositions.length > removePosition) {
        index = removePosition;
      } else {
        index = removePosition;
        while (index > allPositions.length) {
          index = index - allPositions.length;
        }
      }
      // create a temp array to remove element
      int[] temp = new int[allPositions.length - 1];
      System.arraycopy(allPositions, 0, temp, 0, temp.length);

      for (int i = index; i < allPositions.length; i++) {
        temp[i - 1] = allPositions[i];
      }
      allPositions = temp;
      // print the content of the array.
      for (int j = 0; j < allPositions.length; j++) {
        System.out.print(allPositions[j]);
      }
      System.out.println();
    }
    return allPositions[0];
  }

}

************************************
12346789
1234789
123489
12349
1234
234
24
4
4
****************************************

  /**
   * 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();
  }

public class JosephCircle {    
    private class Node {    
        public Node nextnode;    
   
        public boolean flag;    
    }    
   
    private Node[] list;    
   
    public JosephCircle() {    
        list = new Node[30];    
        int i;    
        for (i = 0; i < 30; i++) {    
            Node node = new Node();    
            node.flag = true;    
            if (i > 0) {    
                list[i - 1].nextnode = node;    
            }    
            list[i] = node;    
        }    
        list[i - 1].nextnode = list[0];    
    }    
   
    public void start() {    
        Node node = list[29];    
        for (int i = 0; i < 135; i++) {    
            if ((i+1) % 8 == 0) {   
             node.flag = false;    
                node.nextnode = node.nextnode.nextnode;    
            } else {    
                node = node.nextnode;    
            }    
        }    
    }    
   
    public void print() {    
        Node node = list[29];    
        for (int i = 0; i < 30; i++) {    
            if (node.flag) {    
                System.out.print("#");    
  } else {

        System.out.print("@");    
            }    
            node = node.nextnode;    
        }    
    }    
   
    public static void main(String[] args) {    
        JosephCircle jc = new JosephCircle();    
        jc.start();    
        jc.print();    
    }    
}