Algorithmus (Wiegen)

LinuxC_newbie

Danke für Eure Antworten.

Mir ist noch folgende Idee gekommen.

Sei die Anzahl der Münzen gerade.

Dann bilde zwei Gruppen mit n/2 Münzen.

Diese Gruppen kann man mit Hilfe der Balkenwaage miteinander vergleichen.

Nach dem ersten Wiegen weiß man dann, in welcher Gruppe sich die schwerere Münze befindet. Dann teilt man diese Gruppe wieder in zwei gleichgroße Gruppen usw. bis man am Ende nur noch zwei Münzen miteinander vergleichen muss.

Aber wie ist es mit einer ungeraden Anzahl von Münzen? Da bleibt dann bei der Bildung der Gruppen vor dem ersten Wiegen eine Münze übrig.

volkard

LinuxC_newbie schrieb:

Solange mindestens zwei Münzen vorhanden sind
     Nimm' zwei Münzen und vergleiche deren Gewicht mit der Balkenwaage
...

Oder nimm vier Münzen und lege zwei in die linke und zwei in die rechte Schalde.
Oder 6 Münzen. Oder 8 Münzen.
Jeden diese Algos solltest Du durchspielen und dann den besten nehmen.

SeppJ

Dobi schrieb:

Nur wenn es nicht mehr als 9 Münzen sind.

Klar. Aber alleine an dieser Vorgabe erkennt man doch schon, dass die Lösung gesucht ist, an die wir beide gerade denken. Wenn der Aufgabensteller fies gewesen wäre, dann hätte er 8 Münzen gesagt, damit der TE denkt, die Zahl wäre von Bedeutung und schnurrstracks auf den Holzweg läuft, dass der dreifache Primfaktor 2 hier von Bedeutung wäre.

Sei die Anzahl der Münzen gerade.

Dann bilde zwei Gruppen mit n/2 Münzen.

Anscheinend war die Zahl 8 gar nicht nötig, damit der TE diesen Weg läuft .

volkard

LinuxC_newbie schrieb:

Aber wie ist es mit einer ungeraden Anzahl von Münzen? Da bleibt dann bei der Bildung der Gruppen vor dem ersten Wiegen eine Münze übrig.

Macht gar nix!!!
Die Waage hat nämlich drei Anzeigen, LINKS, RECHTS und GLEICH.
Bei LINKS ist die falsche Münze in der linken Waggschale. bei RECHTS in der rechten. Und bei GLEICH ist sie in der Restgruppe der noch nicht angefaßten Münzen.

LinuxC_newbie

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 insgesamt

Mö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 insgesamt

Antwort zu Frage b): 2 Mal wiegen

-----
Falls dies nun so besser ist, weiß ich aber nicht, wie ich dieses Vorgehen verallgemeinern kann.

SeppJ

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.

LinuxC_newbie

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?

volkard

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 log₂(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.

SeppJ

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?

LinuxC_newbie

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?

volkard

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.

volkard

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?

LinuxC_newbie

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

volkard

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.

LinuxC_newbie

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?

volkard

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?

LinuxC_newbie

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?

volkard

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.

LinuxC_newbie

Dafür ist ja aber auch der best-case deutlich schlechter - oder zählt das nicht?

volkard

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.