Czerpaki Mavannkas: WItam, mam zadanie o treści. Posiadamy dwa czerpaki o pojemnościach M i N litrów. Pusty pojemnik o nieskończonej pojemności. Podaj sposób napełnienia pojemnika K litrami wody. Wodę można wlewać i wylewać tylko pełnymi czerpakami. Podaj ilość ruchów dla każdego czerpaka. Jeśli danym czerpakiem wlewamy traktujemy to z plusem do sumy ruchów a jeśli wylewamy to z minusem. Wiem, że nie zawsze jest to wykonywalne ale muszę znaleźć sposób znalezienia ewentualnego rozwiązania. To jest problem algorytmiczny ale myślę, że jest mocno zawiązany z matematyką dlatego piszę do was Nie chce odpowiedzi wprost ,chciałbym was prosić o jakieś wskazówki Dzięki
27 lis 09:40
Blee: Zasada jest taka niech M > N, Zapełniamy pojemnik N−litrowy. Przelewamy wszystko do M−litrowego (przez co staje się on niepełny). Znowu nalewamy N−litrowy i przelewamy 'co się da' do M−litrowego. W efekcie otrzymujemy pełen M−litrowy + N−litrowy zapełniony dokładnie (2N−M) litrami wody. Ów (2N−M) litrów przelewamy do pustego pojemnika i procedurę powtarzamy. Inna procedura którą można zrobić: Nalewamy do M−litrowego wodę. Przelewamy 'co się da' do N−litrowego (aż będzie pełny). W efekcie w M−litrowym zostaje nam (M−N) litrów wody, które przelewamy do zbiornika docelowego. Procedurę ponawiamy. (bądź korzystamy z poprzedniej zaprezentowanej − wszystko zależy ile litrów nam jeszcze brakuje) Pamiętaj także, że są takie wartości M, N dla których nie można uzyskać dowolnej wartości K. Np. niech M = 8 litrów, N = 6 litrów. Dla K = 1, 3, 5, ...., 2k+1 litrów nie jest możliwe do uzyskania. (ponieważ nie jesteś w stanie uzyskać 1 litra z naczyń dla których NWD(N,K) > 1
27 lis 10:02
Mavannkas: Czy dobrze myślę, że nie da się znaleźć rozwiązania zawsze gdy NWD jest mniejsze od najniższej możliwej pojemności?
27 lis 11:31