8 Bälle
Ich bin über ein spannendes Logik-Problem gestolpert. Die meisten Informatiker kommen aufgrund der angecodeten Denkweise auf die falsche Lösung 😉
Problem:
Du hast 8 gleichaussehende Bälle, von denen einer schwerer ist als die anderen sieben. Es gilt diesen Ball mit Hilfe einer alten Balkenwaage zu identifizieren. Wieviel Mal muss man mindestens wiegen, um den Ball zu erkennen?
Nur weiterlesen, wenn du eine Lösung gefunden hast!
Fast, aber nicht ganz
Die meisten werden sich für 3 Mal wiegen entschieden haben. Nach alter Informatikerweisheit liegt der O(log2 n)-Ansatz nahe, führt aber leider auf den Holzweg.
Beispiel:
1. [1,2,3,4] gegen [5,6,7,8]
2. [5,6] gegen [7,8]
3. [7] gegen [8]
Dann hat man den Ball sicher gefunden. „Devide and conquer“ funktioniert hier aber leider nicht effektiv genug.
Lösung
2 Mal wiegen genügt völlig.
Entweder:
[1,2,3] gegen [4,5,6] – 7 und 8 liegen lassen
» schwerere Schale nehmen
[4] gegen [5] – 6 liegen lassen
Bingo!
Oder:
[1,2,3] gegen [4,5,6] – 7 und 8 liegen lassen
» beide Schalen sind gleich schwer.
[7] gegen [8]
Bingo!
Und, wer hat es auf Anhieb erfasst?
Longneck
😀
…das isch computer-science… dört wo ich kei ahnig ha 😛
do e kompetenzmatrix für programmierer: http://www.indiangeek.net/wp-content/uploads/Programmer%20competency%20matrix.htm
rakudave
hehe
es git no e schwärers, aber do hani no kei stabile algo gfunde…
(12 bäll, eine isch schwärer _oder_ liichter, also vill meh möglichkeite)
Wi!!iam Wa!!ace
also ich bi au ehrlich ich has au mit de ershcte methode gmacht. es ligt villicht so in de IT-gen wer weiss 😀
N
Man sollte vielleicht fragen: Wie oft muss man >höchstens< wiegen 😉
Freidenker
jojo… has au nach dr erschte methode gmacht………. scheiss informatiker ^^