|
|
|
|
Mal wieder Kugeln... |
|
| Autor |
Beitrag |
|
 11.08.05
Lounge Gast
| Mal wieder Kugeln... |
Aber noch verzwickter als das 12-Kugelproblem (finde ich).
Fünf Kugeln mit unterschiedlichem Gewicht. Balkenwaage, gewogen (also verglichen) werden jeweils genau zwei Kugeln (also pro Waagschale genau eine Kugel). Die Kugeln sind nach Gewicht zu sortieren. Wieviele Vergleiche benötigt man höchstens?
;-) Karl
|
[auf diesen Beitrag antworten]
| |
Passende Anzeigen
|
|
|
|
|
|
15.08.05
Lounge Gast
| Re: Mal wieder Kugeln... |
3
|
[auf diesen Beitrag antworten]
|
|
20.09.05
Lounge Gast
| Re: Mal wieder Kugeln... |
Sorry für die verstrichene Zeit, es kam ein längerer Urlaub dazwischen :-)
3??? Wie soll das gehen? Soviel braucht Du schon für drei Kugeln, zur Verdeutlichung:
Die Kugeln seien a,b und c benannt.
1 a --*-- b a sei leichter als b (andernfalls werden sie schnell umbenannt).
2 c --*-- a , falls ca: c --*-- b, falls c>b Lösung a b c, sonst a c b
Bei 4 Kugeln würde wohl (im Fall a b c) folgen
4 d --*-- b
5 wenn d>b: d --*-- c . wenn d>c Lösung a b c d, sonst a b d c
5 wenn da Lösung a d b c, sonst d a b c
Also: Wieviele Wägungen bei 5 Kugeln maximal (!!) (die optimale Strategie natürlich vorrausgesetzt)?
Karl
|
[auf diesen Beitrag antworten]
|
|
16.11.05
Lounge Gast
| Re: Mal wieder Kugeln... |
10 ... 4+3+2+1
|
[auf diesen Beitrag antworten]
|
|
29.11.05
Lounge Gast
| Re: Mal wieder Kugeln... |
> 10 ... 4+3+2+1
Wie kommst Du darauf?
Theoretische Abschätzung dazu: 5 verschieden schwere Kugeln können 120 Permutationen bilden (5!, 1*2*3*4*5). Das System
kann also 120 Zustände einnehmen, man benötigt also
Informationen von ld 120= 6,9 Bit. Die Waage liefert pro Wägung
1 Bit ( a < b oder a>b, Entscheidung zwischen 2 Zuständen, ld 2=1). Also könnten 7 Wägungen (7*1 Bit) ausreichen.
"Könnten" weil die Informationsabschätzung zwar notwendige, aber nicht hinreichende Ergebnisse liefert. Das 12-Kugelproblem (eine leichter oder schwerer) z.B. müsste über die Abschätzung alleine auch mit 13 Kugelen lösbar sein.
Beim Kugelsortieren kommt man aber tatsächlich mit 7 Wägungen hin. Später werden ich mal den zugehörigen Entscheidungsbaum posten, vielleicht wollen es ja noch der eine oder andere selbst versuchen!
|
[auf diesen Beitrag antworten]
|
|
29.11.05
Lounge Gast
| Re: Mal wieder Kugeln... |
also diesen bit-kram versteh ich kein bisschen, aber pro kugel mehr braucht man bei n anzahl der kugeln n-1 versuche mehr dachte ich?
|
[auf diesen Beitrag antworten]
|
|
29.11.05
Lounge Gast
| Re: Mal wieder Kugeln... |
> n anzahl der kugeln n-1 versuche mehr dachte ich?
Ach, jetzt verstehe ich. Du denkst an teilsortierte Listen,
in die Du jeweils die nächste Kugel durch paarweisen Vergleich
einsortierst und berücksichtigst den worst case.
Das geht aber effektiver, wenn die neue Kugel nicht "vom Rand aus"
einsortiert wird sondern von der Mitte her - so braucht es z.B. nur
zwei Vergleiche, um die vierte Kugel in die *sortierte* 3er Liste
einzusortieren: Ist sie schwerer als die Mittlere, muss nur noch
gegen die Leichteste gewogen werden (und gegen die Schwerste im
anderen Fall).
Aber bei dieser Aufgabenstellung kommst Du aber mit dem
"teilsortierte Listen" - Konzept auf bestenfalls 8 Versuche ;-)
|
[auf diesen Beitrag antworten]
|
|
29.11.05
Lounge Gast
| Re: Mal wieder Kugeln... |
> Ist sie schwerer als die Mittlere, muss nur noch gegen die Leichteste gewogen werden
Quatsch, umgekehrt natürlich!
|
[auf diesen Beitrag antworten]
|
|
29.11.05
Lounge Gast
| Re: Mal wieder Kugeln... |
gib mal n konkretes beispiel, wie es bei dir mit 7 geht?
|
[auf diesen Beitrag antworten]
|
|
01.03.06
Lounge Gast
| Re: Mal wieder Kugeln... |
Die Frage war, wieviele Waegungen man hoechstens braucht.
Und das sind nicht sieben, sondern zehn. Mit wievielen man "hinkommt" ist egal.
Und wie kommt man auf die 6,9 Bit?
|
[auf diesen Beitrag antworten]
|
|
11.05.06
Lounge Gast
| Re: Mal wieder Kugeln... |
> Und das sind nicht sieben, sondern zehn.
Nein. Als Beispiel das gleiche Rätesel mit nur 4 Kugeln. Nach Deiner Logik wären es 1+2+3 = 6 Wägungen, richtig? Und ich behaupte, nach folgendem Verfahren sind es *immer* *höchstens* 5.
1. Wägung: b und c, soll b < c ergeben. Reihenfolge: bc
2. Wägung: a und c, ergibt a
|
[auf diesen Beitrag antworten]
|
|
11.05.06
Lounge Gast
| Re: Mal wieder Kugeln... |
oops- es gibt hier inzwischen Ptzbeschränkungen..-(
3. Wägung: a und b, ergibt, wenn a b, wird d mit c verglichen. Es ergibt sich die endgültige Reihenfolge abcd bezw. abdc!
War (in der 4. Wägung) d 6,9 Bit?
In der Informationstheorie ist ein Bit als negativer dualer Logarithmus der Auftretenswahrscheinlichkeit definiert. Die 5 Kugeln können in 120 verschiedene Anordnungen gebracht werden, somit hat (bei Gleichwahrscheinlichkeit der Zustände) ein System den Informationsgehalt -ld(1/120) = ld 120 = 6,9.
In diesem Fall kann man das auch einfacher betrachten, es kommt mathematisch auf das gleiche hinaus: Es gibt 120 Möglichkeiten, die Kugeln anzuordnen. Es gibt 128 Möglichkeiten, wie sich die Waage bei 7 Wägungen jeweils verhält: 2*2*2*2*2*2*2 = 2^7 = 128, das sind *mehr* Möglichkeiten als die der Kugeln, *grundsätzlich* spricht also nichts gegen ein Machbarkeit mit 7 Wägungen.
|
[auf diesen Beitrag antworten]
|
|
11.05.06
Lounge Gast
| Re: Mal wieder Kugeln... |
nochmal..
3. Wägung: a und b, ergibt, wenn a b, wird d mit c verglichen. Es ergibt sich die endgültige Reihenfolge abcd bezw. abdc!
War (in der 4. Wägung) d
|
[auf diesen Beitrag antworten]
|
|
11.05.06
Lounge Gast
| Re: Mal wieder Kugeln... |
...ich geb's auf
|
[auf diesen Beitrag antworten]
|
|
11.05.06
Moderator Jörg
| Re: Mal wieder Kugeln... |
Hi,
du scheinst ein Sonderzeichen zu verwenden, das als html-Code interpretiert wird. Versuchs nochmal ohne das Zeichen oder schick mir dein Posting per Mail, dann ergänze ich das.
Sorry
Jörg
Wissen ist das einzige Gut, das sich vermehrt, wenn man es teilt.
|
[auf diesen Beitrag antworten]
|
|
11.05.06
Lounge Gast
| Re: Mal wieder Kugeln... |
Hallo Jörg, könnt ein < mit direkt folgendem Bustaben sein.
Kannst Du den entstandenen Müll rausschmeissen?
> Und das sind nicht sieben, sondern zehn.
Nein. Als Beispiel das gleiche Rätesel mit nur 4 Kugeln. Nach Deiner Logik wären es 1+2+3 = 6 Wägungen, richtig? Und ich behaupte, nach folgendem Verfahren sind es *immer* *höchstens* 5.
1. Wägung: b und c, soll b < c ergeben. Reihenfolge: bc
2. Wägung: a und c, ergibt a < c (also der *schlechte* Fall)
3. Wägung: a und b, ergibt, wenn a < b ist abc, sonst bac
Annahme: abc
4. Wägung: d wird mit **b** verglichen (es ist hier _nicht_ egal, mit welcher verglichen wird,"angefangen" wird immer in der Mitte).
5. Wägung: War d > b, wird d mit c verglichen. Es ergibt sich die endgültige Reihenfolge abcd bezw. abdc!
War (in der 4. Wägung) d < b, wird d mit a verglichen. Es ergibt sich die endgültige Reihenfolge dabc bezw. adbc!
q.e.d
> 6,9 Bit?
In der Informationstheorie ist ein Bit als negativer dualer Logarithmus der Auftretenswahrscheinlichkeit definiert. Die 5 Kugeln können in 120 verschiedene Anordnungen gebracht werden, somit hat (bei Gleichwahrscheinlichkeit der Zustände) ein System den Informationsgehalt -ld(1/120) = ld 120 = 6,9.
In diesem Fall kann man das auch einfacher betrachten, es kommt mathematisch auf das gleiche hinaus: Es gibt 120 Möglichkeiten, die Kugeln anzuordnen. Es gibt 128 Möglichkeiten, wie sich die Waage bei 7 Wägungen jeweils verhält: 2*2*2*2*2*2*2 = 2^7 = 128, das sind *mehr* Möglichkeiten als die der Kugeln, *grundsätzlich* spricht also nichts gegen ein Machbarkeit mit 7 Wägungen.
|
[auf diesen Beitrag antworten]
|
|
|
|
|
|
| |
![[home]](../gfx/b_home.gif)
![[sitemap]](../gfx/b_sitemap.gif)
![[feedback]](../gfx/b_feedback.gif)
