Risk

door **drc.** » zo 20 okt 2013, 22:59

Hier is een afbeelding om het weer te geven. We gaan van het rode vierkant naar het groene, over de zwarte wegen, en we kunnen alleen naar rechts of omhoog.

Bijvoorbeeld we kunnen vier keer omhoog en dan vier keer naar rechts. Stel, we kunnen m keer naar rechts en n
keer omhoog. Toegepast op dit probleem stellen we dat de dobbelsteen m + 1 waarden kan nemen, van 0 tot en met m (geheel) en dat we n zulke dobbelstenen hebben.
Dan zijn er (m+1+n)!/(n! * (m+1)!) mogelijke wegen. Hier, m = n = 4 zodat we op 70 mogelijke manieren kunnen gaan.

Als we omhoog gaan wil dat zeggen dat het volgende getal dat we plaatsen met 1 wordt verhoogd. Als we naar rechts gaan, gooien we het getal dat die op de verticale as geeft. Stel O is omhoog en R is naar rechts. Dan

OORROORR geeft als worp 2244, twee keer omhoog zodat het volgende te plaatsen getal 2 is. RR. Plaats het twee keer. OO. Weer twee omhoog. Dan is het volgende getal dat we plaatsen
RROORROO geeft dan 0022.

Toegepast op de afbeelding, als we eerst naar rechts gaan dan hebben we als eerste getal een 0 en kunnen we nog 3 keer naar rechts en 4 keer omhoog. Dat kan op 35 manieren. Dus 35 worpen met oplopende dobbels beginnen met een 0.
Een andere mogelijkheid is dat we omhoog als eerst omhoog gaan. Dan is het eerste cijfer minstens 1. Vergelijkbaar met eerst, zijn er dan 35 zulke worpen met eerste getal minstens 1. Zo kan je doorwerken.

Dat met een verhogen kan je nog op een andere manier doen.

Bepaal het aantal zessen waar de worp op eindigt.
1166 eindigt op 2 zessen, 1155 op 0 zessen.
Noem dat aantal z.
Tel 1 + 3 * (10^z - 1) / 9 erbij op. factor 3 want 9 - aantal zijdes = 9 - 6 = 3.
In het geval van 1166 tel je dan 34 op, geeft 1200
Bij 1155 tel je dan 0 op. Blijft 1155.
\ is integer division; n \ m = floor(n/m)
Tel dan nog (10^z - 1) / 9 * ((n \ 10^z) mod 10) op. Voor 1200 geeft dat 11 * ((1200 \ 10) mod 10) = 22 op.
Geeft 1222 als volgende getal voor 1166. Het volgende getal voor 6666 is dan 10000. Dat kan je als stopregel gebruiken, of het aantal keer dat je de volgende hebt bepaald.

Komende midweek ben ik op pad, ik weet niet hoe vaak ik dan nog online ben.

door **Dux** » zo 20 okt 2013, 18:24

Ik kan het volgen, maar kun je misschien uitleggen waarom dit werkt? Ik heb namelijk geen idee waar de driehoek van Pascal wegkomt. Ik zie de connectie tussen de methode en het probleem niet.

Zelf zou ik (net als laatste keer) het laatste cijfer steeds één verhogen, wanneer er zevens ontstaan verhoog je het getal ervoor met één, maar nu maak je daarna alle volgende getallen aan dat getal. Visualisatie:

1111
1112
...
1116
1122
1123
...
1166
1222
...

door **drc.** » za 19 okt 2013, 18:03

Ja, 30 klopt.
Ik heb een truc, methode, maar ik weet niet of die beter is dan recursief die worpen te bepalen. Ik heb nog geen goede recursieve methode. Jij? Hoe zou je het programmeren?

Hier is de methode:
In feite construeer je een getallenstelsel.

3 dobbelstenen, d = 3, dus 3 rijen.
4 zijvlakken, s = 4, dus 4 kolommen.

\({s + d - 1\choose d} = 20 mogelijke worpen.\)

Begin bij 0, een dobbelsteen heeft de zijden 0, 1, 2, 3.

Mogelijke worpen:

Code: Selecteer alles

Hier is een deel van de driehoek van Pascal, gedraaid.

Code: Selecteer alles

   1    1    1    1
   4    3    2    1
  10    6    3    1

Wat je wilt is een manier om bijv. de 11e worp te vinden (geteld vanaf 0) is dat 112
Om al die rijen te vinden kan je het volgende doen:
Een voorbeeld: m = 11. Dan bepalen we de worp.
Het cijfer c = 0. w is de worp, die construeren we en die is nu leeg.
Begin linksonder, bij het getal 10.
10 <= 11 dus verhoog het cijfer c met 1 en
verlaag het getal m met 10, geeft m = 11 - 10 = 1.
Ga een plaats naar rechts, naar cijfer 6.
6 > 1 dus ga naar het cijfer erboven, 3. zet aan w, het (nieuwe) cijfer c = 1. Geeft w = 1
3 > 1 dus ga naar het cijfer erboven, 1. zet aan w, het cijfer c = 1. Geeft w = 11
1 <= 1 dus verhoog het cijfer c met 1. Geeft c = 2.
We zijn nu bovenaan het deel van de driehoek van Pascal, dus plak het cijfer 2 rechts van w. Geeft w = 112.
We gooien 3 dobbelstenen, verleng w totdat die lengte 3 heeft door telkens het cijfer c aan te plakken. De worp w heeft al 3 cijfers dus we hoeven er niets aan te plakken.

Vervolgens wil je nog worp 112 geeft som = 1 + 1 + 2 = 4.
De dobbelsteen gaat van 1 tot en met 4 in plaats van 0 tot en met 3 dus tel voor elke dobbelsteen 1 op.
4 + 3 * 1 = 7. 3 manieren (3 permutaties van 1, 1, 2) om zo 7 te gooien. Dus het aantal manieren om 7 te gooien wordt met 3 verhoogd.

Snap je?

door **Dux** » za 19 okt 2013, 17:49

5!/(2!*2!)=30

Nu aan het programmeren (alleen oplopende getallen, daarna aantal dezelfden tellen) of heb je nog handige truuks?

door **drc.** » za 19 okt 2013, 16:45

Juist. Op hoeveel manieren kan je nu de getallen 12233 rangschikken?

door **Dux** » za 19 okt 2013, 16:31

David schreef:Je wilt n! delen door het product van die 'gefaculteerde' getallen. Kan je dat verklaren?

Natuurlijk, foutje. Het is het product omdat er zoveel mogelijkheden zijn het ene getal te rangschikken én zoveel mogelijkheden het andere getal te rangschikken.

door **drc.** » za 19 okt 2013, 14:40

Als het ging om 22333 was 5! / (2! * 3!) = 10 het aantal permutaties van 22333.

Dux schreef:n! te delen door de som van die 'gefaculteerde' getallen

Je wilt n! delen door het product van die 'gefaculteerde' getallen. Kan je dat verklaren?

door **drc.** » za 19 okt 2013, 13:29

Om alle permutaties van 12233 te vinden, wil je weten hoeveel verschillende objecten (hier, getallen) er voorkomen. In dit geval drie verschillende getallen, 1, 2 en 3. Dan wil je van elk getal weten hoevaak die voorkomt. 1 komt een keer voor, 2 en 3 allebei twee keer. 5!/(2!+3!) = 10 is te laag, voor zowel 12233 als 1223.

door **Dux** » za 19 okt 2013, 12:38

Als ik me niet vergis is dit een combinatie met herhalingen. Ik snapte het door deze site: http://www.mathsisfun.com/combinatorics ... tions.html

Voor het aantal permutaties per worp ben ik van plan het aantal dezelfde getallen per worp te vinden (bij 12233 bijvoorbeeld 2 en 2) en dan n! te delen door de som van die 'gefaculteerde' getallen (dus bij 1223 5!/(2!+3!) ).

door **drc.** » do 17 okt 2013, 21:25

Met inspectie vooral, stel d = aantal dobbelstenen, s = aantal vlakken, dan aantal mogelijkheden is

\({s + d - 1\choose d}\)

. Ik heb nog geen bewijs, misschien kan dat met inductie. In feite construeer je een getallenstelsel.

3 dobbelstenen, d = 3, dus 3 rijen.
4 zijvlakken, s = 4, dus 4 kolommen.

\({s + d - 1\choose d} = 20\)

mogelijke worpen.

Snap je?

door **Dux** » do 17 okt 2013, 19:34

Lijkt me goed, maar hoe kom je op die berekening van 126?

door **drc.** » wo 16 okt 2013, 10:38

Ah dus wat je doet is dat, stel voor vier dobbelstenen je dat wilt bepalen, dan controleer je alle 6^4 mogelijke worpen; 1111, 1112, 1113,...,1311,..., 6664, 6665, 6666.
Of zie je 1113 en 1311 als dezelfde worpen? Het lijkt zo omdat in de lijst met worpen, de aantallen telkens worden verhoogd met 1.

Het kan ook door 1113 als een worp te tellen en alleen de worpen te tellen waarin de dobbelstenen in oplopende volgorde staan. Dan krijg je als mogelijke worpen
1111, 1112, 1113, ..., 5555, 5556, 5566, 5666, 6666 en {6 + 4 - 1 \choose 4} = 126 iets langere inspecties (je moet het aantal permutaties vinden van elke worp) in plaats van 6^4 = 1296 inspecties. Hoe lijkt je zoiets?

door **Dux** » ma 14 okt 2013, 17:10

David schreef:Ik heb een idee van wat de code doet, maar een aantal commando's, try, except, snap ik niet zo.

Ik zal de code dan nog even toelichten:
for n in range(1,d+1): ga voor n alle getallen langs van 1 tot en met d. (hij stopt bij d+1)

Qn=[0] * (6*n+1): Maak een lijst genaamd Qn, met 6*n+1 nullen. De [] worden gebruikt om lijsten te maken, of hun index aan te geven. f[0] is het eerste object in f.

De dobbelstenen (ds) gaat hij systematisch bij langs. Eerst maakt hij de waarde van de laatste dobbelsteen 1 hoger. Dan probeert (try) hij te zoeken naar een zeven; als hij die niet vind (except) dan maakt hij i -1 en houdt bij het if-statement op. Anders is i de index van de zeven en dan wordt de zeven een 1 en het getal ervoor wordt een verhoogd.

Verder staat len([lijst]) voor de lengte van een lijst en sum([lijst]) voor de som van de waarden. 'append()' voegt een waarde toe aan het einde.

Ik kan jouw code zo ongeveer volgen, maar moet nog maar even naar de formules kijken...

Bedankt voor je hulp en aanwijzingen!

door **drc.** » zo 13 okt 2013, 20:37

Ok, dat heb je snel gedaan!

Ik heb deze formules gebruikt:

Gegeven n dobbelstenen. Dan de kans dat je minder dan s ogen gooit is

\(P(Qa < s) = P(Qa + 1 \le s) = \sum_{i=0}^{\lfloor \frac{s-1}{6} \rfloor} {n \choose i} \cdot {s - 6 * i \choose n} \cdot (-1)^i\)

De kans dat je precies s ogen gooit is

\(p(Qa = s) = \sum_{i=0}^{\lfloor \frac{s-1}{6} \rfloor} {n \choose i} \cdot {s - 6 * i - 1 \choose n - 1} \cdot (-1)^i\)

Hier is mijn code, voor Excel VBA

bepaal voor a = 1 t/m 6 en b = 1 t/m 6 de kansen

Code: Selecteer alles

Sub result()
Dim a As Long, b As Long
For a = 1 To 6
    For b = 1 To 6
        dux a, b
    Next
Next
End Sub

bereken het aantal mogelijkheden om met a dobbelstenen meer ogen te gooien dan met b dobbelstenen.

Code: Selecteer alles

Public Function dux(a As Long, b As Long)
Dim i As Long, s As Long
For i = min(a, b) To 6 * max(a, b)
    s = s + diceeq(a, i) * diceless(b, i - 1)
    'Debug.Print i, s, diceeq(a, i), diceless(b, i - 1)
Next
'print a, b, de exacte vorm en de benaderde vorm van de kans
Debug.Print a, b, s & "/6^" & (a + b) & " = " & s / 6 ^ (a + b)
End Function

aantal mogelijkheden om met n dobbelstenen een aantal ogen te gooien <= s.

Code: Selecteer alles

Function diceless(n As Long, s As Long) As Long
Dim i As Long
For i = 0 To (s - 1) \ 6
    diceless = diceless + binomial(n, i) * binomial(s - 6 * i, n) * (-1) ^ i
Next
End Function

aantal mogelijkheden om met n dobbelstenen een aantal ogen te gooien gelijk aan s.

Code: Selecteer alles

Function diceeq(n As Long, s As Long) As Long
Dim i As Long
For i = 0 To (s - 1) \ 6
    diceeq = diceeq + binomial(n, i) * binomial(s - 6 * i - 1, n - 1) * (-1) ^ i
Next
End Function

bereken (n choose k)

Code: Selecteer alles

Function binomial(n As Long, k As Long) As Long
If k = 0 Then
    binomial = 1
Else
    binomial = n / k * binomial(n - 1, k - 1)
End If
End Function

functies voor minimum en maximum van a en b.

Code: Selecteer alles

Public Function min(a As Long, b As Long) As Long
If a < b Then min = a Else min = b
End Function
Public Function max(a As Long, b As Long) As Long
If a > b Then max = a Else max = b
End Function

Maar goed dat je het zelf hebt geleerd

Ik heb wat C gehad maar vooral VBA. Ik heb een idee van wat de code doet, maar een aantal commando's, try, except, snap ik niet zo.

door **Dux** » zo 13 okt 2013, 19:27

Mijn uitkomsten zijn dezelfde:

Code: Selecteer alles

a  b  p(Sa>Sb)
----------------------------
1  1  0.4166666666666667
1  2  0.09259259259259259
1  3  0.011574074074074073
1  4  0.0007716049382716048
1  5  2.1433470507544583e-05
1  6  0.0
2  1  0.837962962962963
2  2  0.4436728395061728
2  3  0.15200617283950615
2  4  0.03587962962962963
2  5  0.006104966849565615
2  6  0.0007662465706447187
3  1  0.9729938271604938
3  2  0.7785493827160493
3  3  0.4535751028806584
3  4  0.19170096021947874
3  5  0.060712686709343086
3  6  0.014878599235380787
4  1  0.9972993827160495
4  2  0.9392361111111109
4  3  0.7428305041152261
4  4  0.45952824931412894
4  5  0.22044235110882487
4  6  0.08342283791850835
5  1  0.9998499657064469
5  2  0.9879401005944214
5  3  0.90934713648834
5  4  0.7180784179240969
5  5  0.46365359701265046
5  6  0.24244910079975954
6  1  0.9999964277549153
6  2  0.9982168543286084
6  3  0.9752998105916272
6  4  0.8839534684647495
6  5  0.6996163882873404
6  6  0.46673060195210997

Mijn programma bestaat uit twee delen.
Dit deel maakt voor alle aantallen dobbelstenen tot en met d een lijst met frequenties (= mogelijkheden) voor een aantal ogen:

Code: Selecteer alles

def frequenties(d):
    f=[0]
    for n in range(1,d+1):
        Qn=[0] * (6*n+1)
        ds=[1] * n
        while sum(ds) < 6*n:
            Qn[sum(ds)] += 1
            ds[-1]+=1
            while 1:
                try:
                    i=ds.index(7)
                except ValueError:
                    i=-1
                if i==-1:
                    break
                else:
                    ds[i]=1
                    ds[i-1]+=1
        Qn[sum(ds)]+=1
        f.append(Qn)
    return f

Het volgende deel gaat alle a's en b's door en dan alle mogelijkheden van a (dan voert hij eigenlijk die som uit die ik eerder postte), hij telt de kansen op en laat ze op beeld zien:

Code: Selecteer alles

for a in range(1,d+1):
    for b in range(1,d+1):
        p=0
        for i in range(0,len(f[a])):
            winst=0
            for j in range(0,i):
                if j+1>len(f[b]):
                    break
                winst+=f[b][j]
            winkans=winst/sum(f[b])
            p+=f[a][i]/sum(f[a])*winkans
        print(a,b,p)

Ik zag aan jouw post dat het meervouden zijn van 1/(6^(a+b)), wat eigenlijk wel logisch is.

David schreef:Hoezo geef je de formule op?

Omdat de formule waarschijnlijk uiteindelijk hetzelfde zou doen als het programma en omdat het programma een exact antwoord kan geven ,die meervouden van 1/(6^(a+b)), is hij ook niet nodig voor een exact antwoord.

PS: Ik sta open voor opmerkingen op mijn programmeren

, ik heb het mezelf aangeleerd.

Risk

Plaats een reactie

Weergave uitklappen Voorafgaande berichten: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Re: Risk

Contact

Community