我是一名编程 II 学生，也是第一次发帖者。一个很可能是一个非常简单的问题却让我困惑了太久。

*问题#3。 一个经过充分研究的事实是，在洗手间的男士通常更喜欢通过占据最长的未占用位置序列的中间来最大化他们与已占用隔间的距离。例如，考虑十个摊位是空的情况。

第一个访客会占据中间位置:

_ _ _ _ _ X _ _ _ _

下一位访客将在左侧空白区域的中间。

_ _ X _ _ X _ _ _ _

用 Java 编写一个程序，读取摊位的数量，然后在摊位填满时以上面给出的格式打印图表，一次一个。提示:使用 boolean 值数组来指示摊位是否有人。

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

摊位数量 = 10 的输出示例

_ _ _ _ X _ _ _ _

_ _ _ _ X _ X _ _

_ X _ _ X _ _ X _ _

_ X _ _ X _ _ X X _

_ X _ _ X X _ X X _

_ X X _ X X _ X X _

_ X X _ X X _ X X X

_ X X _ X X X X X X

_ X X X X X X X X X

X X X X X X X X X X

我假设最简单的方法(本学期传授给我们的编程知识很少)是通过将数组的结尾和数组的开头声明为变量，并找到中间点通过从结尾减去开头并除以二。不幸的是，除此之外我被困住了。我不太精通编码术语，为此我深表歉意。我想展示我在解决这个问题上的尝试会更简单:

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 方法的最后，我几乎只是在玩弄我陷入困境的数字。我当然付出了最大的努力，甚至不得不向教授申请延期，但我这辈子都想不通。任何指导将不胜感激。谢谢!

最佳答案

在我看来，使用 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()));
}

关于java - 小便器算法 - 一个简单的优化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32645046/