Denkaufgabe zu Algorithmus: Balkenwaage und n Kugeln, eine ist schwerer

Question

Hey folgendes Problem:

Sie haben eine Balkenwaage und n Kugeln, die alle gleich aussehen. Alle bis auf eine wiegen exakt gleich viel, eine ist schwerer. Geben Sie einen Algorithmus an, der mit möglichst wenigen Wägungen bestimmt, welche Kugel die Schwerere ist.

Kenne nur das mit den 12 Kugeln :D Aber das würde mich jetzt mal interessieren. Hat wer einen Ansatz?

Answer 1

Man teilt die Menge in 3 Haufen. Läst es sich nicht genau teilen kommt der Rest in den dritten Haufen. Dann wiegt man den ersten und zweiten Haufen. Danach ist entweder die schwerere Kugel im ersten oder zweiten Haufen. Dann sehen wir wo oder im Dritten Haufen.
Nun verfährt man Rekursiv mit dem Haufen indem die schwerere Kugel vorhanden war.

Comments

Genau so hab ich das auch mit den 12 Kugeln gemacht

aber hier sind ja n Kugeln.. geht man davon aus das es eine gerade Zahl ist?

Weil wenns zb 13 Kugeln wären würden am ende ja nicht wie bei 12 Kugeln nur 2 übrig bleiben. Es wär doch ungerade oder nicht?

---

Also meine Frag ist ob es mehrere Wägungen gibt bei einer ungeraden Zahl

---

Das ist egal.
13 = 4 + 4 + 5

Im zweifel ist die schwere Kugel bei den 5 Kugeln.

5 = 1 + 1 + 3

Im Zweifel ist die Kugel jetzt bei den letzten dreien.

3 = 1 + 1 + 1

Spätestens jetzt weiß man die schwere Kugel.

Answer 2

Grobe Beschreibung der Idee:

A) Teile die n Kugeln in 3  Gruppen A, B und C auf, die möglichst die gleiche Anzahl Kugeln enthalten. 

Falls n durch 3 teilbar ist entstehen drei Gruppen mit jeweils n / 3 Kugeln

Falls 1 Kugel übrig bleibt, lege diese in die Gruppe A => Gruppe B und C sind gleich groß.

Falls zwei Kugeln übrig bleiben, lege jeweils eine von diesen in die Gruppe A und die andere in die Gruppe B => A und B sind gleich groß.

In jedem Fall hat man mindestens zwei gleich große Gruppen.

 

B) Nimm nun zwei dieser gleich großen Gruppen und wiege sie gegeneinander.

Falls beide Gruppen gleich schwer sind, muss die schwerere Kugel in der dritten Gruppe sein, andernfalls ist sie in der schwereren Gruppe,

Gehe nun mit der so identifizierten Gruppe zu Schritt A)

 

Auf diese Weise verringert sich die Anzahl der zu testenden Kugeln mit jedem Durchlauf auf etwa ein Drittel der Anzahl des vorherigen Durchlaufs.

Nach etwa log₃ ( n ) Durchläufen hat man die schwerere Kugel gefunden. Einen schnelleren Weg gibt es nicht.

 

Etwas schwieriger wird es, wenn nur bekannt ist, dass eine Kugel eine andere Masse hat, als die anderen Kugeln, nicht aber, ob sie schwerer oder leichter als diese ist.