0

我正在尝试使用 ArrayList 和 for 循环来解决 Josephus 问题。我在我的 circle.size for 循环中创建了一个无限 for 循环，但我无法推断出我的代码的哪一部分导致它发生。

public class project1 {
  public static int Josephus (int n, int k){                                     
    ArrayList<Integer> circle = new ArrayList<Integer>();                       
    for (int p = 1; p <= n; p++) {                                              
      circle.add(p);                                                            
    }
    System.out.println("There are " + n + " people in the circle.");            
    System.out.println(circle);                                                 

    ArrayList<Integer> kill_order = new ArrayList<Integer>();                   
    for (int index=1; circle.size()!=1; index++){                               
      if (circle.size() > 1){                                                   
        index = (index + k - 1) % circle.size();                                
        kill_order.add(index);                                                  
        circle.remove((Integer)index);
        System.out.println(kill_order);
      } else if (circle.size()==1){
        System.out.println("Execution Order: " + kill_order + " ");
        System.out.println(kill_order);
        index = 1;
      }
    }
    return circle.get(0);
  }

  public static void main(String[] args) {
    System.out.println("You should sit in seat " + Josephus(7, 2) + " if you want to survive!");
  }
}
4

2 回答 2

4

我认为问题与这行代码有关 circle.remove((Integer)index);

如果您替换circle.remove(index)为程序结束而没有任何无限循环。

如果调用该方法circle.remove((Integer) index)，它会使用该值搜索数组中的元素，该方法circle.remove(index)会删除指定索引处的元素。

有关更多详细信息，请参阅 javadoc remove(int index) remove(Object o)

于 2021-02-08T20:30:00.707 回答
1

主循环的每次下一次迭代看起来像：

循环开始处的索引 分配新值后的索引 圆阵列
1 2 1、3、4、5、6、7
3 4 1、3、5、6、7
5 1 3、5、6、7
2 3 5、6、7
4 2 5, 6, 7 - 它不能删除值 2 并且数组的大小不是 1
3 1 5、6、7
2 0 5、6、7
1 2 5、6、7
3 1 5、6、7 - 循环开始重复

所以可能你的算法是错误的，或者你应该删除索引处的元素，而不是按值(circle.remove(index))- 而不将其转换为Integer

于 2021-02-08T20:39:51.267 回答