java - 幸存者编程挑战

Question

我正在处理如下所示的幸存者问题:这是 source

Complete Question Text: Take a second to imagine that you are in a room with 100 chairs arranged in a circle. These chairs are numbered sequentially from One to One Hundred.

At some point in time, the person in chair #1 will be told to leave the room. The person in chair #2 will be skipped, and the person in chair #3 will be told to leave. Next to go is person in chair #6. In other words, 1 person will be skipped initially, and then 2, 3, 4.. and so on. This pattern of skipping will keep going around the circle until there is only one person remaining.. the survivor. Note that the chair is removed when the person leaves the room.

Write a program to figure out which chair the survivor is sitting in.

下面是我的代码:

public class ChairProblem {

    public static void main(String[] args) {
        System.out.println(getSurvivors(100));
    }

    private static int getSurvivors(int numChairs) {
        if (numChairs < 1) {
            return -1;
        }

        // populate chair array list
        ArrayList<Integer> chairs = new ArrayList<Integer>();
        for (int i = 0; i < numChairs; i++) {
            chairs.add(i + 1);
        }

        // removing all but one elements
        int indexOfChair = 0;
        while (chairs.size() > 1) {
            chairs.remove(indexOfChair);
            indexOfChair++;// skip every other chair
            indexOfChair %= chairs.size();// loop to beginning if necessary
        }

        return chairs.get(0);
    }
}

我的上述方法不会按照要求中的描述逐出#1、#3、#6。谁能帮我解决这个问题？

Answer 1

我的答案是你在 indexOfChair 之后引入第二个变量 count 并初始化为 1。现在在 while 循环中而不是使用 indexOfChair++ 使用 indexOfChair += count; 然后将 count 增加 1。如下所示:

    int indexOfChair = 0;
    int count = 1;
    while (chairs.size() > 1) {
        chairs.remove(indexOfChair);
        indexOfChair += count;// skip the count number of chairs
        count++; //increase the number of chairs to skip by 1
        indexOfChair %= chairs.size();// loop to beginning if necessary
    }