دو ساعت شنی وجود دارد: یکی به طور کامل در \(4\) دقیقه اجرا می شود، دیگری در \(7\) دقیقه. چگونه دقیقا \(9\) دقیقه را اندازه گیری می کنید وقتی که اندازه گیری باید اولین بار شروع ساعت ها شروع شود؟ ساعت دیگر، شمارش ثانیه و حدس زدن مجاز نیست. تنها کاری که باید انجام دهید این است که ساعت شنی را برگردانید و تماشا کنید که اتاق بالایی خالی است. چرخش نباید زمانبر باشد. آنچه ما به دنبال آن هستیم فرآیندی است که در آن پایان دوره زمانی مورد نظر تنها توسط ساعت شنی قابل تشخیص باشد.
ساعت را با \(4\) دقیقه \(A\) و ساعت \(7\) دقیقه \(B\) می نامیم. در ابتدا تمام شن و ماسه در پایین است. هر دو ساعت را همزمان با برگرداندن آنها شروع می کنیم. از این لحظه به بعد \(9\) دقیقه جستجو شده حساب می شود. پس از آن، همیشه می توانید زمانی که یک ساعت در بالا خالی می شود، معامله کنید. شما نمی توانید یک، یک یا هر دو ساعت را بچرخانید، حتی ساعتی که هنوز کار می کند. شما صبر کنید تا دفعه بعد تمام شود. توقف و علامت گذاری مجاز نیست. یک ساعت خالی می تواند سرپا بماند. راه حل به نظر می رسد این است:
- در دقیقه \(0\) \(A\) و \(B\) شروع می شود.
- در دقیقه \(4\) \(A\) خالی است و برگردانده می شود. \(B\) بدون تغییر به کار خود ادامه می دهد.
- در دقیقه \(7\) \(B\) خالی است و برگردانده می شود. هنوز \(1\) دقیقه به \(A\) باقی مانده است.
- در دقیقه \(8\) \(A\) خالی است. در \(B\) ماسه دقیقاً \(1\) دقیقه پایین رفت. بنابراین \(B\) بلافاصله دوباره برگردانده می شود.
- در دقیقه \(9\) \(B\) خالی است. زمانی که به دنبالش بودید رسیده است.
در دقیقه \(8\) ساعت \(B\) را که هنوز در حال اجراست برمیگردانیم. از زمان راه اندازی مجدد آنها در دقیقه \(7\) ، دقیقاً به اندازه شن و ماسه در \(1\) دقیقه از گلوگاه عبور کرده است. بعد از چرخاندن فقط همین مقدار کم روی آن قرار می گیرد. اکنون \(1\) دقیقه طول می کشد تا دوباره چکه کند. بنابراین ساعت در دقیقه \(9\) خالی می شود، نه پس از اجرای کامل دیگر. بنابراین دقیقه آخر را با ماسه ای که قبلاً از آن عبور کرده است اندازه می گیریم. انیمیشن این حرکت را نشان می دهد:
چرخاندن ساعت شنی نیز برای راه حل کلی مفید است. منظور ما از زمان باقیمانده زمانی است که ماسه هنوز باید در محفظه بالایی جریان داشته باشد. اگر ساعت کامل دارای زمان اجرا \(c\) و زمان اجرای باقیمانده آن \(r\) باشد، مقدار شن در پایین با مدت زمان \(cr\) مطابقت دارد. وقتی آن را برگردانید، این مقدار دقیق به بالا می آید. اگر محفظه بالایی از قبل پر باشد، بعد از آن خالی می شود و بالعکس. برای یک ساعت نیمه اجرا شده، زمان اجرای جدید باقی مانده \(r'\):
$$r'=c-r.$$
قبلاً اندازه گیری با اولین چرخش شروع می شد. این به معنای "بدون زمان پیشروی" است: هر دقیقه از زمان شروع به حساب می آید. از طرف دیگر، "با پیش" به این معنی است که شما می توانید ساعت ها را ابتدا آماده کنید و بازه زمانی مورد نظر بعدا شروع می شود. به عنوان مثال، ما هر دو ساعت را شروع می کنیم و \(A\) را در دقیقه \(4\) برگردانیم. اگر \(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\) قرار دارد. لم Bézout تطبیق اعداد صحیح \(n,m\) را تضمین می کند اگر \(T\) مضرب مثبت \(g\) باشد. رابطه ای که شما به دنبال آن هستید::
$$na-mb=T.$$
اعداد \(n,m\) ارائه شده توسط Bézout در ابتدا می توانند منفی باشند. اجراهای منفی را نمی توان انجام داد. با این حال، می‌توان هر دو عدد را بدون تغییر بازه زمانی افزایش داد: آنها را با \(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}\), این جستجوی اعداد صحیح محدود مناسب نیست.