Kleine Denkaufgabe

Fragen zu mathematischen Problemen
Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Kleine Denkaufgabe

Beitrag von cloidnerux » Mi Aug 03, 2011 10:30 pm

Ich würde das fast mit einer Art BubbleSort vergleichen. Nur, dass es sich hier nicht auf 1 Dimension beschränkt, sondern die Dimensionen gleich der Anzahl der Zwerge außen - 1 ist... sprich das Ganze ist ziemlich hässlich
Wir veranstalten keinen Schönheitswettbewerb :D
Ich wage zu behaupten, dass das obige System zwar für 3 Zwerge funktioniert, bei mehr Zwergen aber im Chaos ausartet, da sich durch das Umstellen wieder Umstellarbeiten ergeben werden, dadurch wieder und wieder und wieder.
Theorie und Realität sind doch immer noch 2 Welten^^
Hübsche Grafik aber keine Erklärung, wie drei Zwerge auf einem Klumpen entscheiden können, wer zusammengehört und wer
Dafür muss ich mich wohl noch entschuldigen.
Ich hatte gerade einen Overheap an Arbeit. Hab diese Grafik gemacht während ich parallel Render laufen hatte und nen Video bearbeitet hatte, an insgesamt 3 Monitoren.
Da ist das alles iwie untergegangen...
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Mi Aug 03, 2011 10:55 pm

Die Lösung ist übrigens trivial.


Das schrieb mein Mathelehrer auf'm Gym auch immer neben meine ausführlichen Berechnungen... aber der rechnete die Wurzel einer Zahl mit 5 Nachkommastellen auch schneller im Kopf als die meisten von uns die Aufgabe in den Rechner eingeben konnten.. ^^

Ansonsten macht sich Dirty Oerti auf dem richtigen Weg sich eine Zipfelmütze zu verdienen, aber er will ja demonstrativ nicht... Mit einem BubbleSort hat es aber nichts zu tun.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

ProgBeginner
Beiträge: 76
Registriert: Mo Jul 29, 2013 2:26 pm

Re: Kleine Denkaufgabe

Beitrag von ProgBeginner » Fr Okt 31, 2014 6:33 am

Die Zwerge stellen sich auf der Linie auf. Zunächst nur zweie. Angenommen, diese hätten dieselbe Mützenfarbe, rot: RR. Nun stellt sich ein Zwerg daneben, mit grüner Mütze: RRG. Alle weiteren Zwerge wählen nun, weil sie selber ja nicht genau wissen, welche Farbe ihre Mütze hat, genau die Grenze zwischen Rot und Grün, wobei die anderen auseinanderrücken. Während zunächst jeder Zwerg Betrachter ist, wird er zum Betrachtem. Die implizite Logik dabei ist also, daß er seine Rolle wechselt, in dem Moment, wo er sich auf der Line genau auf der Grenze zwischen Rot und Grün aufstellt. Es besteht daher kein Bedarf, daß jemand die Zwerge aufteilt, Kommunikation untereinander ist ebenfalls nicht nötig, um zum Ziel zu gelangen, aber nur dann, wenn wirklich jeder das Prinzip verstanden hat, genau weiß, was er zu tun hat, und vor allem - mitdenkt und diszipliniert handelt:

Code: Alles auswählen

       RR
       RRG
       RRGG
       RRGGG
      RRRGGG
     RRRRGGG
     RRRRGGGG
...
RRRRRRRRRGGGGGGGGGGG 
Verwechsle niemals Freie Software mit Freeware - da gibt es markante Unterschiede. Freie Software kann Geld kosten, Freeware ist aber selten frei.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Fr Okt 31, 2014 8:43 am

ProgBeginner hat geschrieben:Die Zwerge stellen sich auf der Linie auf. Zunächst nur zweie. Angenommen, diese hätten dieselbe Mützenfarbe, rot: RR. Nun stellt sich ein Zwerg daneben, mit grüner Mütze: RRG. Alle weiteren Zwerge wählen nun, weil sie selber ja nicht genau wissen, welche Farbe ihre Mütze hat, genau die Grenze zwischen Rot und Grün, wobei die anderen auseinanderrücken. Während zunächst jeder Zwerg Betrachter ist, wird er zum Betrachtem. Die implizite Logik dabei ist also, daß er seine Rolle wechselt, in dem Moment, wo er sich auf der Line genau auf der Grenze zwischen Rot und Grün aufstellt. Es besteht daher kein Bedarf, daß jemand die Zwerge aufteilt, Kommunikation untereinander ist ebenfalls nicht nötig, um zum Ziel zu gelangen, aber nur dann, wenn wirklich jeder das Prinzip verstanden hat, genau weiß, was er zu tun hat, und vor allem - mitdenkt und diszipliniert handelt:
[/code]
Selbst rausgefunden oder gegooglet? ^^

Richtig :-)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

ProgBeginner
Beiträge: 76
Registriert: Mo Jul 29, 2013 2:26 pm

Re: Kleine Denkaufgabe

Beitrag von ProgBeginner » Fr Okt 31, 2014 8:51 am

Gegoogelt - wobei ich in die Richtung durchaus schon gedacht habe - mit kleinen Abweichungen.
Ich habe lediglich gegoogelt, ob ich mit meiner Vermutung richtig liege.

Die Seite, wo ich das her habe, stellt eine interessante Frage, über die ich selber schon die ganze Zeit am rübeln bin.

Nehmen wir mal an, es sind DREI Farben im Spiel. Um eine 3. Farbe einzubringen, nehmen wir doch mal das Farbschema RGB, und wählen blau.

Bedingung bleibt bestehen, keiner weiß, was für eine Mütze er hat. Aufgabe wäre auch hier, eine schöne geordnete Reihe aufzustellen. OHNE Kommunikation der Zwerge untereinander.

Geht das mathematisch noch auf? Ich denke nicht. Zumindest nicht mit dazwischenstellen.

Wenn ich mich in die Situation mal hereinversetze - es sind 3 Farben im Spiel, somit 2 Grenzen, zwischen die ich mich stellen kann. Entweder ich stelle mich zwischen Rot und Grün, oder zwischen Grün und Blau. Die Chance, dass ich mich richtig stelle, liegt also 50:50 - denn ich habe ja 2 Auswahlmöglichkeiten.

Das Problem lös mal einer. Da versage ich soweit, dass ich nichtmal annähernd auf eine plausible Lösung käme.
Verwechsle niemals Freie Software mit Freeware - da gibt es markante Unterschiede. Freie Software kann Geld kosten, Freeware ist aber selten frei.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Kleine Denkaufgabe

Beitrag von cloidnerux » Fr Okt 31, 2014 10:18 am

Wenn ich mich in die Situation mal hereinversetze - es sind 3 Farben im Spiel, somit 2 Grenzen, zwischen die ich mich stellen kann. Entweder ich stelle mich zwischen Rot und Grün, oder zwischen Grün und Blau. Die Chance, dass ich mich richtig stelle, liegt also 50:50 - denn ich habe ja 2 Auswahlmöglichkeiten.
Und nun sollen die Zwerge statt einer Linie oder Kreis einen Stern mit 3 Richtungen aufbauen. Jeder zweig eine Farbe. Jeder neue Zwerg stellt sich genau in die Mitte.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Fr Okt 31, 2014 10:58 am

cloidnerux hat geschrieben:
Wenn ich mich in die Situation mal hereinversetze - es sind 3 Farben im Spiel, somit 2 Grenzen, zwischen die ich mich stellen kann. Entweder ich stelle mich zwischen Rot und Grün, oder zwischen Grün und Blau. Die Chance, dass ich mich richtig stelle, liegt also 50:50 - denn ich habe ja 2 Auswahlmöglichkeiten.
Und nun sollen die Zwerge statt einer Linie oder Kreis einen Stern mit 3 Richtungen aufbauen. Jeder zweig eine Farbe. Jeder neue Zwerg stellt sich genau in die Mitte.
Prinzipiell richtig.... hauptsache ist, dass der Zwerg genau erkennen kann, wohin er gehen muss, damit die Bedingung, dass alle gleichfarbigen Mützen beisammenstehen, weiterhin erfüllt ist. :-)

Das ganze wird aber von einem eindimensionalen Problem zu einem zweidimensionalen. Das heißt, der dritte Zwerg (bzw. der erste mit der dritten Farbe) muss wissen, ob er sich zwischen die beiden anderen stellt (was bei einem eindimensionalen Problem die einzige Möglichkeit ist) oder ob er die zusätzliche Dimension begründet und die dritte Farbe gründet. Nur so kann der Nachfolger entscheiden, wo der Mittelpunkt aller drei Farben ist. Das ganze funktioniert also erst, wenn alle Farben auf einen Punkt zusammenlaufen. Solange nicht alle Farben da sind, ist der Mittelpunkt/Ankunftspunkt nicht markiert.

Es findet mehr Kommunikation statt. Auf einer Geraden geht der Zwerg zwischen die Farben und die Gruppen rücken vom Mittelpunkt ab. Bei einer unendlich großen Geraden, werden einfach die Abstände zwischen den Zwergen in der Mitte immer kleiner. Man kommt also ohne Kommunikation aus, dafür verschiebt sich die Mitte laufend. Bei einem zweidimensionalen Problem, ist der Mittelpunkt da, wo sich die Achsen kreuzen. Verschiebung würde hier doch Kommunikationsbedarf bedeuten, genauso wie den Zwerg im Mittelpunkt entlang seiner Farbachse zu verschieben.

Nicht ganz so trivial, wie es am Anfang aussah. ^^
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Kleine Denkaufgabe

Beitrag von cloidnerux » Fr Okt 31, 2014 12:35 pm

Das ganze wird aber von einem eindimensionalen Problem zu einem zweidimensionalen. Das heißt, der dritte Zwerg (bzw. der erste mit der dritten Farbe) muss wissen, ob er sich zwischen die beiden anderen stellt (was bei einem eindimensionalen Problem die einzige Möglichkeit ist) oder ob er die zusätzliche Dimension begründet und die dritte Farbe gründet. Nur so kann der Nachfolger entscheiden, wo der Mittelpunkt aller drei Farben ist. Das ganze funktioniert also erst, wenn alle Farben auf einen Punkt zusammenlaufen. Solange nicht alle Farben da sind, ist der Mittelpunkt/Ankunftspunkt nicht markiert.
Es funktioniert egt sehr gut.

Nehmen wir an wir haben die Farben A, B, C ohne konkrete Zuordnung.

Der erste Zwerg der kommt hat die Farbe A per Definition.
Der nächste Zwerg hat jetzt entweder die Farbe A oder B(per Definition). Ignorieren wir erstmal den Fall "Farbe A", haben wir also die Struktur Nun solange kein Zwerg mit Farbe C kommt, ist dies das ursprüngliche Problem.
Schauen wir nun an, was mit dem ersten C passiert(Beispielhaft):

Code: Alles auswählen

...AAACBBB...
Nun kommt der nächste Zwerg, sieht die Situation und "schiebt" C eine Reihe nach oben:

Code: Alles auswählen

         C
...AAAXBBB...
Das Verschieben an sich ist keine Kommunikation, da jedem einzelnen nur eine Position(index) Änderung vermittelt wird, Schaut sich jedoch jeder einzelne Zwerg um, kann er natürlich aus der Konstellation seine eigene Farbe erkennen, bzw die Abgrenzungen ermitteln. Das setzt aber auch das Verlangen und die Möglichkeit jedes Einzelnen vor raus, diese Informationen aus der Umgebung zu extrahieren.

Weiter in der Simulation.
Mit dem letzten hinzugekommenen Zwerg, den ich mit "X" markiert habe, wird es natürlich interessant. X kann jetzt ein Element aus {A, B, C} sein, nehmen wir an es sei A(wegen Symmetrie egal welche Farbe):

Code: Alles auswählen

         C
...AAAABBB...
Es sind immer noch alle Gruppen beisammen, nur muss jetzt ein Shift des Mittelpunktes passieren. Das passiert mit dem nächsten Zwerg:

Code: Alles auswählen

           C
...AAAACBBB...
Dieser stellt sich an die Grenze zwischen den Gruppen und alle richten sich per Algorithmus zu diesem als Mittelpunkt aus.
Das sorgt dafür, dass auch in einem Fall mit 3 Farben alle in ihre Gruppe finden.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Kleine Denkaufgabe

Beitrag von Xin » Fr Okt 31, 2014 1:49 pm

cloidnerux hat geschrieben:Weiter in der Simulation.
Mit dem letzten hinzugekommenen Zwerg, den ich mit "X" markiert habe, wird es natürlich interessant. X kann jetzt ein Element aus {A, B, C} sein, nehmen wir an es sei A(wegen Symmetrie egal welche Farbe):

Code: Alles auswählen

         C
...AAAABBB...
Es sind immer noch alle Gruppen beisammen, nur muss jetzt ein Shift des Mittelpunktes passieren. Das passiert mit dem nächsten Zwerg:

Code: Alles auswählen

           C
...AAAACBBB...
Dieser stellt sich an die Grenze zwischen den Gruppen und alle richten sich per Algorithmus zu diesem als Mittelpunkt aus.
Das sorgt dafür, dass auch in einem Fall mit 3 Farben alle in ihre Gruppe finden.
Was wenn der Zwerg ebenfalls ein A ist?

Code: Alles auswählen

           C
...AAAAABBB...
und jetzt kommen weitere A Zwerge?

Code: Alles auswählen

           C
...AAAAAAAAAAAAABBB...
Und dann zwei C-Zwerge

Code: Alles auswählen

           C               C
...AAAAAAAAAAAAACBBB...
Der erste C-Zwerg muss entweder an der Grenze bleiben und darauf achten oder wir haben jetzt 4 Gruppen bei drei Farben.

Das Schieben stellt eine Kommunikationsform dar, denn es teilt den C-Zwergen mit, dass sie aus der ersten Dimension ausscheiden, ergo wissen sie hiermit ihre Mützenfarbe und diese Wissensübergabe findet nur deswegen statt, weil sie geschoben werden. Die A und B Zwerge können dies nicht erkennen, müssen aber auch nicht geschoben werden. Daher findet hier gar keine Kommunikation statt.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

ProgBeginner
Beiträge: 76
Registriert: Mo Jul 29, 2013 2:26 pm

Re: Kleine Denkaufgabe

Beitrag von ProgBeginner » Fr Okt 31, 2014 2:51 pm

Ich wollte es gerade sagen.

Wenn ich jemanden berühre oder an die Seite schiebe oder sowas, ist das Kommunikation. Da kann ich ihm genauso kommunikativ mitteilen "Ey Hannes ... Stück mal n Rück" :D - die Reaktion wird die Gleiche sein: Hannes stückt mal n Rück. :D

No Touch, no speech, no communication anyway.
Und nein - ich habe auch noch keine Lösung, ich bin auch noch am Grübeln. Für 4 Farben wüsst ich nen Weg ... aber das ist hier ja nicht gefragt - es geht um 3. ;)
Verwechsle niemals Freie Software mit Freeware - da gibt es markante Unterschiede. Freie Software kann Geld kosten, Freeware ist aber selten frei.

Antworten