Autor Beitrag
Matg40
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 52



BeitragVerfasst: Fr 02.06.06 11:53 
Hi!
Hab mal wieder eine super Frage :lol:
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 :D )

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 user profile iconjasocul: überflüssige Leerzeilen entfernt
uall@ogc
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: Fr 02.06.06 12:34 
Also so wie ich es verstanden habe:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
var kugeln: array[0..n] of Boolean;
a, b, i: DWord;
begin
  a := 0;
  b := 0;
  i := Low(kugeln);
  while (a < Length(kugeln) div 2) and (b < Length(Kugeln) div 2) do
  begin
    if kugeln[i] then
      inc(a) else
      inc(b);
    inc(i);
    if (i > High(kugeln)) then
      Break;
  end;
  if a > b then
    MessageBoxA(0,'Mehr Kugeln von Gruppe a',nil,0) else
  if b > a then
    MessageBoxA(0,'Mehr Kugeln von Gruppe b',nil,0) else
    MessageBoxA(0,'Gruppe a hat genau so viele Kugeln wie Gruppe b',nil,0);
end;


Ach ist Schwachsinn :P Hab ma wieder net genau gelesen ^^

_________________
wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
digi_c
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1905

W98, XP
D7 PE, Lazarus, WinAVR
BeitragVerfasst: Fr 02.06.06 12:42 
Also du willst ermitteln wie oft man ziehen muss, um die exakte stochaistische Verteilung(Unterschiede Farbe, Form) zu ermitteln? Das wäre doch aber n :eyecrazy:

Magst du mal die Leerzeilen aus deinem Post raus nehmen?
Allesquarks
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 510

Win XP Prof
Delphi 7 E
BeitragVerfasst: Fr 02.06.06 12:46 
Dafür braucht man keinen Algorithmus sondern eine Variable. Wenn du n und k nicht kennst dann könnte man zu jedem Zeitpunkt argumentieren dass noch fast unendlich viele Kugeln in dem Topf sind da ich n ja nicht kenne, wenn ich aber noch beliebig viele ziehen könnte kann damit auch jede derzeitige Verteilung umgeworfen werden. Folglich kann darüber eine Aussage erst getroffen werden, wenn n bekannt ist und das ist dann wohl erst wenn keine Kugel mehr im Topf ist. Die Antwort ist also n.
uall@ogc
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: Fr 02.06.06 12:48 
Also mein Ansatz ist für den Algorithmus schon nicht schlecht. Bei der While-Schleife musst du eben für jedes k prüfen ob dieser größer ist als der 2. größte Wert + verbleibende Kugeln (n-i).
Fürs hochzählen brauchste dann eben ein weiteres Array. Zum ausgeben einfach dann eine Schleife die schaut welches die meiste Anzahl hat. Denn für k = 3 könnte ja auch eine Kugel gar nicht vorkommen, wenn doch muss halt in der obersten While Shcleife noch -k abgerechnet werden.

Brauchst du den Algorithmus in Delphi, oder eine Angabe für den best und worst-case? (Also nicht O-Notation, sondern Theta)

_________________
wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
uall@ogc
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: Fr 02.06.06 12:56 
user profile iconAllesquarks hat folgendes geschrieben:
Dafür braucht man keinen Algorithmus sondern eine Variable. Wenn du n und k nicht kennst dann könnte man zu jedem Zeitpunkt argumentieren dass noch fast unendlich viele Kugeln in dem Topf sind... Die Antwort ist also n.


Absolut richtig.

N und K unbekannt -> N, da aber N unbekannt -> keine Lösung des Problems auf rechnerischer Basis -> Einfach durchgehen

N unbekannt und K bekannt -> N, da N aber unbekannt -> keine Lösung des Problems auf rechnerischer Basis -> Einfach durchgehen

N bekannt und K unbekannt -> solange bis die Anzahl einer Kugel nicht mehr durch die Anzahl jeder anderen Kugeln eingeholt werden kann, weil der Rest der zu ziehen Kugeln kleiner ist -> Ende bei A > B[alleKugelnOhneA]+RestTopf
Min (k=1): N/2+1
Max (k=n): N


N bekannt und K bekannt -> siehe N bekannt und K unbekannt, zusätzlich sollte eine Kugel noch nicht gezogen sein, so muss ja mindestens eine Kugel von dieser noch im Topf sein -> Ende bei A > B[alleKugelnOhneA]+RestTopf-NochNichtGezogeneKugeln
Min (k=n): 0 (alle gleich oft)
Max (k=sqrt(n)): n

_________________
wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit


Zuletzt bearbeitet von uall@ogc am Fr 02.06.06 13:08, insgesamt 1-mal bearbeitet
Matg40 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 52



BeitragVerfasst: Fr 02.06.06 13:06 
Hi!


"N bekannt und K unbekannt -> solange bis die Anzahl einer Kugel nicht mehr durch die Anzahl jeder anderen Kugeln eingeholt werden kann, weil der Rest der zu ziehen Kugeln kleiner ist -> Ende bei A > B[alleKugelnOhneA]+RestTopf "

Das klingt sehr gut!


Ich hatte versucht eine Funktion (in C#) zu optimieren, die die das Element mit der größten Anzahl in einer Zeile findet.

Es wird sich aber ws. nicht viel optimieren lassen, außer, dass ich bei n/2 Elementen einer Sorte abbreche...



Also vielen Dank für die Mühen :!: :!: :!:


MfG

Matt
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Fr 02.06.06 13:08 
user profile iconMatg40 hat folgendes geschrieben:
Ich kenne n, k aber nicht (z.B. Urne wiegen und auf Anzahl schließen).

Diesen Satz verstehe ich so:
user profile iconMatg40 hat gemeint:
Ich kenne n, aber ich kenne k nicht. Z.B. kann man die Urne wiegen und so auf die Anzahl der Kugeln schließen.


Sei also N bekannt (sonst macht das auch keinen Sinn).

Sei max die Anzahl der Kugeln, die bisher am meisten gezogen wurden, max2 die Anzahl der Kugeln, die am zweithäufigsten gezogen wurden. (max2=0, wenn nur eine Farbe bisher auftrat). Du kannst mit dem Ziehen aufhören, wenn "max2 + restliche Kugeln < max". Das kann im WorstCase N sein, wenn N ungerade ist, und von jeder der (z.B.) zwei vorhandenen Farben immer abwechselnd eine gezogen wird.

_________________
We are, we were and will not be.