Algorithmus (Wiegen)
-
Ein allgemeines Muster erkenne ich noch nicht so wirklich, ich beginne aber vielleicht mal mit dem Fall, daß man 9 Münzen hat:
Hier würde ich drei 3er-Gruppen bilden.
Dann nehme ich mir zwei der drei 3er-Gruppen her und vergleiche sie mit der Balkenwaage.1. Wiegen:
Möglichkeit 1:
Beide Gruppen gleich schwer: Gesuchte Münze ist in der dritten Gruppe.
Nimm die dritte Gruppe her. Bilde eine 2er-Gruppe und eine 1-er Gruppe.
Vergleiche die beiden Münzen der 2er-Gruppe. Ist eine der Münzen schwerer, so ist diese die gesuchte Münze. Steht die Waage im Gleichgewicht, ist die Münze aus der 1er-Gruppe die gesuchte Münze.
Also 2 Mal wiegen insgesamtMöglichkeit 2:
Die eine 3er-Gruppe Gruppe ist schwerer als die andere.
Nimm diese Gruppe her und teile sie in eine 2er-Gruppe und eine 1er-Gruppe.
Nimm die 2er-Gruppe her und vergleiche die beiden Münzen. Ist eine schwerer als die andere, ist diese die gesuchte Münze. Sind beide gleich schwer ist die Münze aus der 1er-Gruppe die gesuchte Münze.
Also auch hier: 2 Mal wiegen insgesamtAntwort zu Frage b): 2 Mal wiegen
-----
Falls dies nun so besser ist, weiß ich aber nicht, wie ich dieses Vorgehen verallgemeinern kann.
-
Du kannst nicht immer 2 Wiegevorgange erreichen. Das geht nur bis zu 9 Münzen, darüber brauchst du mehr. Aber die Taktik ist doch schon gut. Wie würdest du es denn bei 3 Münzen machen? Bei 4? Bei 8? Wenn du dies beantworten kannst, dann kommst du bestimmt auch auf die Taktik für 10 Münzen. Und für 28. Und dann für N.
-
Bei 3 Münzen würde ich eine 2er-Gruppe und eine 1er-Gruppe bilden.
Dann die beiden Münzen aus der 2er-Gruppe vergleichen. Ist eine dieser beiden Münzen schwerer als die andere Münze, so ist diese die gesuchte Münze.
Wenn nicht, so ist die Münze, die die 1er-Gruppe bildet, die gesuchte Münze.
Man muss also nur 1 Mal wiegen.Bei 4 Münzen würde ich zwei 2er-Gruppen bilden, dann eine der 2er-Gruppen hernehmen. Ist eine der Münzen schwerer als die andere Münze, ist diese die gesuchte Münze. Sind beide Münzen gleich schwer, werden die beiden anderen Münzen gewogen, die schwerere ist die gesuchte.
Bei 8 Münzen würde ich zwei 4er-Gruppen bilden und dann entsprechend verfahren.
Bei 10 Münzen würde ich zwei 5er-Gruppen bilden.
Bin ich auf dem Holzweg?
-
LinuxC_newbie schrieb:
Bei 8 Münzen würde ich zwei 4er-Gruppen bilden und dann entsprechend verfahren.
Bei 10 Münzen würde ich zwei 5er-Gruppen bilden.
Bin ich auf dem Holzweg?Naja, Dein erster Algo hat pro Wägung zwei Kugeln verbraucht und am Ende im schlimmsten Fall ungefähr N/2 Wägungen gebraucht.
Der Neue tut pro Wägung die Hälfte der Kugeln verbrauchen und am Ende im schlimmsten Fall ungefähr log2(N) Wägungen brauchen, also fast nichts. Bei 1000000 Kugeln nur 20 Wägungen statt vorher 500000. Hast Deine Brötchen schon verdient.Aber es geht noch schärfer. Vorher gibt es keine Kekse.
-
LinuxC_newbie schrieb:
Bin ich auf dem Holzweg?
Wieso gehst du denn bei 3 und 9 anders vor als bei 4, 8 und 10?
Bei 8 würdest du ja 3 Wiegevorgänge brauchen, was mehr ist als du oben für 9 vorgeschlagen hast. Wie kann das denn sein?
-
Also man teilt immer in drei Gruppen ein, wobei zwei Gruppen gleich groß sein müssen und die dritte Gruppe kleiner als die beiden anderen.
Aber ab welcher Anzahl von Münzen klappt das?
Für drei oder vier Münzen klappt das doch z.B. nicht, oder?
-
LinuxC_newbie schrieb:
Also man teilt immer in drei Gruppen ein, wobei zwei Gruppen gleich groß sein müssen und die dritte Gruppe kleiner als die beiden anderen.
Aber ab welcher Anzahl von Münzen klappt das?
Für drei oder vier Münzen klappt das doch z.B. nicht, oder?Lassen wir mal die Fälle unter 9 erstmal weg.
Um ein Gefühl für den allgemeinen Fall zu bekommen.Und dann entweder für unter 9 einfach mit if eine Sonderregel machen. Oder überraschenderweise passt da auch der allgemeine Fall. Das würde ich sogar vermuten.
-
LinuxC_newbie schrieb:
Also man teilt immer in drei Gruppen ein, wobei zwei Gruppen gleich groß sein müssen und die dritte Gruppe kleiner als die beiden anderen.
Das ist noch ein wenig schwammig. Bei 100 Kugeln könnte man also Gruppen zu 49-49-2 oder 48-48-4 oder 47-47-6 oder... und so weiter machen.
Welche Gruppeneinteilung würdest Du denn vorschlagen? Welche wird wohl die schärfste sein? Kannst ja schlecht einen Algo anbieten, der die Einteilung so offen läßt. Wie sollte man den dann berechnen?
-
Ich würde das immer so machen, daß ich 1 oder 2 Kugeln übrig habe, also immer auf die nächste durch 2 teilbare Zahl gehen.
Also z.B. bei 33 Kugeln, dann auf 32 gehen, also 16-16-1
oder bei 100
49-49-2
-
LinuxC_newbie schrieb:
Ich würde das immer so machen, daß ich 1 oder 2 Kugeln übrig habe, also immer auf die nächste durch 2 teilbare Zahl gehen.
Also z.B. bei 33 Kugeln, dann auf 32 gehen, also 16-16-1
oder bei 100
49-49-2
Das ist ja an sich schon schlau. Aber das hat ein Problem:
Im Normalfall sagt die Waage nur LINKS oder RECHTS und fast nie GLEICH.
Falls sie mal GLEICH sagt, ist die eine Restkugel sofort identifiziert.Hast also einige Fälle der Sofort-Identifikation und die bezahlst Du im Gegenzug durch längeren Worst-Case.
Wir erinnern uns an den ersten Algo. Da war ja Sofort-Identifikation an der Tagesordnung und der Worst-Case war astronomisch.
-
Das ist ja alles ganz schön verstrickt.
Ist es also klüger die Größe der kleinsten Gruppe möglichst groß zu wählen?
Also etwa bei 100 Kugeln 40-40-20?
Oder 35-35-30?Oder gibt's da keine perfekte Antwort?
-
LinuxC_newbie schrieb:
Ist es also klüger die Größe der kleinsten Gruppe möglichst groß zu wählen?
Jo, klar! Für den Algo mit dem billigsten Worst-Case must die Waage die im nächsten Schritt zu prüfende Gruppe (egal, ob sie RINKS, LECHTS oder GLEICH sagt) so klein wie möglich machen.
Das leuchte ein, oder?
-
Das verstehe ich nicht.
Was ist an 35-35-30
besser als an
49-49-2?
Denn dann ist doch der best-case dafür schlechter?
-
LinuxC_newbie schrieb:
Das verstehe ich nicht.
Was ist an 35-35-30
besser als an
49-49-2?
49-49-2
Falls die Waage GLEICH sagt, haste im zweiten Zug gewonnen, lecker.Falls die Waage LINKS oder RECHTS sagt, haste im zweiten noch N=49 zu lösen statt nur N=35.
Es fühlt sich doch gleich mal so an, daß N=35 bestimmt nicht länger dauert als N=49.
-
Dafür ist ja aber auch der best-case deutlich schlechter - oder zählt das nicht?
-
LinuxC_newbie schrieb:
Dafür ist ja aber auch der best-case deutlich schlechter - oder zählt das nicht?
Das zählt erstmal nicht.
Erstmal den Worst-Case analysieren.Typischerweise sind bei Teile-Und-Herrsche-Algorithmen mit Zufallsdaten der Worst-Case und der Average-Case nur um 1 entfernt. Davon gehe ich hier auch mal aus.
Wir beide können den allerbesten Algo für den Worst-Case zusammenfrickeln. Interessant wäre noch der Average-Case.
Es gibt nämlich zwei Sorten von Kunden:
a) Der Zocker, der will, daß sein Game möglichst nicht ruckelt. Er braucht den billigsten Worst-Case. Gamecoder optimieren den Worst-Case.
b) Der Sysadmin, der unglaubliche Mengen an Daten durchnudelt und am nächsten morgen die Ergebnisse anschaut. Ihm ist der Average-Case wichtig. Null Problemo, wenn mal ein blöder Datensatz rumzickt.
Zum Glück hat sich SeppJ angeboten, dann den Average-Case zu berechnen. (Puh, Glück gehabt.) Naja, er hat ihn überhaupt erst ins Spiel gebracht, obwohl die Aufgebenstellung deutlich vom Worst-Case redet.
-
LinuxC_newbie schrieb:
Dafür ist ja aber auch der best-case deutlich schlechter - oder zählt das nicht?
Uns interessiert erst einmal nur der Mittelwert und der Worst Case. Bubblesort hat auch einen tollen Best Case, trotzdem ist das ein mit Absicht schlecht gemachtes Sortierverfahren.
-
Zum Glück hat sich SeppJ angeboten, dann den Average-Case zu berechnen. (Puh, Glück gehabt.) Naja, er hat ihn überhaupt erst ins Spiel gebracht, obwohl die Aufgebenstellung deutlich vom Worst-Case redet.
Morgen! Heute ist zu spät. Außerdem will ich erst einmal vom Threadersteller den Algorithmus sehen.
volkard schrieb:
b) Der Sysadmin, der unglaubliche Mengen an Daten durchnudelt und am nächsten morgen die Ergebnisse anschaut. Ihm ist der Average-Case wichtig. Null Problemo, wenn mal ein blöder Datensatz rumzickt.
Da steckt der Teufel im Details. Falls der Worst Case zu schlecht ist, dann bekommt auch der Sysadmin Probleme. Es gibt eine Denial of Service Attacke, bei der ein Angreifer einem Serverprogramm gezielt einen (an sich gültigen) Datensatz gibt, der dann in dem Programm zu einem besonders schlechten Worst Case führt überproportional Rechenzeit pro Anfrage verbraucht. So wird der Server mit wenigen Anfragen lahmgelegt.
Ja, das ist ein anderer Sysadmin, als der, den du meintest.
-
Nebenher: Irgenwann mal gelesen, vermutlich von Martin Gardner, und aus freier Erinnerung bestimmt fürchterlich entstellt.
Nach dem Giftmord auf einer größeren Party wissen wir:
Es gibt viele benutze Gläser. Eins davon hatte Gift drin. Dessen Fingerabdrücke brauchen wir! Die Gift-Analyse einer Probe kostet viel Geld. Deswegen schütten wir gerne Mikrotropfen von Gläsern zur Analyse zusammen, um dann Mischungen aus Gläsern zu analysieren. Die Gift-Analyse ist voll genau, sobald eines der beteiligten Gläsern Gift drin hatte, schlägt er gut aus.
Es wurde eine Mathe-Prof herbeigeholt mit dem Auftrag, die maximalen Ausgaben für die Gift-Analyse bei optimalem Vorgehen vorher zu berechnen und das hatte man vor dem Analysieren dann von der Buchhaltung auch absegnen lassen.Und er führete dann auch natürlich das Vorgehen. Der Prof nahm ein willkürliches Glas und sagte "Untersucht das mal". Empörung, weil er anscheinend keine Zusammenschütt-Strategie angestebt hatte! Er aber sagte "Nee, ist nicht schlimm, wir werden sicher nicht deswegen mehr Untersuchungen bezahlen müssen als nötig".
Der Detektiv erinnert sich genau, daß es nicht weniger als 100 und nicht mehr als 200 Gläser gab.a) Wieviele Gläser waren es?
b) Wieviele Untersuchungen wären durchschnittlich eingespart worden, wenn der Mathe-Prof den Auftrag gehabt hätte, die zu erwartenden Kosten zu minimieren?
-
So grob über den Daumen gepeilt würde ich schätzen
a) 129
b) 121/129 ≈ 0.938
