| Autor |
Beitrag |
    
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1352
Registriert: 07-2000
| | Veröffentlicht am Donnerstag, den 23. Januar, 2003 - 19:56: | 
|
Ben, Maria und Florian haben von ihrer Tante ein 15-Liter-Fass Bier geschenkt bekommen, das sie sich geschwisterlich teilen sollen. Sie haben dazu einen leeren 7-Liter-Eimer und zwei leere 4-Liter-Schüsseln zur Verfügung.
Wie können sie das Bier so hin und herschütten, dass schließlich im Fass und im Eimer je 5 Liter und in den beiden Schüsseln zusammen auch 5 Liter drin sind?
Ein zulässiger Schüttvorgang besteht entweder darin, dass ein Gefäß komplett in ein anderes entleert oder aber ein Gefäß aus einem anderen randvoll gefüllt wird.
Ist nicht ganz appetitlich, aber viel Spaß ;-) |
ICH (tux87)
Mitglied
Benutzername: tux87
Nummer des Beitrags: 48
Registriert: 12-2002
| | Veröffentlicht am Donnerstag, den 23. Januar, 2003 - 21:20: |
|
15:0:0:0
8:7:0:0
8:3:4:0
12:3:0:0
12:0:3:0
5:7:3:0
5:6:4:0
5:2:4:4
9:2:4:0
9:0:4:2
9:4:0:2
5:4:4:2
5:7:1:2
5:5:1:4
Das 1. ist das Fass
Das 2. ist der Eimer
Das 3. und 4. sind die Schüsseln
(Beitrag nachträglich am 23., Januar. 2003 von tux87 editiert)
ICH
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1353
Registriert: 07-2000
| | Veröffentlicht am Donnerstag, den 23. Januar, 2003 - 21:38: |
|
Klasse! Probiert oder rechnen lassen? ;-)
Die Lösung ist übrigens nicht eindeutig, aber 13 Schüttvorgänge scheinen optimal zu sein.
Gruß
Z. |
ICH (tux87)
Fortgeschrittenes Mitglied
Benutzername: tux87
Nummer des Beitrags: 51
Registriert: 12-2002
| | Veröffentlicht am Donnerstag, den 23. Januar, 2003 - 22:01: |
|
Hi Zaph!
Größtenteils probiert! Am Ende rekursiv - das ging dann ganz gut! Hab nur wenig gerechnet! War aber ne gute Aufgabe - man kann es doch bestimmt auch komplett rechnen - wie geht das?
ICH
|
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 182
Registriert: 10-2001
| | Veröffentlicht am Donnerstag, den 23. Januar, 2003 - 22:09: |
|
15 7 4 4
--------
15 0 0 0
8 7 0 0
8 0 4 3
12 0 0 3
5 7 0 3
5 3 4 3
9 3 0 3
9 6 0 0
9 0 4 2
9 4 0 2
5 4 4 2
5 7 1 2
5 5 1 4
Gelöst mit rumprobieren - wäre mal interessant wie man das mit einem Programm lösen kann, denn außer Brute-Force fällt mir spontan kein Algorithmus ein.
Ein Rucksack-Pack-Problem ist es IMHO auch nicht.
Onkel Murray |
kai (kai14)
Neues Mitglied
Benutzername: kai14
Nummer des Beitrags: 4
Registriert: 12-2002
| | Veröffentlicht am Freitag, den 24. Januar, 2003 - 11:26: |
|
Was heisst eigentlich IMHO ?? |
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 183
Registriert: 10-2001
| | Veröffentlicht am Freitag, den 24. Januar, 2003 - 12:31: |
|
In My Humble Opinion - meiner bescheidenen Meinung nach
Onkel Murray} |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1354
Registriert: 07-2000
| | Veröffentlicht am Freitag, den 24. Januar, 2003 - 14:11: |
|
Das Probieren habe ich schnell aufgegeben. Hier das Programm, das meine Lösung gefunden hat. Hoffe, es ist nicht zu kryptisch und einigermaßen verständlich.
#include <stdio.h>
#define I0 4
#define I1 4
#define I2 7
#define I3 15
const int Volumen[4] = {I0,I1,I2,I3}, Ziel = 5;
int main(){
..int Vater[I0+1][I1+1][I2+1];
..int Liste[(I0+1)*(I1+1)*(I2+1)][3];
..int Alt[4], Neu[4], ToDo, Done, Summe, i, j, k;
..// Anfangszustand: Behaelter 0, 1 und 2 leer
..// (in Behalter 4 der Rest)
..Liste[0][0] = 0;
..Liste[0][1] = 0;
..Liste[0][2] = 0;
..// initialisieren
..for(i=0; i<=Volumen[0]; i++)
....for(j=0; j<=Volumen[1]; j++)
......for(k=0; k<=Volumen[2]; k++)
........Vater[i][j][k] = -1;
..ToDo = 1;
..Done = 0;
..while(Done < ToDo){
....// Zustand mit der Nr. Done bearbeiten
....Alt[3] = Volumen[3];
....for(i=0; i<3; i++){
......Alt[i] = Liste[Done][i];
......Alt[3] -= Alt[i];
....}
....// hier:
....// Alt[01 + Alt[ll + Alt[2] + Alt[3] = Volumen[3]
....for(i=3; i>=0; i--){ // Nachfolgezustaende suchen
......if(Alt[i] > 0){
........// Fluessigkeit von Behaelter i
........for(j=3; j>=0; j--){
..........if(j != i && Alt[j] < Volumen[j]){
............// Fluessigkeit nach Behaelter j
............for(k=0; k<4; k++)
..............Neu[k] = Alt[k] ;
............Summe = Alt[i] + Alt[j];
............if(Summe <= Volumen[j]){
..............// Behaelter i komplett in Behaelter j fuellen
..............Neu[i] = 0;
..............Neu[j] = Summe;
............}
............else{
..............// Behaelter j mit Behaelter i fuellen
..............Neu[i] = Summe - Volumen[j];
..............Neu[j] = Volumen[j];
............}
............if(Vater[Neu[0]][Neu[1]][Neu[2]] < 0){
..............// neuer Zustand!
..............Vater[Neu[0]][Neu[1]][Neu[2]] = Done;
..............for(k=0; k<4; k++)
................Liste[ToDo][k] = Neu[k];
..............if(Neu[0] + Neu[1] == Ziel
.................&& Neu[2] == Ziel && Neu[3] == Ziel)
................goto Bingo;
...............ToDo++;
.............}
..........}
........} // j-Schleife
......}
....} // i-Schleife
....Done++;
..} // while-Schleife
..printf("Keine Loesung\n");
..return 0;
.Bingo:
..printf("BINGO!! Liste in umgekehrter Reihenfolge:\n");
..for(i=ToDo, j=0; i>0;
......i=Vater[Liste[i][0]][Liste[i][1]][Liste[i][2 ]], j++)
....printf("%2d %d %d %d\n",
...........Volumen[3]-Liste[i][0]-Liste[i][1]-List e[i][2],
...........Liste[i][2],Liste[i][1],Liste[i][0]);
..printf("%2d %d %d %d\n",
.........Volumen[3]-Liste[i][0]-Liste[i][1]-Liste[ i][2],
.........Liste[i][2],Liste[i][1],Liste[i][0]);
..printf("%d Schritte\n",j);
..return 0;
}
Es liefert die Lösung
15 0 0 0
8 7 0 0
8 3 4 0
8 0 4 3
1 7 4 3
1 6 4 4
5 6 0 4
5 2 4 4
9 2 4 0
9 0 4 2
9 4 0 2
5 4 4 2
5 7 1 2
5 5 1 4
|
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 184
Registriert: 10-2001
| | Veröffentlicht am Freitag, den 24. Januar, 2003 - 15:45: |
|
So ganz übersichtlich ist das Programm ja nicht, aber anhand der Schleifen kann man dann auf "ausbrüten" schließen (also einfach alles durchprobieren).
Die Frage die sich stellt lautet, ob es ein in der Informatik bekanntes Lösungsverfahren gibt, da es sich gewissermaßen um ein allgemeines Problem handelt.
Onkel Murray
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1355
Registriert: 07-2000
| | Veröffentlicht am Freitag, den 24. Januar, 2003 - 18:03: |
|
Hallo Onkel Murray,
ganz so brutal war meine Gewaltanwendung dann hoffentlich doch nicht. Immerhin wird das Problem durch das Programm in einem Wimpernschlag erledigt.
Die äußere while-Schleife wird maximal (I0 + 1)*(I1 + 1)*(I2 + 1) = 5 * 5 * 8 = 200 mal durchlaufen. i und j laufen beide von 0 bis 3. Also insgesamt 3200 Durchläufe der inneren Schleife.
Betrachtet wird hier ein gerichteter Graph mit 200 Knoten. In diesem Graph wird ein kürzester Weg vom Startknoten (0,0,0) bis in die Zielmenge
{(x,y,z) | x+y=5, z=5)}
gesucht.
Dieses Vorgehen ist aber i. A. nicht polynomial, da es nicht polynomial in
log max(I0,I1,I2)
ist. Ich bezweifele, dass es einen Polynomialzeit-Algorithmus gibt.
Gruß
Z. |
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 185
Registriert: 10-2001
| | Veröffentlicht am Freitag, den 24. Januar, 2003 - 22:58: |
|
Damit beantwortest du aber auch schon eine ganze Menge Fragen.
Es ist also ein Graphenproblem - ich hab übrigens in der KI-Forschung auch sowas gefunden.
Ich muß gestehen, das ich eine derartige Wucht hinter einem so scheinbar simplen Problem nicht vermutet hätte.
Onkel Murray
PS: Ich werde mir mal den Artikel aus der KI näher durchlesen, dann verstehe ich es sicher besser.
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1356
Registriert: 07-2000
| | Veröffentlicht am Samstag, den 25. Januar, 2003 - 00:43: |
|
Bin gespannt, wenn du neue Erkenntnisse präsentieren kannst :-)
Gruß
Z. |
svenja (friend)
Neues Mitglied
Benutzername: friend
Nummer des Beitrags: 2
Registriert: 03-2003
| | Veröffentlicht am Dienstag, den 04. März, 2003 - 16:00: |
|
zwar auch nur durch probieren, aber weniger schritte:
15 0 0 0
8 7 0 0
4 7 4 0
0 7 4 4
7 0 4 4
7 4 0 4
7 7 0 1
7 3 4 1
5 5 4 1
oder stimmt da was nicht?
|
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 198
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 04. März, 2003 - 16:15: |
|
Hallo Svenja,
es ist definitiv klar, das unser Problem mit 13 Zügen den kürzesten Weg hat. Ich knobel seit nunmehr einigen Wochen über den längsten Weg (derzeit liegt der bei 83 :-).
Aber zu Deinem Denkfehler, er liegt im letzten Zug - Du kannst von den letzten 7 Liter nicht einfach mal so 'schätzweise' 2 Liter abgießen.
Cu Onkel Murray
|
svenja (friend)
Neues Mitglied
Benutzername: friend
Nummer des Beitrags: 3
Registriert: 03-2003
| | Veröffentlicht am Mittwoch, den 05. März, 2003 - 15:37: |
|
klar mensch, weiß auch nich wie ich drauf komme!
na denn mal noch viel spaß beim längsten weg...
svenja
|
