小蛋糕奶蛋糊沼泽拼图

我正在寻找最佳的策略为下面的谜题。

作为新的仙女王，你有责任绘制王国的乳蛋糕沼泽。
沼泽覆盖在空灵的薄雾中，散布着各种各样的乳蛋糕。
你可以在沼泽中发送你的小精灵，指示在每个点上飞低或高。
如果一个小精灵在蛋挞上猛扑过来，它会分心并且不会完成它的序列。由于雾太浓，所以你知道的是小精灵是否到达另一边。

在编码方面..

bool flutter(bool[size] swoop_map);

这将返回一个精灵是否为退出俯冲给定的顺序。

最简单的方法是只传递一次序列。这揭示了“大小”尝试的所有奶油岛。
我宁愿什么成正比，蛋奶的数量 - 但有样序列问题：

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

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

来源

2009-05-21 caffiend

这些架次是自适应还是非自适应？也就是说，后期小精灵的飞行计划能否取决于早期的结果？另外，你可以期望的最低点是log_2（size）来找到一个奶油蛋糕。 – Dave 2009-05-21 19:00:14

是的，如果可以减少总数，鼓励适应性的架次。 – caffiend 2009-05-21 19:11:30

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

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; 
}

用简单的英语，它的蛋奶地图，一次一个的每个元素调用扑。如果它没有找到奶油蛋糕，下一次调用将会是前一次调用的两倍。这有点像二分搜索，除了在一个方向上，因为它不知道它正在搜索多少项目。我不知道这是多高效。

来源

2009-05-21 18:54:21 Brian

布赖恩的第一个分治法在以下意义上是最优的：存在一个常数C，使得在n个平方和最多k个蛋格的所有沼泽中，没有算法的最坏情况比C好多于C倍Brian的。 Brian的算法使用O（k log（n/k））飞行，其在常数因子log2（n选择k）= log2（（n/k）^ k）= k欧米茄的信息论下界内k log（n/k））。（你需要像k < = n/2这样的假设来使最后一步严格，但是在这一点上，我们已经达到了O（n）次航班的最大值。）

为什么Brian的算法只使用O （k日志（n/k））航班？在递归深度i，它至多使得最小（2^i，k）航班。 0的总和为0（k）。 log2（k）<的总和为log2（n）= log2

来源

2009-05-21 19:40:50 Dave

小蛋糕奶蛋糊沼泽拼图

回答

相关问题