Umfüllproblem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:40 Mi 16.02.2005 | | Autor: | patrick |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Hallo ich habe eine Frage zu folgendem (bekannten) Problem:
Man kommt in einen Milchladen mit einem Gefäß, mit dem man genau 7 Liter abmessen kann, und möchte 4 Liter Milch kaufen. Der Milchverkäufer besitzt leider nur einen Eimer mit der Eichmarke 10 Liter. Frage: kann man mit diesen beiden Gefäßen aus einer risiegen Milchwanne genau 4Liter abfüllen oder nicht?
Die Frage ist für den konkreten Fall natürlich simpel und einfach durch Probieren zu lösen. Nun betrachtet man den allgemeinen Fall; wir ersetzen das Fassungsvermögen des Eimers durch Emax und das des Gefässes durch Gmax.. Folgender Algorithmus löst das Problem
Es sei S die Sollmenge (diese sei ein Vielfaches von ggT(GMAX und EMAX):
G := 0, E:= 0
while G <> S
Fuelle E
WHILE E>= GMAX DO
UMFUELLEN von E nach G; AUSGIESEN von G;
END (*WHILE*);
Umfuellen von E nach G;
END;
ACHTUNG: die einzelnen Operationen lauten in einer Programmiersprache:
Fülle E entspricht E:= EMAX
AUSGIESSEN G entspricht G:= GMAX
UMFÜLLEN von E nach G enspricht falls E+G <= GMAX G := G+E; E:= 0;
andernfalls E := E-(G-GMAX); G:= 7
Nun meine Frage. Wieso leistet der Algorithmus das Gewünschte. Danke für eure Hilfe.
|
|
| |
|
Hallo Patrick,
> Nun meine Frage. Wieso leistet der Algorithmus das
> Gewünschte.
Ich habe versucht einen kleinen Ableitungsbaum für deinen Algo zu erstellen:
[Dateianhang nicht öffentlich]
Dort scheinen sich gerade und ungerade Zahlen bei einem Ast immer abzuwechseln.
Viele Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:23 Do 17.02.2005 | | Autor: | leduart |
Hallo
Ich nenne deine Mengen a,b mit a>b
dann gilt [mm] a=n_{1}*b [/mm] +r r hat denselben ggT wie a,b oder [mm] a=(n_{1}+1)*b -r_{1} [/mm] mit [mm] r_{1}=b-r.
[/mm]
[mm] r_{1} [/mm] bleibt nach n+1 mal umschütten in b, danach (a ausleeren) in a
Du tust dasselbe mit [mm] a-r_{1} =(n_{2}+1)*b -r_{2}; [/mm] mit [mm] n_{2} \le n_{1}. [/mm] Dabei gilt [mm] r_{2}
Immer so weiter, [mm] r_{i+1}
Eben fällt mir ein, dass das Argument viel zu lang ist. Wenn man benutzt, dass ggT=m*a-n*b ist bist du sofort fertig!. Wenn du die Gleichung nicht kennst sieh nach unter "euklidischer Allgorithmus"
Gruss leduart
|
|
|
|
