| Autor |
Beitrag |
Ralfi89
Hält's aus hier
Beiträge: 4
|
Verfasst: So 21.02.10 04:22
Hallo,
Ich bräuchte Hilfe bei der Simulierung eines Programms zur Berechnung von Wahrscheinlichkeiten. Ich habe leider kaum Kenntnisse aus der Informatik .
Folgende Situation :
Man hat 32 Karten von 1 - 32.
Man zieht eine Karte x . Die Karte ( Bsp . 9) wird nach rechts gelegt. Jetzt zieht man die nächste Karte( Bsp.7 ) und vergleicht diese mit der Karte auf dem rechten Stapel. Wenn die Karte kleiner ist, dann wird sie links auf einen Stapel gelegt,wenn sie größer ist,dann ersetzt sie die Karte auf dem rechten Stapel( also die 9). Man macht das solange weiter bis keine Karten mehr übrig sind . Extremfälle sind halt,dass meine keine karte weglegt ( wenn man jetzt eine 1 , dann eine 2 ,dann eine 3 ,dann eine 4 etc ziehen würde oder das man 31 Karten weglegt,wenn man direkt die 32 ziehen würde)
Die Frage ist jetzt, wie viel Karten man im Durchschnitt auf den linken Stapel legt.
Wäre nett,wenn mir jemand behilflich sein könnte.
Danke im Vorraus
Lg
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 21.02.10 04:29
Naja, was Dir helfen könnte, wäre in diesem Fall "Backtracking", d.h. dass Du alle Varianten einfach ausprobierst und das Ergebnis dann auszählst.
Da dies aber zu 32! Schritten führt, was doch recht große Zahlen nach sich führt, solltest du ggf. dir eher überlegen, dass Du sowas versuchst mathematisch herzuleiten?
Wie sieht dein jetziger Ansatz bisher aus?
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Ralfi89 
Hält's aus hier
Beiträge: 4
|
Verfasst: So 21.02.10 04:39
Ich dachte eigentlich,dass man ein Programm schreiben könnte, wo man mit einer FOR-Schleife immer die "gezogene" Karte mit der "bisher höchsten gezogegenen Karte" vergleicht und dann ausgibt wie oft die schleife durchgelaufen ist , bis der Stapel leer ist.
|
|
Xion
      

Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: So 21.02.10 10:33
Das ist eigentlich eher eine Mathe-Aufgabe...
naja, du kannst das auch so machen:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| procedure Check (x: integer); begin if x>max then max:=x else counter:=counter+1; end; |
Jetzt musst du nur noch 32 Karten zufällig ziehen (random). Ich würde jetzt auf Anhieb ein array [1..32] of boolean machen und dann die, die du schon gezogen hast, auf true setzen, damit du weißt, welche du noch ziehen darfst. For-Schleife rum (in der du auch das array immer wieder komplett auf false setzen musst) und fertig
_________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
|
|
Niko S.
      
Beiträge: 566
Erhaltene Danke: 10
Win 7, Ubuntu
Lazarus, Turbo Delphi, Delphu 7 PE
|
Verfasst: So 21.02.10 13:58
Ist das nicht eine Bernoulli aufgabe?
Wo man das Ereignis einfach "Wahr" oder "Falsch" setzen kann.
Also ob man nun eine Karte links packt oder nicht.
Also könnte man das mit der B(n;p;k) Formel lösen oder irre ich mich da?
|
|
Xion
      

Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: So 21.02.10 14:05
Hmm, Bernoulli ist schon zu lange her (2 Jahre) als das ich das noch könnte
Ich würde jetzt so ansetzen
Wenn die 32 gezogen wird -> 1 auf rechtem Stapel
Wenn die 31 gezogen wird -> zu 50% ist 32 schon weg, also 1,5 auf rechtem Stapel
...
zum Schluss käme dann wohl was logisches, aber falsches raus, wie es bei mir immer ist ^^
_________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
|
|
Niko S.
      
Beiträge: 566
Erhaltene Danke: 10
Win 7, Ubuntu
Lazarus, Turbo Delphi, Delphu 7 PE
|
Verfasst: So 21.02.10 14:09
Das hatte ich auch überlegt, logisch wäre eigentlich ein Durchschnitt von 50%
Sind wir eigentlich bei einem Einfachen Kartenspiel?
7,8,9,10,Bube,Dame,König,Ass ?
Oder sind die Karten von 1 bis 32 Nummeriert?
Edit
Wenn wir bei 1 bis 32 sind bei der Nummerierung, dann verändert sich die Chance immer wieder.
Wenn man beispielsweise gleich am anfang die 32 Zieht, so ist die Chance dass auch nur eine Karte auf dem linken Stapel liegt = 0;
Und wenn wir bei dem anderen Beispiel sind, was passiert dann wenn man 2 mal die gleiche Zahl hat?
Zuletzt bearbeitet von Niko S. am So 21.02.10 14:17, insgesamt 1-mal bearbeitet
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 21.02.10 14:11
Für das Mischen der Karten würde ich Fischer-Yates empfehlen. Der terminiert wenigstens garantiert in endlicher Zeit ... im Gegensatz zu anderen Random-Ansätzen 
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Ralfi89 
Hält's aus hier
Beiträge: 4
|
Verfasst: So 21.02.10 14:34
Niko S. hat folgendes geschrieben : | Das hatte ich auch überlegt, logisch wäre eigentlich ein Durchschnitt von 50%
Sind wir eigentlich bei einem Einfachen Kartenspiel?
7,8,9,10,Bube,Dame,König,Ass ?
Oder sind die Karten von 1 bis 32 Nummeriert?
Edit
Wenn wir bei 1 bis 32 sind bei der Nummerierung, dann verändert sich die Chance immer wieder.
Wenn man beispielsweise gleich am anfang die 32 Zieht, so ist die Chance dass auch nur eine Karte auf dem linken Stapel liegt = 0;
Und wenn wir bei dem anderen Beispiel sind, was passiert dann wenn man 2 mal die gleiche Zahl hat? |
Die Karten sind von 1-32 durch nummeriert,also wenn man die 32 zieht ,dann werden ja 31 karten nach links abgelegt und angenommen,man würde alle karten von 1-32 nach der reihenfolge ziehen ,dann würde keine karte nach links gelegt 
|
|
Niko S.
      
Beiträge: 566
Erhaltene Danke: 10
Win 7, Ubuntu
Lazarus, Turbo Delphi, Delphu 7 PE
|
Verfasst: So 21.02.10 14:59
Ja gut dann sind das aber wie BenBE schon sagte 32! Möglichkeiten.
Wobei man sofort abbrechen kann, wenn man die 32 gezogen hat, sodass alle möglichkeiten entfallen wenn man zuerst die 32 zieht.
Vielleicht sollte man einfach nur eine Nährung nehmen...
sprich also mit FischerYates meinetwegen 100.000 Verschiedene Wege generieren. und dann den durchschnitt ermitteln.
Damit das ganze noch mehr oder weniger fair bleibt, werden alle 1/32 mal die erste Zahl ne andere sein. sprich also alle 3125 mal wird die erste zahl geändert der rest gewürfelt.
Denke mal, damit sind näher am richtigen Durchschnitt als wenn wir von den 100.000 mal, 80.000 mal die 32 vorne haben ;D
Im endeffekt müsste man das komplett durchplanen, sodass man bei allen 100.000 versuchen das ganze möglichst gerecht aufgeteilt hat, wobei ich dann aber glaube dass es auf die 50% also durchschnittlich 16 Karten kommt.
|
|
Namenlosnameless
      
Beiträge: 259
Erhaltene Danke: 6
Windows XP Home Edition, Windos Vista
C#
|
Verfasst: So 21.02.10 17:00
Hallo!
Das ist jz vlt ein klein wenig off-topic, weil es nicht zur Lösungsfindung beiträgt!
Aber ich hab mir gerade so was geschrieben, allerdings in C# darum glaub ich bringt es nix den Code hier zu posten.
Ich bin mir nicht sicher ob das was ich gemacht habe stimmt, aber mir kommt 27,96 also 28 Karten im Durschschnitt raus.
Wenn das iwem auch rauskommt dann bitte per Pn an mich.
_________________ 1:<<Life sucks!!>> 2:<< Well okay>> 1: <<Just Yours>> 2:<<Ohmph>>
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 21.02.10 17:16
Namenlosnameless hat folgendes geschrieben : | Hallo!
Das ist jz vlt ein klein wenig off-topic, weil es nicht zur Lösungsfindung beiträgt!
Aber ich hab mir gerade so was geschrieben, allerdings in C# darum glaub ich bringt es nix den Code hier zu posten.
Ich bin mir nicht sicher ob das was ich gemacht habe stimmt, aber mir kommt 27,96 also 28 Karten im Durschschnitt raus.
Wenn das iwem auch rauskommt dann bitte per Pn an mich. |
Dieses Forum kann auch C#; und selbst wenn man die Sprache nicht kann, kann man sich trotzdem grob dran orientieren ...
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Niko S.
      
Beiträge: 566
Erhaltene Danke: 10
Win 7, Ubuntu
Lazarus, Turbo Delphi, Delphu 7 PE
|
Verfasst: So 21.02.10 17:44
Wenn du das mal gaaaanz Grob überschlägst:
1000 versuche.
im durchschnitt kannst du am anfang ca 31 mal die "32" ziehn womit du schonmal 32 mal 0 hast.
Das ist ja im endeffekt so festgelegt.
Wenn ich das jetzt logisch weiter führen würde, würde ich bei +- 16 karten im durchscnitt liegen.
Hast du dein Experiment mehrmals versucht?
Und ist immer sowas hohes rausgekommen?
|
|
bole
      
Beiträge: 107
Erhaltene Danke: 15
win 10
|
Verfasst: So 21.02.10 17:50
Ich habe das Fischer--Yates Demoprogramm von Narses etwas erweitert...
www.delphi-library.d...&highlight=yates
Danke für die Vorlage Narses
Ich komme auch auf 28 auf dem linken Stapel. egal wieviele Versuche!
_________________ ein programm macht nicht das was du willst sondern was du schreibst!
|
|
ub60
      
Beiträge: 765
Erhaltene Danke: 130
|
Verfasst: So 21.02.10 21:12
Also ich habe gerade 10 mal 10 Millionen Versuche durchlaufen lassen und ich komme nicht auf 28, sondern bleibe immer unter 27 (ca. 26,9725+-0,0008).
ub60
|
|
bole
      
Beiträge: 107
Erhaltene Danke: 15
win 10
|
Verfasst: So 21.02.10 21:45
Ich habs nochmals mit je 10'000'000 Versuchen getestet. Ich komme immer noch auf ca.28
Quelltext 1: 2: 3: 4: 5: 6:
| Left Right 27.9415706 4.0584294 27.9426821 4.0573179 27.9421349 4.0578651 27.9422340 4.0577660 27.9422853 4.0577147 |
Ich habe folgenden Code in die Demo www.delphi-library.d...&highlight=yates von Narses eingebaut:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28:
| procedure TForm1.Button1Click(Sender: TObject); Var Demo: TArray; i,j, maxlauf,AnzStLeft,AnzStRight,StRight :integer; begin Memo1.Lines.Add('Karten'); AnzStLeft:=0; AnzStRight:=0; maxlauf:=StrToint(edit1.text); SetLength(Demo,32); For j:=1 to maxlauf do Begin; StRight:=0; FillArray(Demo,1); ShuffleFisherYates(Demo); for i := Low(Demo) to High(Demo) do begin; If Demo[i]> StRight then begin; StRight:=Demo[i]; inc(AnzStRight); end else inc(AnzStLeft); end;
End; left.Caption:=floattostr(AnzStLeft/maxlauf); right.Caption:=floattostr((AnzStright/maxlauf)); |
Wie ist Dein Code?
Bole
_________________ ein programm macht nicht das was du willst sondern was du schreibst!
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: So 21.02.10 21:50
Hallo,
sind die 26,97 nicht sehr genau um 1 weg von den oben genannten 27,96 ?
Vielleicht zählen die anders
Interessante Sache das, bestimmt völlig sinnfrei.
Das heisst, dass man im Schnitt nur 4 mal die rechte oberste Karte ersetzt.
Wie kann man das denn berechnen und nicht raten.
Gruß Horst
EDIT:
Das reicht doch, Du kennst doch die Durchläufe und damit die Anzahl aller Karten.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| for i := Low(Demo) to High(Demo) do begin If Demo[i]> StRight then begin; StRight:=Demo[i]; IF Stright = 32 then break; inc(AnzStRight); end end; end;AnzStLeft := maxlauf*32 |
EDIT2:
Ich finde immer noch keinen Ansatz.
Aber vielleicht kann man dennoch abzaehlen indem alle Permutationen erzeugt.
lexikografische Permutation.
Quelltext 1: 2: 3: 4: 5: 6:
| 1,2,3,4,..30,31,32: links 0 rechts 32 0!-fach 1,2,3,4,..30,32,31: links 1 rechts 31 1!-fach 1,2,3,4,..32,30,31: links 2 rechts 30 2!-fach Permution der hinteren beiden ... 1,32,2,3, ..30,31: links 31 rechts 1 30!-fach Permution von 2..31 32,1,2,3, ..30,31: links 32 rechts 0 31!-fach Permution von 1..31 |
Na das lässt sich ja gut an 
Zuletzt bearbeitet von Horst_H am So 21.02.10 22:32, insgesamt 1-mal bearbeitet
|
|
bole
      
Beiträge: 107
Erhaltene Danke: 15
win 10
|
Verfasst: So 21.02.10 22:13
Die differenz von ziemlich genau 1 deutet schon auf ein Problem beim Zählen hin, wenn auch sinnfrei wäre es interessant den Code von ub60 zu sehen. Ich denke dem kommt man schon auf den Grund!
Wie man das berechnet weiss ich nicht, ich kanns nur simulieren denn ich bin kein Mathematiker
Wenn man nur einen Stapel zählt reicht das zwar und man gewinnt etwas performance, aber wenn man beide zählt hat man eine gewisse Kontrolle. Beide Stapel müssen addiert die Anzahl der Karten ergeben -> 32
Gruss
Bole
_________________ ein programm macht nicht das was du willst sondern was du schreibst!
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: So 21.02.10 22:38
Hallo,
Mein Edit2...
Aber vielleicht kann man dennoch abzaehlen, indem alle Permutationen erzeugt.
lexikografische Permutation.
Quelltext 1: 2: 3: 4: 5: 6:
| 1,2,3,4,..30,31,32: links 0 rechts 32 0!-fach 1,2,3,4,..30,32,31: links 1 rechts 31 1!-fach 1,2,3,4,..32,30,31: links 2 rechts 30 2!-fach Permutation der hinteren beiden ... 1,32,2,3, ..30,31: links 31 rechts 1 30!-fach Permution von 2..31 32,1,2,3, ..30,31: links 32 rechts 0 31!-fach Permution von 1..31 |
Na das lässt sich ja gut an
Die Gesamtsumme ist die Summe 31!+30!+29! ...
Aber dann müßte 31!/( Summe i= 1..31[i!]) = 1/32 sein.
Das ist was für Flamefire und BigNum
Gruß Horst
Edit alles Murks...
31!/( Summe i= 1..31[i!])
= 1/(1+1/31+1/(31*30)+..+1/31!+1/31!)
=1/[1+1/31*(1+1/30*(1+1/29*( ...1/2*(1+1/1*(1+1)....))]
EDIT2:
Die ganzen Permutationen vor der 32 fehlen, es müssen am Ende schliesslich 32! Permutationen sein...
Zuletzt bearbeitet von Horst_H am Mo 22.02.10 00:35, insgesamt 2-mal bearbeitet
|
|
Namenlosnameless
      
Beiträge: 259
Erhaltene Danke: 6
Windows XP Home Edition, Windos Vista
C#
|
Verfasst: So 21.02.10 22:46
Also wir haben in der Schule noch keine wahrscheinlichkeitsrechnungen gemacht... aber ich hab mir meine Gedanken dazu gemacht!
Gleich vorweg ich hab keine Ahnung von der Materie und ich weiß nicht ob mein Ansatz stimmt!
Meine Überlegungen:
1. Karte:
Wahrscheinlichkeit für die Karte x=1/32.
2.Karte: Die wahrscheinlichkeit dass die neue karte größer ist beträgt 1/(32-x) und die dass sie kleiner ist 1/x
3. Karte: blabla macht schon 4 Lösungen....... => schwere Berechnung.
Wenn man das macht und dann immer das vorherige x einsetzt könnte es klappen.
Ich hab hier noch den Quelltext von meinem Programm:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44:
| private void button1_Click(object sender, EventArgs e) { int counter=int.Parse(textBox1.Text); int highcard; int drwawncard; int gewaehlterindex; int counter2 = 0; int a=0, b=0;
for (int x = 0; x < counter; x++) { counter2 = 0; List<int> Karten =new List<int>{};
for(int x1=1;x1<=32;x1++) { Karten.Add(x1); } gewaehlterindex = rd.Next(1, Karten.Count + 1); highcard =Karten[gewaehlterindex-1]; Karten.Remove(highcard);
while (Karten.Count != 0) { gewaehlterindex = rd.Next(0, Karten.Count); drwawncard = Karten[gewaehlterindex]; Karten.RemoveAt(gewaehlterindex);
if (drwawncard < highcard) { counter2++; } else { highcard = drwawncard; } } a = a + counter2; Karten.Clear(); label2.Text = (((long)a / ((double)x)).ToString()); label2.Refresh(); } } |
Einloggen, um Attachments anzusehen!
_________________ 1:<<Life sucks!!>> 2:<< Well okay>> 1: <<Just Yours>> 2:<<Ohmph>>
|
|
|