1

我正在尝试使用 java 中的队列来解决 Josephus 问题。输入必须是名称列表（字符串）和整数 k 或马铃薯已通过队列的次数。我需要测试 4 个不同的输入。这就是我到目前为止所拥有的，我从一些随机教程中获得了帮助，但不确定要对此进行编辑以使其正常工作。

 /*Jess Anastasio
  * HW 1
  * Part 2
  */ 

 import java.util.*;
 import java.util.Queue;
    /*pseudocode:
     * int k = amount of people cycled through 
     * before deleted. Need to enter string input
     * of names into queue. Need to cycle through
     * the queue k times and the object at position
     * k will be deleted. 
     * 
     * first: create string array holding names
     * method buildQueue takes the string array 
     * and adds it to a string queue
     * next: Josephus method passes in string queue and
     * int k, 
     */

  public class HotPotato 
  {
   //tester
    public static void main(String[] args) 
     {
    //use an array to save string input of names (4 different inputs)
       String[] a1 = {"Genna", "Bob", "Rob", "Alexa", "Brian", "Frank"};
       String[] a2 = {"Rich", "Taylor", "Jackie", "Jan", "Kim", "Denver"};
       String[] a3 = {"Jess", "Kyle", "Mike", "Carolyn", "Ant", "Ed"};
       String[] a4 = {"Natalie", "Emma", "Olivia", "Joe", "Kitty", "Jenn"};
       System.out.println("First winner is " + Josephus(buildQueue(a1), 5));
       System.out.println("Second winner is " + Josephus(buildQueue(a2), 2));
       System.out.println("Third winner is " + Josephus(buildQueue(a3), 4));
       System.out.println("Fourth winner is " + Josephus(buildQueue(a4), 10));
     }

    // build a queue from an array of string objects
    public static Queue<String> buildQueue(String[] str) 
    {
      Queue<String> Q = new Queue<String>();
      for (int i = 0; i < str.length; i++)
        Q.enqueue(str[i]);

      return Q;
    }

     // Josephus problem using a queue
     public static String Josephus(Queue<String> Q, int k) 
     {
       //if there is nothing in the queue return null
       if (Q.isEmpty()) 
        return null;

       //while the size of the queue is greater than 1
       while (Q.size() > 1) 
       {
         //print out the contents of the queue
         System.out.println(" Queue: " + Q + " k = " + k);
         for (int i = 1; i < k; i++)
           Q.enqueue(Q.dequeue());
         String e = Q.dequeue();
         //update user on who was deleted 
         System.out.println(" " + e + " is out");
       }
       return Q.dequeue();
     }

  }

这不起作用..有人可以提供建议吗？

4

1 回答 1

0

我不确定你的 while 循环。这就是我想出的 - this.potentialVictims 是一个队列

public String findSurvivor(int k) { 

  int pos=1;
  while (this.potentialVictims.size() > 1) {
    String person=this.potentialVictims.poll();
    if (pos++ %k != 0) {
            this.potentialVictims.offer(person);
    }
    else {
       System.out.printf("%s is out\n",person);
    }
  }
  if (this.potentialVictims.size()==1) {
    return this.potentialVictims.poll();
  }
  else {
    return null;
  }
}
于 2014-04-21T03:07:18.360 回答