小便池算法 - 一個簡單的優化

Question

我是一個編程II的學生和第一次海報第一次海報。很可能是一個非常簡單的問題，讓我的思維時間太長了。

*問題＃3。 這是一個充分研究的事實，廁所中的男性通常更喜歡通過佔據最長空置位置中間的距離來最大化與已經佔據的攤位的距離。例如，考慮十個攤位爲空的情況。

---

第一訪問者將佔據中間位置：

_ _ _ _ _ X _ _ _ _

接下來的遊客將在左側空白區域的中間。

_ _ X _ _ X _ _ _ _

Java編寫一個程序，讀取檔位數，然後在上面當檔位變得充滿，一次一個給定的格式打印出的圖。提示：使用一組布爾值來指示是否佔用了一個檔位。

public class MenStall 
{ 
public static int nextStall(boolean[] stalls) { . . . } 
public static void printStalls(boolean[] stalls) {. . . } 
. . . 
} 

輸出爲檔位數的實施例= 10

_ _ _ _ X _ _ _ _ _

_ _ _ _ X _ _ X _ _

_ X _ _ X _ _ X _ _

_ X _ _ X _ _ _ XX

_ X _ _ _ XX XX _

_ XX _ XX _ XX _

_ XX _ XX _ XXX

_ XX _ XXXXXX

_ XXXXXXXXX

XXXXXXXXXX

我認爲最簡單的方法（對於這個學期已經傳授給我們的編程知識知之甚少）要做到這一點將是通過聲明數組的結束和arr的開始ay作爲變量，通過從最後減去開始併除以2來找到中間值。不幸的是，除此之外，我被卡住了。我對編碼術語不熟悉，所以爲此我表示歉意。我想這會更簡單，以顯示我在嘗試解決這個問題：

public class MenStall 

{ 

public static int position = 0; 
public static int nextStall = 0; 
public static boolean[] stalls = new boolean[10]; 
public static final int TRUE_END = stalls.length; 
public static final int TRUE_START = 0; 
public static int start = TRUE_START; 
public static int end = TRUE_END; 
public static final int TRUE_MID = (TRUE_END - TRUE_START)/2; 
public static int mid = TRUE_MID; 

public static int nextStall(boolean[] stalls) 
{ 
    if (position == 0) 
    { 
     nextStall = mid; 
    } 
    else 
    { 
     if (position % 2 == 1) 
     { 
      end = mid; 
      mid = (end - start)/2; 
      nextStall = mid; 
     } 

     else if (position % 2 == 0) 
     { 
      mid = (end - start)/2 + TRUE_MID; 
      nextStall = mid; 
      end = mid; 
      mid = (TRUE_END - TRUE_START)/(int)Math.pow(2,position); 

     } 
    } 

    position++; 
    return nextStall; 
} 

public static void printStalls(boolean[] stalls) 
{ 
    String[] s1 = new String[stalls.length]; 

    while (position < stalls.length) 
    { 
     nextStall(stalls); 
     stalls [nextStall] = true; 
     for (int i = 0; i < stalls.length; i++) 
     { 
      if(stalls[i] == true) 
      { 
       s1[i] = "x"; 
      } 
      else 
      { 
       s1[i] = "_"; 
      } 
     } 
    System.out.println(Arrays.toString(s1)); 
    }  
} 

public static void main(String[] args) 
{ 
    printStalls(stalls); 
} 

} 

走向nextStall方法的盡頭，我是非常簡單，只是與數字打從我如何卡住了。我當然付出了我最認真的努力，甚至不得不請求教授進行延期，但我不能在我的生活中弄清楚這一點。任何指導將不勝感激。謝謝！

Answer 1

在我看來，使用BitSet它更簡單比boolean[]陣列BitSet有預定義的方法nextSetBit返回（如它的名字一樣）下一組位。我認爲，分治策略對你的任務來說是不必要的。這個問題是可以解決這樣的：

public static void main(String[] args) { 
    int numStalls = 10; // get it from user input if you like 
    BitSet bs = new BitSet(); 
    // set the leftmost and the rightmost bits (which represent walls) 
    bs.set(0); 
    bs.set(numStalls+1); 
    // now we have 10 bits gap, which represent stalls 
    // like this: X__________X 
    for(int i=0; i<numStalls; i++) { 
     bs.set(nextStall(bs)); 
     printStalls(bs); 
    } 
} 

public static int nextStall(BitSet bs) { 
    int bestPos = 0, maxDist = bs.nextSetBit(0); 
    // iterate over the set bits 
    for(int pos = maxDist; pos != -1; pos = bs.nextSetBit(pos+1)) { 
     int dist = bs.nextSetBit(pos+1) - pos; 
     // track the position of the stall with biggest gap on the right 
     if(dist > maxDist) { 
      maxDist = dist; 
      bestPos = pos; 
     } 
    } 
    // return the position on the middle of the best gap 
    return bestPos+maxDist/2; 
} 

public static void printStalls(BitSet bs) { 
    StringBuilder sb = new StringBuilder(); 
    // Iterate over all the bit positions except the walls 
    // walls have positions 0 and bs.length() 
    for(int i=1; i<bs.length()-1; i++) { 
     sb.append(bs.get(i) ? "X" : "_"); 
    } 
    System.out.println(sb); 
} 

如果你的Java-8是允許的，該解決方案可以更短：

public static int nextStall(BitSet bs) { 
    // Find the position of the stall (or wall) 
    // For which the next stall/wall is the most distant 
    // bs.stream() returns stream of positions of the set bits 
    int pos = bs.stream().boxed() 
       .max(Comparator.comparingInt(v -> bs.nextSetBit(v+1) - v)).get(); 
    // Return the middle position in the gap 
    return (pos+bs.nextSetBit(pos+1))/2; 
} 

public static void printStalls(BitSet bs) { 
    // Iterate over all the bit positions except the walls 
    // walls have positions 0 and bs.length() 
    System.out.println(IntStream.range(1, bs.length() - 1) 
      .mapToObj(idx -> bs.get(idx) ? "X" : "_").collect(Collectors.joining())); 
}