Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Ein Stapelrätsel

ZahlReich - Mathematik Hausaufgabenhilfe » Denksport » Kopfnüsse » Ein Stapelrätsel « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Kay Schönberger (kay_s)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: kay_s

Nummer des Beitrags: 115
Registriert: 01-2001
Veröffentlicht am Freitag, den 13. Juni, 2003 - 16:39:   Beitrag drucken

In einem Lagerhaus befinden sich nebeneinander vier großflächige Palettenstapel. Auf dem Stapel ganz links befinden sich 100 Paletten, die anderen sind leer.
Um die (ziemlich schweren) Paletten umzuverteilen steht ein vollautomatischer Gabelstapler bereit.

Das Problem: Die gesamte Technik sowie die Software stammt noch aus den Siebzigern. Damals war die Steuerelektronik noch ziemlich primitiv und so versteht der Gabelstapler nur die zwei Befehle "L" und "R".
Nach einer solchen Anweisung holt der Stapler eine Zahl Paletten vom aktuellen Stapel, bewegt sich (je nach Anweisung "L" oder "R") eine Position nach links oder rechts und schichtet die Paletten auf den aktuellen neuen Stapel auf.
Dummerweise kann das Maschinchen nicht einzelne Paletten auseinanderhalten, sondern holt nach jeder Anweisung exakt die Hälfte der Paletten vom aktuellen Stapel herunter (ist die Zahl N der Paletten ungerade, werden (N+1)/2 Stück geholt).

Der Lagerchef würde es nun gerne sehen, daß der Gabelstapler folgende Aufgaben erledigt:

Programm A:
60 Paletten vom Ausgangsstapel gleichmäßig auf die restlichen verteilen (Zielkonfiguration: 40/20/20/20)

Programm B:
90 Paletten vom Ausgangsstapel gleichmäßig auf die restlichen verteilen (Zielkonfiguration: 10/30/30/30)

In einem Beispiel würde die Anweisungsfolge "R L R R R L ..." also zu der Konfigurationsfolge

(100/0/0/0 [1]) -> (50/50/0/0 [2]) -> (75/25/0/0 [1]) -> (37/63/0/0 [2]) -> (37/31/32/0 [3]) -> (37/31/16/16 [4]) -> (37/31/24/8 [3]) -> ...

führen (letzte Ziffer = aktuelle Position der Maschine).

Der Chef sieht sich trotz seiner Qualifikation leider nicht in der Lage, die richtige Anweisungsfolge einzugeben. Deshalb hat er sich ein ganzes Dutzend Programmierer ins Boot geholt, die das Problem lösen sollten.

Und tatsächlich - nach einer Woche fand einer der gestreßten Computerexperten eine Anweisungsfolge für Programm A!

Wie sah sie wohl aus?

(P.S.: Trotzdem der Chef weitere zwei Monate Zeit investiert hat, fand keiner der Programmierer eine Lösung für Programm B...)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Martin (martin243)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: martin243

Nummer des Beitrags: 771
Registriert: 02-2001
Veröffentlicht am Montag, den 16. Juni, 2003 - 17:33:   Beitrag drucken

Tach!

Nach ersten zaghaften Versuchen per Hand kam ich zu dem Schluss, dass es wohl doch mehr als 5 oder 10 Schritte sein müssten. Also habe ich mal den Computer darauf angesetzt und er fand für A insgesamt 675 verschiedene jeweils 40-schrittige Lösungen. Hier mal drei davon:

rrrlrlllrrrlllrrrlllrrrllrrlllrrllrrrlll

rlrlrrlrrlllrrrllrllrrrlllrrlrrlllrrrlll

rlrrrllrrlllrrlrrlllrrrlllrrlrrlllrrrlll

Hier auch mal die letzte zum Nachvollziehen, wobei die Positionen mit 0 bis 3 bezeichnet sind:

50 50 0 0 [1]
75 25 0 0 [0]
37 63 0 0 [1]
37 31 32 0 [2]
37 31 16 16 [3]
37 31 24 8 [2]
37 43 12 8 [1]
37 21 34 8 [2]
37 21 17 25 [3]
37 21 30 12 [2]
37 36 15 12 [1]
55 18 15 12 [0]
27 46 15 12 [1]
27 23 38 12 [2]
27 42 19 12 [1]
27 21 40 12 [2]
27 21 20 32 [3]
27 21 36 16 [2]
27 39 18 16 [1]
47 19 18 16 [0]
23 43 18 16 [1]
23 21 40 16 [2]
23 21 20 36 [3]
23 21 38 18 [2]
23 40 19 18 [1]
43 20 19 18 [0]
21 42 19 18 [1]
21 21 40 18 [2]
21 41 20 18 [1]
21 20 41 18 [2]
21 20 20 39 [3]
21 20 40 19 [2]
21 40 20 19 [1]
41 20 20 19 [0]
20 41 20 19 [1]
20 20 41 19 [2]
20 20 20 40 [3]
20 20 40 20 [2]
20 40 20 20 [1]
40 20 20 20 [0]


Über die B zerbreche ich mir momentan noch den Kopf.

MfG
Martin
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Onkel Murray (murray)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: murray

Nummer des Beitrags: 207
Registriert: 10-2001
Veröffentlicht am Donnerstag, den 10. Juli, 2003 - 07:12:   Beitrag drucken

Hallo Kay,

für Programm A ist die kürzeste Lösung 38 Züge:

1: r [100,0,0,0] ==> [50,50,0,0]
2: l [50,50,0,0] ==> [50,25,25,0]
3: r [50,25,25,0] ==> [50,38,12,0]
4: l [50,38,12,0] ==> [69,19,12,0]
5: r [69,19,12,0] ==> [34,54,12,0]
6: r [34,54,12,0] ==> [34,27,39,0]
7: r [34,27,39,0] ==> [34,27,19,20]
8: l [34,27,19,20] ==> [34,27,29,10]
9: l [34,27,29,10] ==> [34,42,14,10]
10: l [34,42,14,10] ==> [55,21,14,10]
11: r [55,21,14,10] ==> [27,49,14,10]
12: r [27,49,14,10] ==> [27,24,39,10]
13: r [27,24,39,10] ==> [27,24,19,30]
14: l [27,24,19,30] ==> [27,24,34,15]
15: l [27,24,34,15] ==> [27,41,17,15]
16: r [27,41,17,15] ==> [27,20,38,15]
17: l [27,20,38,15] ==> [27,39,19,15]
18: l [27,39,19,15] ==> [47,19,19,15]
19: r [47,19,19,15] ==> [23,43,19,15]
20: r [23,43,19,15] ==> [23,21,41,15]
21: r [23,21,41,15] ==> [23,21,20,36]
22: l [23,21,20,36] ==> [23,21,38,18]
23: l [23,21,38,18] ==> [23,40,19,18]
24: l [23,40,19,18] ==> [43,20,19,18]
25: r [43,20,19,18] ==> [21,42,19,18]
26: r [21,42,19,18] ==> [21,21,40,18]
27: l [21,21,40,18] ==> [21,41,20,18]
28: r [21,41,20,18] ==> [21,20,41,18]
29: r [21,20,41,18] ==> [21,20,20,39]
30: l [21,20,20,39] ==> [21,20,40,19]
31: l [21,20,40,19] ==> [21,40,20,19]
32: l [21,40,20,19] ==> [41,20,20,19]
33: r [41,20,20,19] ==> [20,41,20,19]
34: r [20,41,20,19] ==> [20,20,41,19]
35: r [20,20,41,19] ==> [20,20,20,40]
36: l [20,20,20,40] ==> [20,20,40,20]
37: l [20,20,40,20] ==> [20,40,20,20]
38: l [20,40,20,20] ==> [40,20,20,20]

Programm B ist nicht lösbar.

Um es mal ein bißchen mit Graphentheorie zu sagen: Die Zielmenge B befindet sich in einem unabhängigen Teilgraphen. Es gibt keine Beziehung zur Startmenge.

Scheinbar läßt die Art und Weise des umstapelns nicht alle möglichen Kombinationen zu, was eine kleine Statistik über den kompletten Graph zeigt:

Ecken: 2265 (mögliche Palettenverteilung)
Kanten: 3630 (Wege zwischen Palettenverteilungen)

IMHO müßte der Graph 101^3 Palettenverteilungen enthalten (ca. 1 Mio.).

Onkel Murray
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Giertzsch (bernoulli01)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Junior Mitglied
Benutzername: bernoulli01

Nummer des Beitrags: 8
Registriert: 07-2003
Veröffentlicht am Donnerstag, den 10. Juli, 2003 - 09:30:   Beitrag drucken

Hallo Onkel Murray!

Meinst du mit Ecken jetzt die Knoten,
oder Blätter des Graphen?

MFG
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Onkel Murray (murray)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: murray

Nummer des Beitrags: 208
Registriert: 10-2001
Veröffentlicht am Donnerstag, den 10. Juli, 2003 - 09:53:   Beitrag drucken

@Giertzsch: Wäre es ein Baum, dann hätte er Blätter, da es aber ein gerichteter Graph mit Schleifen ist (ein Baum hat keine Schleifen) meine ich die Knoten - und zwar in diesem Falle alle, welche mit dem Startknoten (100,0,0,0) erzeugbar sind.

Wenn man Blatt als Knoten definiert, welcher keine Kinder hat, dann gibt es in diesem Graph auch keine Blätter (sorry, kann nix dafür ).

Onkel Murray
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Onkel Murray (murray)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: murray

Nummer des Beitrags: 209
Registriert: 10-2001
Veröffentlicht am Donnerstag, den 10. Juli, 2003 - 10:02:   Beitrag drucken

Aber um den Spaß mal zu steigern:

Angenommen, der Typ der das Programm schreibt hat Pause während der Stapler stapelt. Dann möchte er doch möglichst ein langes Programm haben.
Das Problem ist nur, würde der Stapler sich in einer Schleife verfangen, käme das Program nie zum Ende. Auch würde es dem Chef auffallen wenn eine Kombination mehrfach vorhanden ist.

Dann grübelt mal schön

Onkel Murray

PS: Ich hab die Lösung schon, falls jemand verzweifelt kann ich auch Tips geben :-)

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page