我正在处理一个幸存者问题，如下所示：这里是来源
完整的问题文本：花一秒钟想象你在一个房间里，100把椅子排成一个圈。这些椅子按从一到一百的顺序编号。
在某个时间点，坐在1号椅子上的人会被告知离开房间。第二把椅子上的人将被跳过，第三把椅子上的人将被告知离开。接下来是坐在6号椅子上的人。换言之，一开始跳过一个人，然后跳过2、3、4。。等等。这种跳跃的模式会一直绕着圆圈转，直到只剩下一个人。。幸存者。请注意，当人离开房间时，椅子会被取下。
写一个程序来计算幸存者坐在哪把椅子上。
下面是我的代码：
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。有人能帮我吗？
3条答案
按热度按时间fae0ux8s1#
我的答案是你引入第二个变量
count类型int之后indexOfChair并初始化为1。现在在while循环而不是使用indexOfChair++使用indexOfChair += count;然后你增加count1。如下所示：u4dcyp6a2#
您计算要删除的indexofchair时出错。在每次迭代中，最新移除的椅子的位置是lostt。必须保留最新移除的椅子位置，并向其添加递增的indexofchair。
rwqw0loc3#
这个问题类似于约瑟夫问题。使用递归策略可能更容易：进行第一次消元，然后将算法递归地应用于剩余的组。比如：