Hi!
Hab mal wieder eine super Frage
Ich suche einen Algorithmus oder ähnliches zur Lösung folgenden Problems:
Ich habe eine Urne mit n Kugeln, von denen k verschieden sind.
Ich kenne n, k aber nicht (z.B. Urne wiegen und auf Anzahl schließen).
Wie oft muss ich mindestens Kugeln ziehen, um sagen zu können, welche am Meisten vorkommen?
Dabei:
• wenn die Anzahl n/2 ist, ist das Maximum erreicht (5/10 ist Maximum, auch wenn ein zweites auch 5/10 haben kann).
• wenn eines als erstes das Maximum erreicht, gilt das.
• wenn n=k => die 1. Kugel gibt es am Meisten (notfalls letzt/irgendeine)
Beispiel (wird nicht so toll angezeigt, vielleicht in Editor kopieren, falls es irgendwen interessiert

)
z.B. n=10, k=1:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
x x x x x| => 5 Untersuchungen (k ist vorher nicht bekannt)
z.B. n=10, k=2:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
y x x x x x| => min 6 Untersuchungen (n/2 erreicht)
y y y y x x x x x| => max 9 Untersuchungen
und so weiter....
MfG
Matt
PS:
z.B. n=10, k=3:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
z y x x x x x| => min 7 Untersuchungen
z y x z y x z y x x| => max 10 Untersuchungen
z.B. n=10, k=4:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
q z y x x x x| => min 7 Untersuchungen (jedes muss min. 1x vorkommen; wenn z.B. 8=9=10=q hätte es auch 4, aber zu spät)
q z y x q z y x x| => max 9 Untersuchungen (käme z.B. q, dann hätte es als erste die Meisten, auch wenn x genausoviel haben könnte)
z.B. n=10, k=5:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
r q z y x x x x| => min 8 Untersuchungen
r q z y x r q z y x| => max 10 Untersuchungen (r gewinnt, weil alle gleich viel haben)
z.B. n=10, k=6:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
s r q z y x x x| => min 8 Untersuchungen
s r q z y x s r q x| => max 10 Untersuchungen (s gewinnt, weil alle gleich viel haben)
z.B. n=10, k=7:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
t s r q z y x x x| => min 9 Untersuchungen
t s r q z y x t s x| => max 10 Untersuchungen (t gewinnt, weil alle gleich viel haben)
z.B. n=10, k=8:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
u t s r q z y x x| => min 9 Untersuchungen
u t s r q z y x u x| => max 10 Untersuchungen (u gewinnt, weil alle gleich viel haben)
z.B. n=10, k=9:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
v u t s r q z y x x| => min 10 Untersuchungen
z.B. n=10, k=10:
1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------
p v u t s r q z y x| => min 10 Untersuchungen (p gewinnt)
Moderiert von
jasocul: überflüssige Leerzeilen entfernt