Strona główna » Algorytmy » Artykuły » Czas i Klepsydry
 

Czas i Klepsydry

Zagadka

Odmierz 17 minut przy pomocy dwóch klepsydr. Piasek w pierwszej klepsydrze przesypuje się w dokładnie 9 minut, a w drugiej trwa to 13 minut. Zakładamy, że dobrze ustawiona klepsydra to taka, która stoi równo na powierzchni.

Rozwiązanie

W celu zmierzenia 17 minut należy najpierw obrócić równocześnie jedną i drugą klepsydre. Po upływie 9 minut w mniejszej zostanie całkowicie przesypany piasek, a w drugiej pozostanie do odmierzenia jeszcze 4 minuty. W tym momencie należy obrócić mniejszą klepsydrę. Po kolejnych 4 minutach w większej klepsydrze cały piasek się przesypie, a w drugiej zostanie do odmierzenia 5 minut. Do tej pory upłynęło 13 minut, więc trzeba obrócić mniejszą klepsydrę, aby zmienić pozostały czas do odmierzenia z 5 minut to 4 minut.

Powyższe rozumowanie można również przedstawić w postaci tabelki:

Aktualny czasKlepsydra
9 min.
Klepsydra
13 min.
Komentarz
000Na początku obracamy obie klepsydry
1812Minęła jedna minuta, dlatego nie pozostało 9 i 13
........
815 
904Obracamy Klepsydrę 9 minutową
1083 
1172 
1261Obracamy Klepsydrę 9 minutową
1350 
........
1610 
1700Odmierzone zostało dokładnie 17 minut
Implementacja
Powyższą zagadkę można dowolnie modyfikować poprzez zmianę ilości klepsydr oraz czasu przesypywania się wewnątrz nich piasku. Ze względu na niezliczoną ilość przypadków program komputerowy mógłby spróbować odpowiedzieć na je wszystkie w celu potwierdzenia rozwiązania, albo potwierdzenia, że rozwiązanie nie istnieje.
Strategia
Na podstawie rozwiązanego zadania można stwierdzić, że każda klepsydra może być w dwóch stanach: przesypywać się, albo nie. Dodatkowo należy zauważyć, że klepsydrę można obrócić oraz skończy mierzyć czas w momencie, gdy któraś z klepsydr skończy przesypywać piasek. W innym przypadku byłoby to mierzenie czasu na oko, a co za tym idzie nie byłoby pewności co do tego rozwiązania. Dodatkowo szukanie rozwiązania można ograniczyć z góry poprzez czas do odmierzenia.
Funkcja wyszukiwania
Na podstawie rozwiązanego zadania można stwierdzić, że każda klepsydra może być w dwóch stanach: przesypywać się, albo nie. Dodatkowo należy zauważyć, że klepsydrę można obrócić oraz skończy mierzyć czas w momencie, gdy któraś z klepsydr skończy przesypywać piasek. W innym przypadku byłoby to mierzenie czasu na oko, a co za tym idzie nie byłoby pewności co do tego rozwiązania. Dodatkowo szukanie rozwiązania można ograniczyć z góry poprzez czas do odmierzenia.
Testowanie funkcji
Kod źródłowy ImplementacjaKod źródłowy Implementacja