Sannolikhets/ kombinatorik(đ€ą đ€ź)problem
Hej!
Jag undrade om följande problem kunde lösas med sannolikhet:
https://open.kattis.com/problems/dicecup
Just nu har jag löst det klassisk, men jag undrar om det Àr en formel för att lösa det snabbare Àn med en HashMap?
Jag tĂ€nkte att först mĂ„ste man nog bestĂ€mma pĂ„ hur mĂ„nga sĂ€tt fĂ„r vi varje tal -tĂ€rningar lĂ€r vĂ€l olika (hatade kombinatorik đ!), och dĂ„ dela det med alla möjliga utfall. Men Ă€ven dĂ„, skulle vi inte behöva en HashMap eller en frequency array för att besvara frĂ„gan?
Vad tycker ni?
Hur menar du "med sannolikhet"? Genom att slÄ tÀrningarna en miljard gÄnger och kolla vad som blir vanligast?
Det lĂ„ter som en bra idé, om inte för lĂ„ngt!
Som sagt jag gjorde en samling av vÀrdarna, och valde ut den vanligaste
med 6 och 6 blir det
{2=1, 3=2, 4=3, 5=4, 6=5, 7=6, 8=5, 9=4, 10=3, 11=2, 12=1}
6 och 4 sidor blir det
{2=1, 3=2, 4=3, 5=4, 6=4, 7=4, 8=3, 9=2, 10=1}
Annars om det finns en formeln?
dajamanté skrev:Det lĂ„ter som en bra idé, om inte för lĂ„ngt!
Som sagt jag gjorde en samling av vÀrdarna, och valde ut den vanligaste
med 6 och 6 blir det
{2=1, 3=2, 4=3, 5=4, 6=5, 7=6, 8=5, 9=4, 10=3, 11=2, 12=1}
6 och 4 sidor blir det
{2=1, 3=2, 4=3, 5=4, 6=4, 7=4, 8=3, 9=2, 10=1}
Annars om det finns en formeln?
Nja, min idé Ă€r bara bra om man inte kan rĂ€kna ut det pĂ„ nĂ„got annat sĂ€tt. Din metod Ă€r bra, men Ă€nnu bĂ€ttre Ă€r att arbeta fram en formel matematiskt. Man ser redan ett mönster i dina tvĂ„ exempel. Om du skriver talen i en tabell (ena tĂ€rningen lodrĂ€tt och andra tĂ€rningen vĂ„grĂ€tt) och ser vilken summa som Ă€r vanligast sĂ„ ser du det kanske tydligare.
Med min ökÀnda teknik av den blöta öga, tomma hjÀrna kan jag gissa att det kommer att likna en normalfördelning?
dajamanté skrev:Med min ökĂ€nda teknik av den blöta öga, tomma hjĂ€rna kan jag gissa att det kommer att likna en normalfördelning?
Den gissningen Àr inte helt fel: om man har riktigt mÄnga tÀrningar sÄ nÀrmar sig den resulterande binomialfördelningen en normalfördelning. Men hÀr Àr det bara tvÄ tÀrningar, sÄ normalfördelning Àr fel.
Men hur skulle du lösa, matematisk?
Om tÀrningarna har 8 respektive 15 sidor, sÄ blir tabellen sÄ hÀr:
Har du en hypotes om hur man tÀnker sen?
Det verkar som... alla tal efter 8:an upprepas 8 gÄnger (?)
dajamanté skrev:Det verkar som... alla tal efter 8:an upprepas 8 gĂ„nger (?)
Inte alla, men vi ser att det största antalet sÀtt att fÄ en viss summa Àr 8, och att det Àr nÄgra som uppnÄr det antalet.
Laguna skrev:dajamanté skrev:Det verkar som... alla tal efter 8:an upprepas 8 gĂ„nger (?)
Inte alla, men vi ser att det största antalet sÀtt att fÄ en viss summa Àr 8, och att det Àr nÄgra som uppnÄr det antalet.
Jag men precis. Jag menade sÄ.
Jag har sovit (mycket dÄligt) pÄ det. Varför Àr det sÄ?
Om vi sÀger att antalet sidor Àr m och n, och m <= n, vilket Àr det största antalet sÀtt som nÄgon summa kan bildas pÄ?
LÄt oss sÀga m-n dÄ?
Men hur kan jag isolera vilka tal repeteras 8 gÄnger (i den hÀr exempel)?
dajamanté skrev:LĂ„t oss sĂ€ga m-n dĂ„?
Men hur kan jag isolera vilka tal repeteras 8 gÄnger (i den hÀr exempel)?
m-n kan inte vara rÀtt. DÄ skulle det bli noll för tvÄ likadana tÀrningar. Dessutom Àr det negativt i alla andra fall.
n-m + 1?... Jag verkligen ser inte.
m, helt enkelt.
Okej, tack för talamÄdet!
SÄ nu som vi du har listat ut att det var m, hur tar vi fram vilka tal Äterkommer m gÄnger?
Alla tal frÄn och med m+1 till och med n+1
Nu som du sÀger det... det verkar rimligt.
Jag ska testa uppdaterade koden.
EDIT: vad om m = n?
dajamanté skrev:Nu som du sĂ€ger det... det verkar rimligt.
Jag ska testa uppdaterade koden.
EDIT: vad om m = n?
Ja?
LÄt oss titta pÄ m=n=3
DÄ kommer alla tal frÄn och med m+1=4 till och med n+1=4 vara de tal som förekommer flest gÄnger.
Det vill sÀga 4
Ja, det stÀmmer ju. Talet 4 Àr det tal som förekommer flest gÄnger. Antal gÄnger Àr som talet förekommer Àr 3 och det stÀmmer ju med att Laguna skrev att det skulle vara m.
Allt under förutsÀttning att m<=n som Laguna skrev.
Nu mÄste jag faktiskt tacka er mycket varmt!
Koden innan PA intervention:
koden efter PA intervention:
