我有以下问题我要解决：
连续有6杯（例如1至6杯）。在其中一个杯子下是一个球（我不知道哪一个）。我可以举起杯子，看看球是否在那里。如果是，我赢了。如果不是不是，球就会从目前的位置转移到立即的左或右（因此从杯4到3杯或5杯或5杯。5）。球必须移动，它不能保持到位。
问题是：如果您使用最佳策略，则在何种"杯赛升降机"之后，您会知道球的位置。
目前，我对 a 策略感到困惑，最坏的情况是6个升降机。请注意，最终的升降机，"证明"球所在的位置，不需要完成。我的问题是：是否有更好的"最坏情况"算法？如果没有，我该如何证明这是最好的算法？
我当前的策略。我们假设球开始时均匀的杯子（2、4或6）。最坏情况的一步是如下。
提升1 ：举起杯号2。球不在。根据我们的假设，球会移至奇怪的杯子，但是它不能移至杯1（因为它必须起源于2杯，并且不存在）
）提升2 ：提升杯数字3。我不能以下1岁以下（见上文），它不到3岁以下，并且假设它在奇数杯下。这意味着现在在杯5下，因此必须移至4或6杯。
。提升3：举升杯4，球不在。这意味着它一定已经移至6号杯，所以在下一步，它必须移至杯赛数字5
提升4：举升杯5，球不在。这是剩下的唯一可能性，所以我们猜测它始于均匀的杯子。结果，它是现在在一些甚至杯子下，下一步将移至奇怪的杯子。我们现在正在使用相同的过程，但相反。
提升5：提升杯5号（再次）。球不在。通过新的假设，球现在将移至2或4杯（再次，它不能移至6杯，因为它不到5岁）。
。举升6：举升杯数字4。因此，我们知道杯子在哪里（即使我们不执行2号杯的最后举起）。
您的算法有一个缺陷。如果球以奇数的位置开始，则在偶数动作后将其最终处于奇数位置。您的算法假定六个动作后它处于均匀位置。那永远不会起作用。此外，您的升降顺序无法积极地确定球的位置。
例如，想象一下球从杯赛＃1开始。按照您的升降顺序，可以进行以下操作。
- 升降杯2.球移至杯2。
- 举升杯3.球移至杯1。
- 举升杯4.球移至杯2。
- 举升杯5.球移至杯1。
- 提升杯5（再次）。球移至2。
- 举升杯4.球移至杯1。
步骤6之后，球可以从杯2移至1杯或杯3。因此，您不知道它在哪里。
如果要用程序解决问题，请构造顶点是可能是可能位置的位置的图，而边缘是杯升降机露出球。然后，解决方案是最短的路径，从您想要的任何开始状态到具有2个可能的杯子升降机的任何状态。（由于允许在球移动之前"知道"球的规则，以a结束的终止条件有点混乱。
）。此代码非常粗糙，但是使用DFS查找最短路径，然后漂亮打印解决方案。它确认在最坏情况下需要6杯升降机才能找到球，实际上找到与您完全相同的解决方案。
输出为：
$ python cups.py
the ball can be under cups: 1,2,3,4,5,6
lift cup 2
the ball can be under cups: 2,3,4,5,6
lift cup 3
the ball can be under cups: 1,3,4,5,6
lift cup 4
the ball can be under cups: 2,4,5,6
lift cup 5
the ball can be under cups: 1,3,5
lift cup 5
the ball can be under cups: 2,4
lift cup 2
代码是：
import collections
N = 6
MASK = (1<<N)-1
def bitcount(n):
if n == 0: return 0
return 1 + bitcount(n & (n-1))
def shifts(c):
return ((c << 1) | (c >> 1)) & MASK
def adjacent(c):
if bitcount(c) == 2:
yield min(i for i in xrange(N) if (c>>i)&1), 0
return
for i in xrange(N):
if (c>>i)&1:
yield i, shifts(c & ~(1<<i))
def bfs(edges, start):
prev = {start: None}
q = collections.deque([start])
while q:
x = q.popleft()
for y in edges[x]:
if y in prev: continue
prev[y] = x
q.append(y)
return prev
def path(x, prev):
if x is None: return []
return path(prev[x], prev) + [x]
edges = dict((v, [n for _, n in adjacent(v)]) for v in xrange(2**N))
best_path = path(0, bfs(edges, MASK))
for pi, p in enumerate(best_path[:-1]):
print 'the ball can be under cups: %s' % ','.join(str(i+1) for i in xrange(N) if (p>>i)&1)
print 'lift cup %d' % list(c+1 for c, n in adjacent(best_path[pi]) if n == best_path[pi+1])[0]
我认为这个谜语接近您提出的问题。但是，它包含5个框而不是6。无论如何，您仍然可以检查他们提出的解决方案并将其策略与您的策略进行比较。
希望它有帮助。