最近找實習, 在做Test Assignment時遇到了這麼道題, 就順便記錄下來:
說, 有1到100共100個數, 擺成一個圈. 從1開始, 每隔1, 2, 3, 4 ... 個數拿走一個數, 一直循環, 最後剩下幾? 具體的講就是一開始(隔0個數)把 1 拿走, 隔1個數(2)把3拿走, 再隔2個數(4, 5)把6拿走, 再隔3個數(7, 8, 9)把10拿走. 第一圈數到100之後接著從2開始數, 直到最後剩下1個數為止, 請問最後剩下幾? 如果是1到n呢?
1 public static int selectNumber(int n) {
2
3 int result = -1;
4 ArrayList<Integer> nums = new ArrayList<Integer>();
5 int index = 0; // this variable is used to remove numbers from list
6 int count = 0; // count is used to count which numbers should be remove
7 int pIndex = 0; // this is used to record previous index
8
9 // generate a list contains numbers from 1 to n
10 for(int i = 1; i <= n; i++) {
11 nums.add(i);
12 }
13
14 while(nums.size() > 1) {
15
16 while(index < nums.size()) {
17 nums.remove(index);
18 count++;
19 pIndex = index;
20 index += count;
21 }
22
23 index = count - (nums.size() - pIndex);
24
25 while(index > nums.size() - 1) {
26 index = index - nums.size();
27 }
28 }
29
30 result = nums.get(0);
31 return result;
32 }
33
34 public static void main(String[] args) {
35 int surviver = selectNumber(100);
36 System.out.println("The surviver is: " + surviver);
37 }
以上就是我的解決方案, 最後留下的數是31
