有两个沙漏：一个需要\(4\)分钟跑完，另一个需要\(7\)分钟。当第一次启动时钟时必须开始测量时，如何精确测量\(9\)分钟？另一个时钟、数秒和猜测是不允许的。您所要做的就是将沙漏翻过来，观察上层室何时变空。转身不应该花任何时间。我们正在寻找的是一个过程，在这个过程中，所期望的时间段的结束只能通过沙漏来识别。
我们将具有\(4\)分钟的时钟称为\(A\) ，将具有\(7\)分钟的时钟称为\(B\) 。最初所有的沙子都在底部。我们通过翻转两个时钟来同时启动它们；从此时起，搜索的\(9\)分钟开始计数。之后，当顶部的时钟变空时，您可以随时进行交易。您不得翻转一个、一个或两个时钟，即使是仍在运行的时钟。你等到下次它用完的时候。不允许停车和标记；空钟可以保持站立状态。解决方案看起来像这样:
- 在\(0\)分钟\(A\)和\(B\)启动。
- 在分钟\(4\) \(A\)为空并被翻转。 \(B\)继续运行不变。
- 在分钟\(7\) \(B\)为空并被翻转。 \(A\)还剩\(1\)分钟。
- 在分钟\(8\) \(A\)为空。在\(B\)中，沙子流下整整\(1\)分钟；因此\(B\)立即又被翻过来。
- 在分钟\(9\) \(B\)为空。您要寻找的时间已到。
在\(8\)分钟\(B\) 。自从它们在\(7\)分钟重新启动以来，流下的沙子数量与在\(1\)分钟内通过瓶颈的沙子数量完全相同。翻转后，只有这一小部分在上面。现在需要\(1\)分钟才能再次滴落。因此，时钟在\(9\)分钟变空，而不是在另一次完整运行之后。所以我们用已经通过的沙子来测量最后一刻的情况。动画展示了这个动作:
翻转运行的沙漏对于一般解决方案也很有用。剩余时间是指沙子仍然需要流经上室的时间。如果满钟的运行时间为\(c\) ，剩余运行时间为\(r\) ，则底部的沙子数量对应于持续时间\(cr\) 。当你把它翻过来时，这个确切的数字就会出现在顶部。如果上腔室事先已满，则随后将是空的，反之亦然。对于部分运行的时钟，新的剩余运行时间为\(r'\):
$$r'=c-r.$$
以前，测量从第一圈开始。这意味着“没有提前时间”：自开始以来的每一分钟都很重要。另一方面，“提前”意味着您可以先准备好时钟，然后再开始所需的时间段。例如，我们启动两个时钟并在\(4\)分钟转动\(A\) 。如果\(B\)在\(7\)分钟变空，我们的测量就开始。如果\(A\)在\(8\)分钟变空，则结束。我们测量了\(1\)分钟；之前的\(7\)分钟不算在内。
现在我们考虑具有正整数运行时间\(a\)和\(b\)的任意沙漏。我们将所需的持续时间称为\(T\) 。如果准备允许的话，可以用这个来测量什么时间？在这里，开始和结束也必须通过空白来识别。因此，您不应该根据自己的感觉在某个时刻开始进行测量。手柄与实际拼图中的手柄保持相同。首先我们显示哪些时间被排除；然后我们将向您展示如何实际测量其余所有内容。
首先让我们使用\(6\)和\(10\)分钟的时钟。两个运行时间都可以被\(2\)整除。因此，沙子可以在心里分成几部分，每一部分都需要\(2\)分钟才能通过。当您将其翻转或等到下一次它为空时，只会再次创建整个部分。因此，所有可观察到的空闲时间相隔偶数分钟。即使您事先准备好时钟，也无法使用它来测量\(3\)分钟的持续时间。
一般来说，令\(g=\gcd(a,b)\)为运行时间的最大公约数。最初剩余的两项都是\(g\)的倍数。当旋转 时\(r\)变为\(ar\)或\(br\) ；两者都可以被\(g\)整除。等待时，经过最小的正剩余时间，也是\(g\)的倍数。这意味着所有空时间及其距离仍然是\(g\)的倍数。因此，可测量的持续时间必须满足\(g\mid T\) ： \(T\)必须能被\(g\)整除。这是否足够还有待观察。
为此，我们让两个时钟一次又一次完全运行，并在每个时钟空了后立即将其翻转。第一个在\(a,2a,3a,\ldots\)个时间单位后变空，第二个在\(b,2b,3b,\ldots\)后变空。我们正在寻找第二个时钟的时间\(mb\)和第一个时钟的较晚时间\(na\) ，两者之间恰好是\(T\) 。如果\(T\)是\(g\)的正倍数，Bézout 引理保证匹配整数\(n,m\) 。您正在寻找的关系是：:
$$na-mb=T.$$
Bézout 提供的数字\(n,m\)最初可以为负数。不能进行负运行。然而，我们可以在不改变时间间隔的情况下增加这两个数字：我们用\(n+kb/g\)和\(m+ka/g\)替换它们，其中\(k\)是一个足够大的正整数。因此，两个时间都偏移相同的量\(kab/g\) ；他们的区别仍然是\(T\) 。因此，两个数字都变为正值，所需时间实际上是在时钟开始之后。
现在您可以计算每个时钟的完整周期。当\(m\)时钟变空时，测量开始；当第一个时钟第\(n\)次变空时，它结束。其间正好有\(T\)个时间单位。准备工作可能需要很长时间。该证明并没有承诺一个特别短的过程。对于\(T=0\)起点和终点重合。这证明了所有非负整数目标：通过准备，当且仅当最大公约数除以持续时间时，才可以测量持续时间:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
此规则不一定适用于第一次开始时就开始测量。例如， \(4\)和\(7\)分钟\(g=1\) ，但在\(1\)分钟后没有时钟为空。所以你看不到这一分钟的结束。上述从\(7\)到\(8\)分钟的测量仅有效，因为准备工作不算在内。因此，这个证明回答了准备之后什么是可能的问题。如果您正在寻找有或没有准备的许可流程，以下系统搜索将会有所帮助。
PHP 脚本会记住剩余运行时间和自测量开始以来已经过去的时间。对于每一个这样的条件，都尝试一下 \(4\) 可能性：没有时钟，只有第一个，只有第二个，或者两者都翻转。然后它会等待，直到下次清空。价值 \(-1\) 表示准备；条目 start 设置测量时间 \(0\). 已知情况不会重新调查。找到的序列是通过其前身获得的。 wait 仅指到下一次排空的距离，而不是额外的时间测量:
<?php
declare(strict_types=1);
function hourglass(int $a, int $b, int $target, bool $prepare = false): ?array
{
if ($a <= 0 || $b <= 0 || $target < 0) {
throw new InvalidArgumentException('Positive capacities, nonnegative target required.');
}
$root = [0, 0, $prepare ? -1 : 0];
$key = static fn(array $s): string => implode(',', $s);
$queue = new SplQueue();
$queue->enqueue($root);
$previous = [$key($root) => null];
$enqueue = static function (array $next, array $from, array $action)
use ($queue, &$previous, $key): void {
$k = $key($next);
if (!array_key_exists($k, $previous)) {
$previous[$k] = [$key($from), $action];
$queue->enqueue($next);
}
};
while (!$queue->isEmpty()) {
$state = $queue->dequeue();
[$x, $y, $elapsed] = $state;
if ($elapsed === $target) {
$path = [];
for ($k = $key($state); $previous[$k] !== null;) {
[$k, $action] = $previous[$k];
$path[] = $action;
}
return array_reverse($path);
}
if ($elapsed === -1) {
$enqueue([$x, $y, 0], $state, ['start' => true]);
}
for ($mask = 0; $mask < 4; ++$mask) {
$u = ($mask & 1) ? $a - $x : $x;
$v = ($mask & 2) ? $b - $y : $y;
if ($u === 0 && $v === 0) {
continue;
}
$wait = $u === 0 ? $v : ($v === 0 ? $u : min($u, $v));
$nextTime = $elapsed < 0 ? -1 : $elapsed + $wait;
if ($nextTime > $target) {
continue;
}
$enqueue(
[max(0, $u - $wait), max(0, $v - $wait), $nextTime],
$state,
['flip' => $mask, 'wait' => $wait]
);
}
}
return null;
}
foreach ([[4, 7, 9, false], [4, 7, 1, false], [4, 7, 1, true],
[6, 10, 3, true], [5, 5, 10, false], [4, 7, 0, false]] as $case) {
echo json_encode($case), ': ', json_encode(hourglass(...$case)), PHP_EOL;
}
搜索找到或返回允许的进程 null, 如果不存在。它涵盖了所有允许的延续并需要最大限度的准备 \((a+1)(b+1)(T+2)\) 国家。因此，大输入需要大量内存。搜索转换的次数被最小化，而不是准备时间被最小化。合理的跑步时间和目标时间使用公分母转换为整数。例如，对于没有公共时间单位的运行时间 \(1\) 和 \(\sqrt{2}\), 这种有限整数搜索是不合适的。