មានវ៉ែនតាពីរ៖ មួយដំណើរការទាំងស្រុងក្នុងរយៈពេល \(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\) -th time ។ មានឯកតាពេលវេលា \(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}\), ការស្វែងរកចំនួនគត់កំណត់នេះមិនសមរម្យទេ។