Strona główna » Algorytmy » Odmierzanie Wody
 

Odmierzanie Wody

Zadanie

Odmierz 6l wody przelewając wodę z naczynia do naczynia. Wody nie można nalewać na oko zawsze przelewając z wiaderka do wiaderka przelewa się całą wodę z wiaderka, albo tylko tyle ile można, ale nie przykładowo tylko połowę wody. W trakcie przelewania nie wolno rozlać wody.

Przykład

Przykładowo przelewając wodę z naczynia o pojemności 12l do naczynia o 5l można przelać tylko 5l, więc w pierwszym naczyniu zostanie 7l. Jednak jeśli chcielibyśmy wykonać operację odwrotną to naczynie z 5l wody będzie puste, ponieważ cała jego zawartość mieści się w 12l.

Odpowiedź

Oto lista kroków, która pozwala na znalezienie rozwiązania:

Przelewanie
z -> do
Wiadro 1Wiadro 2Wiadro 3
- start- 0012
3 -> 2075
2 -> 1525
1 -> 30210
2 -> 12010
3 -> 2273
2 -> 1543
1 -> 3048
2 -> 1408
3 -> 2471
2 -> 1561

Poprawnych rozwiązań jest oczywiście więcej, ale mogą wymagać większej ilości kroków. Przedstawione rozwiązanie pozwala na osiągnięcie celu w najmniejszej ilości kroków.

Prostokąt, nie kwadrat
Zadanie
Napisz program, który dla podanej siatki o rozmiarze a×b wyznaczy ile jest różnych kwadratów do zaznaczenia. Podczas rozwiązywania zadań nie należy używać żadnego wzoru.
Przykład
W podanym przykładzie można zaznaczyć 20 różnych kwadratów. (Wskazówka: 12 elementów 1×1, 6 elementów 2×2 oraz 2 elementy 3×3)
Rozwiązanie
Zauważmy, że jeśli a < b to w podanym prostokącie nie będzie można znaleźć kwadratu o rozmiarze większym niż a×a. Rozumowanie dotyczące ilości elementów o rozmiarze k×k jest bardzo podobne, ale należy pamiętać, że tym razem będzie ich (a - k + 1)(b - k + 1) pod warunkiem, że taki kwadrat można wpisać. Ponownie rozwiązanie można wygodnie przedstawić w tabelce:
#Element1×12×23×3..(a - 1)×(a - 1)a×a(a + 1)×(a + 1)..b×b#Ilośćab(a - 1)(b - 1)(a - 2)(b - 2)..2·(b - a + 1)b - a0..0
Implementacja
Funkcja ileKwadratow() wylicza dla podanej wielkości siatki a×b ile jest możliwych kwadratów do zaznaczenia. Pomijane są przypadki, gdy kwadrat nie mieści się na siatce.
(2.) Na początku należy wyznaczyć maksymalny rozmiar kwadratu, który można wpisać w podany rozmiar siatki. Następnie (3.) inicjalizujemy zmienną, a następnie (4. - 5.) sumujemy wartości dla kolejnych wielkości kwadratów. Na koniec (6.) zwracamy wyliczoną sumę.
(2.) Na początku należy wyznaczyć maksymalny rozmiar kwadratu, który można wpisać w podany rozmiar siatki. Następnie (3.) inicjalizujemy zmienną, a następnie (4. - 5.) sumujemy wartości dla kolejnych wielkości kwadratów. Na koniec (6.) zwracamy wyliczoną sumę.
Testowanie funkcji
W celu przeprowadzenia obliczeń i przetestowania powyższego kodu można skorzystać z poniższego fragmentu kodu:
Kod źródłowy ImplementacjaKod źródłowy Implementacja
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1