Skriptum Informatik (PDF)

Es handelt sich um ein alltägliches Problem, wie es einem in Oldenburg und Umge­ bung (immer noch, aber seltener werdend) begegnet. Jemand betritt einen Milchladen mit einer Kanne K, die genau die Menge V K (z. B. VK = 7 1) fasst, und möchte die Menge Soll kaufen (mit 0 < Soll S; VK , z. B. Soll = 41). Der Milchverkäufer hat nur einen Eimer E, der es erlaubt, die Menge VE (mit VE ~ VK, z. B. VE = 10 1) abzumessen. Frage: Kann man mit diesen beiden Gefässen aus einer grossen Milchwanne die gewünschte Menge abfüllen oder nicht? Und falls ja, wie soll das vor sich gehen? Die Lösung soll also möglichst für beliebige Werte von VK, Soll S; VK und VE ~ VK anwendbar sein; der Fall VE < VK lässt sich durch Tausch der Gefässe analog behandeln. Der Einfachheit halber nehmen wir an, dass es sich stets um ganze Liter handelt, dass wir also VK, Soll und VE durch natürliche Zahlen darstellen können. Da wir nur mit Vielfachen des Volumens 11 zu tun haben, können wir die Einheit weg­ lassen. Wenn Soll null oder VK ist, ist die Lösung trivial; andernfalls lässt sich das Problem immer dann lösen, wenn die gewünschte Menge Soll ein Vielfaches des grössten gemeinsamen Teilers von VK und VE ist; das ist sicher der Fall, wenn VK und VE teilerfremd sind.