| Autor |
Beitrag |
    
Martin
| | Veröffentlicht am Sonntag, den 10. Dezember, 2000 - 20:30: | 
|
Jemand hat fünf verschiedenschwere aber gleichaussehende Kugeln und soll sie dem Gewicht nach ordnen. Dazu darf er die Kugeln siebenmal auf einer Balkenwaage (ohne zusätzliche Gewichte) abwiegen. Ist das möglich???
Ich bin trotz tagelangem Herumprobieren auf keine Lösung gekommen und konnte auch nicht beweisen, dass es keine gibt. (5!<2^7) |
DIZZI
| | Veröffentlicht am Mittwoch, den 20. Dezember, 2000 - 13:28: |
|
Hi ,
Meiner Meinung nach benötigt man im worst case
immer noch 8 Versuche !
Mit 7 geht es m.E. nicht.
Gruss DIZZI |
Martin
| | Veröffentlicht am Mittwoch, den 20. Dezember, 2000 - 14:51: |
|
Hi,
ich glaube auch, dass das nicht mit 7 Versuchen geht, aber kann man das auch beweisen? (ohne alle Möglichkeiten auszuprobieren)
Viele Grüße,
Martin |
DIZZI
| | Veröffentlicht am Donnerstag, den 21. Dezember, 2000 - 09:03: |
|
back again,
die Frage ist, was ist ein Beweis ?
Zwangsläufig eine mathematische Herleitung ?
Ich kann bei Anwendung des binary search
algorithmus zeigen, dass der schlechtest
mögliche Fall 8 Versuche benötigt.
Natürlich geht es auch mit weniger !!
(z.B. mit 7).
Es geht auch mit 6 Versuchen eindeutig ! Dazu
muss aber eine bestimmte Ausgangslage herrschen,
bzw. man die Kugeln in einer entsprechenden
Reihenfolge ziehen.
Wie gesagt, bei gewissen Reihenfolgen benötigt man
nach obigen Verfahren 6-8 Wägungen, um
die Sortierung eindeutig zu machen.
so far so good
bye
DIZZI |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 23. Dezember, 2000 - 00:36: |
|
Hallo DIZZI,
du hast ein Verfahren ("binary search algorithm"), bei dem im schlechtest möglichen Fall acht Wiegungen notwendig sind.
Heißt das aber, dass es kein Verfahren gibt, dass auf jeden Fall mit sieben Wiegungen auskommt?? |
DIZZI
| | Veröffentlicht am Dienstag, den 26. Dezember, 2000 - 20:13: |
|
Hi ZAPH,
meines Wissens gibt es kein solches verfahren.
Das wäre 1. unglaublich und
2. für mich hochinteressant.
Falls irgendjemand etwas weiss, so wäre ich brennend
daran interessiert; aber ich bezweifele dies
absolut.
Nur: Wie lässt sich dies beweisen.
Grus
DIZZI |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Mittwoch, den 27. Dezember, 2000 - 22:34: |
|
Hallo Allerseits
Wenn man immer nur zwei Kugeln gegeneinander wiegen darf, so braucht jeder Sortieralgorithmus im Durchschnitt mindestens n*log2n Vergleiche. Das sind in unserem Fall sind das etwas mehr als 7, also muss es einen Fall geben, in dem 7 Versuche nicht ausreichen.
Das einzige, was mir im Moment noch Kopfzerbrechen bereitet, ist, ob es was bringt, mehr als zwei Kugeln auf die Waage zu legen. Dann könnte man womöglich doch auf 7 Versuche kommen.
viele Grüße
nachträglich Frohe Weihnachten
und ein frohes neues Jahrtausend
SpockGeiger |
DIZZI
| | Veröffentlicht am Donnerstag, den 28. Dezember, 2000 - 11:06: |
|
Hi SpockGeiger,
dies mit dem n*log n bezweifele ich.
Wieso sollte jeder!!! sortieralg. im durchschnitt
soviele versuche benötigen ?
Ich meine es kommt auf dem alg. als solchen an.
oder, wie kommst du auf so eine allgemeingültige
Formel ?
Es gibt sortieralg. die haben keinen
"Durchschnitt", sondern immer eine konstante Anzahl
von Wägungen.
Deine Idee mit mehr als 2 Kugeln auf einer
Waag-schale ist zwar eine gute Idee,
bringt uns aber m.E. nicht weiter.
Du musst jedenfalls, bei 2 Kugeln auf
einer Schale, rückschlüsse auf jede einzelne
ziehen, um jede Kugel in die richtige
Reihenfolge zu bringen.
Nun noch folgendes : Du willst 1 Mio. Kugeln der
Reihe nach sortieren.
Man kann nun versch. Algorithmen vergleichen.
Wieviele Wägunen benötigst du für einen
Algorithmus bestenfalls oder schlechtestenfalls
dafür (oder im Durchschnitt) ?
Gruss DIZZI |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Donnerstag, den 28. Dezember, 2000 - 23:30: |
|
Hallo Dizzy
Ich habe mich vielleicht etwas mißverständlich ausgedrückt. Mit "Jeder
Algorithmus braucht im Durchschnitt mindestens n*log n Vergleiche" Es
ist klar, dass man Algorithmen konstruieren kann, die länger brauchen, was
ich aber aussagen wollte, ist, man kann diese Zahl nicht unterschreiten, sie
ist eine untere Schranke. Es geht einfach nicht schneller. Diese Schranke
haben wir im zweiten Semester Informatik bewiesen. Allerdings muss ich mich
auch entschuldigen, ich habe mich vertan, die Anzahl ist nur ordnungsmäßig
gleich n*log n, nicht genau die Zahl, also stimmte der Beweis nicht. Wie
schon erwähnt, ist 5!<2^7, also könnte es rein theoretisch gehen. Das
Probelm ist nur, man hat sehr wenig Spielraum für redundante Wägungen.
Wieso haben Algorithmen mit konstanter Laufzeit keinen Durchschnitt??? Dann
ist doch der Durchschnitt gerade diese konstante Zeit oder auch Anzahl der
Vergleiche.Und eben darum geht es ja auch hier. Wir versuchen einen
Algorithmus zu finden, der die Fünf Kugeln garantiert mit 7 Wägungen
sortiert. Wenn die Formel auch exakt richtig wäre, dann wären wir doch
fertig.
Ich versuche nochmal, den Durchschnitt klarzustellen: Zu einem
gegebenen Algorithmus nimmt man alle möglichen Eingaben (hier der Länge
n), betrachtet zu jeder möglichen Eingabe (das sind hier n! Stück) die
Anzahl der Vergleiche, summiert sie auf, und dividiert diese Zahl durch die
Anzahl der Möglichkeiten.
viele Grüße
SpockGeiger |
|
