奶油沼泽拼图中的小精灵
（感谢 Rich Bradshaw）
我正在寻找解决以下难题的最佳策略。
作为新的仙王，你有责任绘制王国的奶油沼泽地图。
沼泽被一层空灵的薄雾覆盖，到处都是蛋奶冻岛。
您可以发送小精灵穿过沼泽，并附有在每个点低飞或高飞的指示。
如果小精灵从蛋奶冻上俯冲下来，它会分心而无法完成其动作。 由于雾气太浓，你只能知道小精灵是否到达了另一边。
用编码术语来说……
bool flutter( bool[size] swoop_map );
这将返回小精灵是否在给定的俯冲序列中退出。
最简单的方法是仅一次传递序列。 这揭示了所有蛋奶群岛的“大小”尝试。
我更喜欢与蛋奶冻数量成比例的东西 - 但对序列有问题，例如：
C......C (that is, custards at beginning and end)
也欢迎指向此谜题其他形式的链接。
(With thanks to Rich Bradshaw)
I'm looking for optimal strategies for the following puzzle.
As the new fairy king, it is your duty to map the kingdom's custard swamp.
The swamp is covered in an ethereal mist, with islands of custard scattered throughout.
You can send your pixies across the swamp, with instructions to fly low or high at each point.
If a pixie swoops down over a custard, it will be distracted and won't complete its sequence.
Since the mist is so thick, all you know is whether a pixie got to the other side or not.
In coding terms..
bool flutter( bool[size] swoop_map );
This returns whether a pixie exited for a given sequence of swoops.
The simplest way is to pass in sequences with only one swoop. That reveals all custard islands in 'size' tries.
I'd rather something proportional to the number of custards - but have problems with sequences like:
C......C (that is, custards at beginning and end)
Links to other forms of this puzzle would be welcome as well.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这让我想到分而治之。 也许是这样的（这是稍微损坏的伪代码。它可能有栅栏柱错误等）：
用简单的英语来说，它在蛋奶冻地图的每一半上调用颤动。 如果任何一半返回 false，则整个一半都没有蛋奶冻。 否则，一半的算法会递归应用。 我不确定是否可以做得更好。 然而，如果沼泽主要是蛋奶冻，这个算法就有点蹩脚了。
想法二：
用简单的英语来说，它在蛋奶冻图的每个元素上调用颤动，一次一个。 如果找不到蛋奶冻，下一次调用的元素数量将是上一次调用的两倍。 这有点像二分搜索，只不过只在一个方向上，因为它不知道要搜索多少项。 我不知道这有多有效。
This makes me think of divide and conquer. Maybe something like this (this is slightly broken pseudocode. It may have fence-post errors and the like):
In plain English, it calls flutter on each half of the custard map. If any half returns false, that whole half has no custard. Otherwise, half of the half has the algorithm applied recursively. I'm not sure if it is possible to do better. However, this algorithm is kind of lame if the swamp is mostly custard.
Idea Two:
In plain English, it calls flutter on each element of the custard map, one at a time. If it does not find custard, the next call will be on twice as many elements as the previous call. This is kind of like binary search, except only in one direction since it does not know how many items it is searching for. I have no idea how efficient this is.
Brian 的第一个分而治之算法在以下意义上是最优的：存在一个常数 C，使得在所有具有 n 个正方形和最多 k 个蛋奶冻的沼泽中，没有算法的最坏情况比 Brian 的算法好 C 倍以上。 Brian 的算法使用 O(k log(n/k)) 次飞行，其在常数因子内 log2(n 选择 k) >= log2((n/k)^k) = k Omega 的信息论下界(k log(n/k))。 （你需要像 k <= n/2 这样的假设来使最后一步变得严格，但此时，我们已经达到了 O(n) 次飞行的最大值。）
为什么 Brian 的算法只使用 O(k log (n/k)) 航班？ 在递归深度 i 处，它最多进行 min(2^i, k) 次飞行。 0 <= i <= log2(k) 的总和为 O(k)。 log2(k) < 的总和 i <= log2(n) 是 k (log2(n) - log2(k)) = k (log2(n/k))。
Brian's first divide and conquer algorithm is optimal in the following sense: there exists a constant C such that over all swamps with n squares and at most k custards, no algorithm has a worst case that is more than C times better than Brian's. Brian's algorithm uses O(k log(n/k)) flights, which is within a constant factor the information-theoretic lower bound of log2(n choose k) >= log2((n/k)^k) = k Omega(k log(n/k)). (You need an assumption like k <= n/2 to make the last step rigorous, but at this point, we've already reached the maximum of O(n) flights.)
Why does Brian's algorithm use only O(k log(n/k)) flights? At recursion depth i, it makes at most min(2^i, k) flights. The sum for 0 <= i <= log2(k) is O(k). The sum for log2(k) < i <= log2(n) is k (log2(n) - log2(k)) = k (log2(n/k)).