Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Umfüllproblem
Fiete - Fr 01.06.12 11:26
Titel: Umfüllproblem
Das Programm löst das sogenannte 3-Krüge-Problem.
Beispiel:
Ein Winzer hat einen vollen Krug mit 8Litern Wein und zwei leere Krüge, von denen einer 5, der andere 3 Liter fasst.
Nun kommt ein Mann vorbei, der exakt 4 Liter Wein kaufen möchte. Der Bauer hat aber keine anderen Hilfsmittel als seine drei Krüge, um den Wein abzumessen. Wie oft muss er Wein von einem Krug in einen anderen gießen, um schließlich in den beiden größeren Krügen je 4 Liter zu haben?
Algorithmus:
Man fülle aus dem großen Krug in den kleinen,
von dem kleinen Krug SOLANGE in den mittleren Krug bis dieser gefüllt ist.
Dann entleere man den mittleren Krug in den großen Krug und
beginne von vorn, bis der Endzustand (Erfolg) oder
bis der Anfangszustand (Mißerfolg) erreicht ist
Der Umfüllprozeß kann in Dreickskoordinaten dargestellt werden.
Es gilt der Satz von Viviani (1622 - 1703):
In jedem gleichseitigen Dreieck ist die Summe der Abstände eines
innerhalb des Dreiecks befindlichen Punktes von den Seiten konstant.
Gruß Fiete
Mathematiker - Fr 01.06.12 12:22
Hallo Fiete,
schönes Programm.
Ich habe mal ein paar Testläufe gemacht, so zum Beispiel mit 15, 7, 4 Eimergrößen und einer Zielfüllung 6, 7, 2. Dein Programm findet die beste Lösung!
Meine Frage: Findet man mit Deinem Algorithmus immer die optimale Lösung?
Beste Grüße
Mathematiker.
Horst_H - Fr 01.06.12 17:53
Hallo,
ich bin mir da nicht sicher.
Ausgangskruggrößen
10..7..3
Startfüllung
10..0..0
Endfüllung
7..0..3
Ich würde nun einfach aus 10 l Krug direkt in 3 Liter giessen und fertig ist.
Das Programm ist etwas kreativer:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
| 10 0 0 3 7 0 3 4 3 6 4 0 6 1 3 9 1 0 9 0 1 2 7 1 2 5 3 5 5 0 5 2 3 8 2 0 8 0 2 1 7 2 1 6 3 4 6 0 4 3 3 7 3 0 7 0 3 18 Umfüllungen |
Gruß Horst
EDIT
Liegt es daran, dass 10 = 7 + 3 ist
Fiete - Fr 01.06.12 20:06
Moin Horst_H,
Zitat: |
Ausgangskruggrößen
10..7..3
Startfüllung
10..0..0
Endfüllung
7..0..3
|
Das Programm ermittelt immer zwei Lösungen!
10 0 0
7 0 3
1 Umfüllung
1. Lösung gefunden!
10 0 0
3 7 0
3 4 3
6 4 0
6 1 3
9 1 0
9 0 1
2 7 1
2 5 3
5 5 0
5 2 3
8 2 0
8 0 2
1 7 2
1 6 3
4 6 0
4 3 3
7 3 0
7 0 3
18 Umfüllungen
2. Lösung gefunden!
Gruß Fiete
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!