20 svar
170 visningar
dajamanté Ă€r nöjd med hjĂ€lpen!
dajamanté 5246
Postad: 26 jan 2019

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?

Laguna 5108
Postad: 26 jan 2019

Hur menar du "med sannolikhet"? Genom att slĂ„ tĂ€rningarna en miljard gĂ„nger och kolla vad som blir vanligast? 

dajamanté 5246
Postad: 27 jan 2019

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?

Laguna 5108
Postad: 27 jan 2019 Redigerad: 27 jan 2019
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.

dajamanté 5246
Postad: 27 jan 2019

Med min ökÀnda teknik av den blöta öga, tomma hjÀrna kan jag gissa att det kommer att likna en normalfördelning?

Laguna 5108
Postad: 27 jan 2019
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.

dajamanté 5246
Postad: 27 jan 2019

Men hur skulle du lösa, matematisk?

Laguna 5108
Postad: 27 jan 2019

Om tÀrningarna har 8 respektive 15 sidor, sÄ blir tabellen sÄ hÀr:

 234567893456789104567891011567891011126789101112137891011121314891011121314159101112131415161011121314151617111213141516171812131415161718191314151617181920141516171819202115161718192021221617181920212223

Har du en hypotes om hur man tÀnker sen?

dajamanté 5246
Postad: 27 jan 2019

Det verkar som... alla tal efter 8:an upprepas 8 gÄnger (?)

Laguna 5108
Postad: 27 jan 2019
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.

dajamanté 5246
Postad: 28 jan 2019
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Ä?

Laguna 5108
Postad: 28 jan 2019

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Ă„? 

dajamanté 5246
Postad: 28 jan 2019

LÄt oss sÀga m-n dÄ?

Men hur kan jag isolera vilka tal repeteras 8 gÄnger (i den hÀr exempel)?

Laguna 5108
Postad: 28 jan 2019
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.

dajamanté 5246
Postad: 28 jan 2019

n-m + 1?... Jag verkligen ser inte.

Laguna 5108
Postad: 28 jan 2019

m, helt enkelt.

dajamanté 5246
Postad: 30 jan 2019

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?

joculator 1562 – Moderator
Postad: 30 jan 2019

Alla tal frĂ„n och med m+1 till och med n+1

dajamanté 5246
Postad: 30 jan 2019 Redigerad: 30 jan 2019

Nu som du sÀger det... det verkar rimligt.

Jag ska testa uppdaterade koden.

 

EDIT: vad om m = n?

joculator 1562 – Moderator
Postad: 31 jan 2019
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

(1)(2)(3)(1)234(2)345(3)456

 

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.

dajamanté 5246
Postad: 31 jan 2019

Nu mÄste jag faktiskt tacka er mycket varmt!

 

Koden innan PA intervention:

 

koden efter PA intervention:

 

Svara Avbryt
Close