java - 当n个人围成一圈时寻找幸存者

Question

嗨，我遇到了这个问题并试图解决这个问题

花一点时间想象一下您在一个有 100 张椅子围成一圈的房间里。这些椅子按从一到一百的顺序编号。 在某个时间点，坐在#1 椅子上的人将被告知离开房间。坐在#2 椅子上的人将被跳过，坐在#3 椅子上的人将被告知离开。接下来是 6 号椅子上的人。换句话说，一开始会跳过 1 个人，然后是 2、3、4.. 等等。这种跳跃模式将继续绕一圈，直到只剩下一个人……幸存者。请注意，当人离开房间时，椅子会被移除。编写一个程序来找出幸存者坐在哪张椅子上。

我取得了良好的进展，但遇到了一个问题，在计数达到 100 后，不知道如何从这里迭代，任何人都可以帮助我，这是我的代码

import java.util.ArrayList;

public class FindSurvivor {

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

private static int getSurvivorNumber(int numChairs) {
    // Handle bad input
    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);
    }


    int chairIndex = 0;
    int lr =0;
    while (chairs.size() > 1) {
        chairs.remove(lr);
        chairIndex+=1;
        System.out.println(lr+" lr, size "+chairs.size()+" index "+chairIndex);
        if(lr==chairs.size()||lr==chairs.size()-1)
            lr=0;
        lr = lr+chairIndex;
        printChair(chairs);
        System.out.println();
    }

    return chairs.get(0);
}

public static void printChair(ArrayList<Integer> chairs){
    for(int i : chairs){
        System.out.print(i);
    }
}
}

Answer 1

答案是 31。以下是三种不同的实现

var lastSurvivor = function(skip, count, chairs) {
    //base case checks to see if there is a lone survivor
    if (chairs.length === 1)
        return chairs[0];
    //remove chairs when they are left/become dead
    chairs.splice(skip, 1);
    //increment the skip count so we know which chair
    //to leave next. 
    skip = (skip + 1 + count) % chairs.length;
    count++;
    //recursive call
    return lastSurvivor(skip, count, chairs);
};

/** TESTS *******************************************************************
----------------------------------------------------------------------------*/

var result = lastSurvivor(0, 0, chairs);
console.log('The lone survivor is located in chair #', result);
// The lone survivor is located in chair # 31




/** ALTERNATE IMPLEMENTATIONS ***********************************************
-----------------------------------------------------------------------------

/* Implemenation 2 
-----------------*/

var lastSurvivor2 = function(chairs, skip) {
    skip++;
    if (chairs === 1)
        return 1;
    else
        return ((lastSurvivor2(chairs - 1, skip) + skip - 1) % chairs) + 1;
};

/** Tests 2 *******************************************************************/

var result = lastSurvivor2(100, 0);
console.log('The lone survivor is located in chair #', result);
// The lone survivor is located in chair # 31



/* Implemenation 3 
------------------*/

var chairs2 = [];
for (var i = 1; i <= 100; i++)
    chairs2.push(i);

var lastSurvivor3 = function(chairs, skip) {
    var count = 0;
    while (chairs.length > 1) {
        chairs.splice(skip, 1);
        skip = (skip + 1 + count) % chairs.length;
        count++;
    }
    return chairs[0];
};

/** Tests 3 *******************************************************************/

var result = lastSurvivor3(chairs2, 0);
console.log('The lone survivor is located in chair #', result);
// The lone survivor is located in chair # 31