Weintrinker Problem |
10.09.2014, 08:46 | Auf diesen Beitrag antworten » | ||||||||||
SilverG6 | Weintrinker Problem Meine Frage: Die Aufgabe : Es treffen sich 2 Wanderer. Der Erste besitzt einen Krug mit 8 Liter Wein Inhalt, dass Gesamtvolumen dieses Krugs ist ebenfalls 8 Liter. Der Zweite besitzt 2 Krüge mit jeweils 5 und 3 Liter Füllvolumen, jedoch besitzt er noch keinen Wein. Der erstere möchte mit dem 2. so teilen das sie beide gleich viel Wein besitzen. Die beiden besitzen leider keine Hilfsmittel zum abmessen. Das bedeutet, dass sie nur die Krüge komplett umkippen können bis einer leer oder der zu befüllende Voll ist. Ich soll dazu nun ein Programm schreiben welches auch für allgemein gültige Fälle die schnellste Lösung angibt. Meine Ideen: Ich brauche keine Hilfe beim programmieren, an was es mir fehlt ist ein richtiger Lösungsansatz. Irgendwie scheint es mir was mit Differenzen zusammenzuhängen. Ich hab schon ziemlich lange daran gesessen und weiß das dies nur ein dürftiger eigener Ansatz ist. Meine Idee ist nun, dass man immer die Differenz zwischen den beiden Wanderern betrachtet und immer so umfüllt man beim umfüllen die Differenz entweder verringert oder halt die kleinst mögliche Erhöhung entsteht. Bsp. Person A besitzt 2 Krüge mit den Volumen 10(a) und 8(b) Liter. Krug a ist mit 10 Liter Wein gefüllt. Krug b ist mit 4 Liter Wein gefüllt. Person B besitzt auch 2 Krüge mit den Volumen 11(c) und 7(d) Liter. Krug c ist mit 4 Liter Wein gefüllt. Krug d ist mit 6 Liter Wein gefüllt. Die Differenz beträgt 4 Liter Person A besitzt 14 Liter und Person B 10 also muss Person A abgeben Möglichkeiten des umfüllens : a --> c = 7 Liter Austausch a --> d = 1 Liter Austausch b --> c = 4 Liter Austausch b --> d = 1 Liter Austausch Man muss aber auch nur 2 Liter ausgleichen, da man sonst ja die Differenz einfach halten würde also muss immer die hälfte der Differenz ausgeglichen werden. also würde ich jetzt einfach a --> d füllen das würde ich dann einfach in eine Schleife mit Abbruchbedingung stecken und fertig \(^.^)/ /(._.)\ Ich danke schonmal für Hilfe ! mit freundlichen Grüßen Franz |
||||||||||
|
|||||||||||
10.09.2014, 16:03 | Auf diesen Beitrag antworten » | ||||||||||
SilverG6 | RE: Weintrinker Problem Was mir und einem Freund noch aufgefallen ist. Es muss bei jeder Differenzveränderung zwischen den Weinmengen der Wanderer ein internes umschütten erfolgen bevor sie wieder gegenseitig umgießen. |
||||||||||
11.09.2014, 16:21 | Auf diesen Beitrag antworten » | ||||||||||
Karlito | Hallo, ich würde die Differenzen außer Acht lassen und einfach nur eine Breitensuche implementieren mit der Abbruchbedingung, dass es keine weiteren Möglichkeiten mehr gibt oder die Differenz null ist. Das Problem ist nämlich, dass die Differenz zwischenzeitlich wieder höher werden kann. Für die Breitensuche würde ich einfach eine Warteschlange nehmen und von jeder Konfiguration jede Folgekonfiguration in die Warteschlange einfügen (jede Umfüllmöglichkeit). Dabei muss man sich natürlich zu jedem Knoten im Suchbaum den Pfad merken. Weiterhin braucht es eine Liste, in welcher alle schon bekannten Konfigurationen gespeichert sind um doppelte Expansion des Knotens mit einer bekannten Konfiguration zu vermeiden und zu garantieren, dass das Programm terminiert, falls es keine Lösung gibt. Gruß, Karlito |
||||||||||
11.09.2014, 18:24 | Auf diesen Beitrag antworten » | ||||||||||
SilverG6 | Also meinst du ich sollte es mit Backtracking und probieren versuchen ? Die Abbruchbedingung wäre dann also wenn eine gleiche Verteilung wie irgendwann vorher schon auftritt ? Ja das ist uns auch schon aufgefallen das war etwas verwirrend ^^ Aber soll ich das ganze dann einfach per Zufall machen ? Ich hätte eigentlich gerne einen Algorithmus ._. So wie bei einem Labyrinth das ich irgendwie definieren kann das man gegen keine Wände läuft ^^ Aber ich glaube ich weiß ungefähr was du meinst ich versuche das mal umzusetzen ! DANKE <3 Btw bleibt das Forum hier so falls ich nachträglich dann noch fragen hätte ? mfg franz |
||||||||||
Anzeige | |||||||||||
|
|||||||||||
11.09.2014, 21:51 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | Du fängst mit einem Umfüllvorgang an, speicherst das Ergebnis, kehrst zur Lage von vor dem Umfüllen zurück und versuchst einen anderen Zug, bis du für eine Stellung alle möglichen Züge getestet hast. Diese Stellungen haben ermöglichen wiederum Züge, die du abarbeiten musst. Eine Möglichkeit ist Rekursion: du entscheidest dich am Anfang für einen Pfad und klapperst den komplett ab. Dann machst du das selbe für einen anderen Anfangszug. Alternativ (das dürfte effizienter sein): Du speicherst alle mit einem Zug erreichbaren Ergebnisse. Für jedes von diesen machst du einen weiteren Zug und speicherst das dann wieder (wenn du diese Stellung nicht früher schon erreicht hattest). Von den Ergebnissen aus Runde 2 kannst du die für den 3. Zug ermitteln. Zusätzlich solltest du für jeden Zug noch speichern, wo du hergekommen bist, damit du nicht nur sagen kannst, wie viele Züge nötig sind, sondern auch welche. Und hier wird kein Thread geschlossen, solange es kein Spam ist. Kannst dich gerne auch nach ein paar Wochen wieder melden. |
||||||||||
11.09.2014, 22:15 | Auf diesen Beitrag antworten » | ||||||||||
Karlito | Hallo,
Ja.
Nein. Du hast 2 Gruppen an Krügen in der allgemeinen Variante, oder? Ziel ist einfach, dass beide Gruppen die gleiche Menge Wein haben. D.h. die Differenz der Menge Wein zwischen beiden Gruppen ist 0.
Natürlich nicht per Zufall. Du kannst doch Systematisch vorgehen. Du hast einen Knoten im Suchbaum. Dann wählst du einen Krug aus und schüttest der Reihe nach in alle anderen Krüge um. Das wiederholst du für jeden nicht leeren Krug. Was den Algorithmus angeht: da wüsste ich gerade keinen Weg. Schau dir mal A* an. Die Schwierigkeit dabei ist sicher eine gute Heuristik zu finden.
Der Link bleibt gleich, die Rangfolge auf der "Portalseite" ändert sich sobald ein neuer Beitrag verfasst wird. Im Forum selbst kannst Du den Beitrag jedoch immer wieder finden und weitere Fragen anhängen. Gruß, Karlito |
||||||||||
11.09.2014, 22:20 | Auf diesen Beitrag antworten » | ||||||||||
Karlito | Hallo euler,
Eine Rekursion ist hier ungeeignet ist, da man mit Rekursion üblicherweise eine Tiefensuche realisiert. Laut Aufgabenstellung ist jedoch die schnellste Lösung gefragt, auf welche man nur stößt, wenn man alle Lösungen der Tiefensuche vergleicht oder Breitensuche verwendet und die erste Lösung wiedergibt. Würde bedeuten, dass man bei der Rekursion den gesamten Suchbaum ablaufen muss um dann alle Lösungen zu vergleichen (unoptimiert). Oder übersehe ich etwas? Gruß, Karlito |
||||||||||
12.09.2014, 05:41 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | Deshalb
Man könnte das Ganze etwas optimieren, wenn man zu jeden Schritt die Anzahl der benötigten Züge und die Folgezustände speichert (um die Zahl der nötigen Züge dann für den gesamten Baum zu verringern). Aber wie gesagt: Breitensuche ist effizienter. Vielleicht habe ich morgen etwas langeweile und schreibe ein paar Zeilen, mal sehen. |
||||||||||
13.09.2014, 08:07 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | Entweder habe ich Unsinn getrieben, oder dein zweites Beispiel ist nicht lösbar. Für das erste erhalte ich: jeweils Füllstand(maximal)
hier mein Code (C#, getestet mit MonoDevelop):
|
||||||||||
13.09.2014, 14:47 | Auf diesen Beitrag antworten » | ||||||||||
Karlito | Nice work! So. Und jetzt noch mal in C, Haskell und Prolog Gruß, Karlito |
||||||||||
13.09.2014, 15:04 | Auf diesen Beitrag antworten » | ||||||||||
eulerscheZahl | Aber nur, solange . Dann kann ich das int mit der Funktion decode nicht zurück in int[] umrechnen, würde wohl ohnehin Performaceprobleme geben. Immerhin wird mein Code auch mit mehr als zwei Eimern pro Person und mit mehr als zwei Personen fertig. |
|