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 czas | Klepsydra
9 min. | Klepsydra
13 min. | Komentarz |
|---|
| 0 | 0 | 0 | Na początku obracamy obie klepsydry |
| 1 | 8 | 12 | Minęła jedna minuta, dlatego nie pozostało 9 i 13 |
| .. | .. | .. | .. |
| 8 | 1 | 5 | |
| 9 | 0 | 4 | Obracamy Klepsydrę 9 minutową |
| 10 | 8 | 3 | |
| 11 | 7 | 2 | |
| 12 | 6 | 1 | Obracamy Klepsydrę 9 minutową |
| 13 | 5 | 0 | |
| .. | .. | .. | .. |
| 16 | 1 | 0 | |
| 17 | 0 | 0 | Odmierzone 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 Implementacja Kod źródłowy Implementacja