在蛋羹沼泽之谜小妖精

Question

（与感谢富布拉德肖）

我在寻找以下拼图最优策略。

由于新仙王，这是你的责任，映射王国的蛋奶沼泽。结果 沼泽被覆盖在一个空灵的雾气，要用软冻的岛屿散落各处。结果 您可以在沼泽发送您的小精灵，并指示飞高或低，在每一个点。点击 如果一个精灵在蛋羹猛扑下来，这将是分心，将无法完成其序列。 由于雾是那么厚，你知道是一个小精灵是否得到了对方与否。

在编码方面..

bool flutter( bool[size] swoop_map ); 

这将返回一个小精灵是否退出用于俯冲的给定序列。

最简单的方法是在序列通过与仅一举。这表明在“大小”尝试所有蛋奶岛屿。结果 我宁愿东西成正比蛋羹的数量 - 但与样序列的问题：

     C......C     (that is, custards at beginning and end) 

链接到其他形式的这个难题的将受到欢迎以及。

Answer 1

这让我觉得分而治之的。也许这样的事情（这是略微沙哑的伪代码可能有栅栏后的错误等。）：

retval[size] check()
{
   bool[size] retval = ALLFALSE;
   bool[size] flut1 = ALLFALSE;
   bool[size] flut2 = ALLFALSE;
   for (int i = 0; i < size/2; ++i) flut1[i] = TRUE;
   for (int i = size/2; i < size; ++i) flut2[i] = TRUE;
   if (flutter(flut1)) retval[0..size/2] = <recurse>check
   if (flutter(flut2)) retval[size/2..size] = <recurse>check
}

在简单的英语，它在乳蛋糕地图的每个半呼叫扑。如果有一半返回假的，整个半没有蛋奶。否则，一半一半有采用递归算法。我不知道是否有可能做的更好。然而，该算法是种跛当沼泽主要是乳蛋糕。

观二：

int itsize = 1
bool[size] retval = ALLFALSE;
for (int pos = 0; pos < size;)
{
    bool[size] nextval = ALLFALSE;
    for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) nextval[pos2] = true;
    bool flut = flutter(nextval)
    if (!flut || itsize == 1)
    {
        for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) retval[pos2] = flut;
        pos+=itsize;
    }
    if (flut) itsize = 1;
    if (!flut) itsize*=2;
}

在简单的英语，它蛋羹地图，一次一个的每个元素调用扑。如果它没有找到蛋糊，下一个电话将是两倍多的元素以前调用。这是一种像二进制搜索，但只在一个方向，因为它不知道它有多少项目寻找。我不知道如何有效的，这是。

Answer 2

Brian的第一分而治之算法是最佳在以下意义：存在一个常数C使得在具有n个方块和至多为k蛋羹所有沼泽，没有算法具有比Brian的比C倍以上更好的最坏情况。 Brian的算法使用O（ķ的log（n / k））的航班，这是一个常数因子内的信息理论下限的log 2（N个选择K）> = LOG2（（N / K）^ K）= K欧米茄（ ķ日志（N / K））。 （您需要一个像k时的假设<= N / 2，使最后一步严谨，但在这一点上，我们已经达到了最大的O（n）的航班。）

为什么Brian的算法只使用Ø（K的log（n / k））的航班吗？在递归深度I，它使至多分钟（2 ^ I，K）的航班。为0的总和<= I <= LOG2（k）为O（K）。对于LOG2（k）的总和。