Löysin tällaisen tehtävän Ohjelmointiputkan putkapostista Lottovoitto;
Lotossa oli ennen 39 numeroa, joista valittiin 7. Mikä on pienin määrä lottorivejä siten, että arvottiinpa mikä tahansa 7 numeron rivi, on kyseisellä rivillä ainakin 4 yhteistä numeroa jonkun kyseisen rivikokoelman rivin kanssa.
Olen miettinyt, miten tuollainen ohjelma kannattaisi tehdä. Toistaiseksi pystyn tekemään ohjelman, joka arpoo tietyn määrän rivejä. Mutta onko olemassa nopeaa tapaa tarkistaa rivien validius? Yritin tehdä ohjelman, joka tekee listan kaikista eri riveistä ja tarkistaa ne kaikkien rivien kanssa. Mutta noin 15000000 rivin tarkastaminen 400 rivin kanssa on hidasta. Lisäksi kaikkien rivien generoiminen vie aikaa ja muistia.
Onko siis tapaa tehdä funktio nextRow, joka palauttaisi annetusta lottorivistä seuraavan? Eli nextrow([1,2,3,4,5,6,7])=[1,2,3,4,5,6,8], nextrow([1,2,3,4,5,6,8])=[1,2,3,4,5,6,9] jne, vai miten kannattaisi iteroida kaikki rivit? Vai onko olemassa tapaa, jolla ei tarvitsisi tarkistaa kaikkia 15 miljoonaa riviä, eli joku suppeampi osajoukko riittäisi todistamaan, että nyt valittiin kunnollinen joukko rivejä?
Lottotehtävän algoritmi
13
1622
Vastaukset
- Anonyymi
Eikös oikea vastaus irtoa suoraan talukkolaskennan kaavalla:
=KOMBINAATIO(7;4)
eli 35 varitaatiota.- Anonyymi
Lisätäänpä vielä tapa jolla poimit nuo numerosarjat;
>>> python3
>>> from itertools import permutations
>>> perm = permutations([1, 2, 3, 4, 5, 6, 7], 4)
>>> for i in list(perm): print(i);
Eikös se näin mene? - Anonyymi
Anonyymi kirjoitti:
Lisätäänpä vielä tapa jolla poimit nuo numerosarjat;
>>> python3
>>> from itertools import permutations
>>> perm = permutations([1, 2, 3, 4, 5, 6, 7], 4)
>>> for i in list(perm): print(i);
Eikös se näin mene?Ehkä tuossa jäi epäselvyyttä lisäävä vaikutelma, kun laitoin oikeaa riviä kuvaamaan numerot 1..7, voit käyttää mitä tahansa muita lukuja noiden tilalla.
- Anonyymi
Minusta tuntuu, että yrität ratkaista tuota tarpeettoman monimutkaisesti, mutta kyllä sen varmasti noinkin saa oikein. Kannattaa kuitenkin huomata, että NextRow-funktiota ei kannata tehdä käymään rivejä läpi tuossa järjestyksessä, koska se on paljon työläämpää kuin "normaalissa" suuruusjärjestyksessä läpikäyminen.
Ensimmäinen rivi on siis 1, 2, 3, 4, 5, 6, 7 ja
toinen rivi on 1, 2, 3, 4, 5, 6, 8, kuten sinullakin, mutta
kolmas rivi on 1, 2, 3, 4, 5, 6, 9, ja
neljäs 1, 2, 3, 4, 5, 6, 10,
ja niin edelleen, kunnes viimeinen luku on käyty läpi kaikilla vaihtoehdoilla:
1, 2, 3, 4, 5, 6, 39.
Sitten toiseksi viimeistä numeroa kasvatetaan yhdellä, ja taas käydään viimeinen numero läpi kaikilla vaihtoehdoilla:
1, 2, 3, 4, 5, 7, 8
1, 2, 3, 4, 5, 7, 9
1, 2, 3, 4, 5, 7, 10,
...
1, 2, 3, 4, 5, 7, 39.
Ja taas kasvatetaan seuraavaa lukua yhdellä:
1, 2, 3, 4, 5, 8, 9.
1, 2, 3, 4, 5, 8, 10
1, 2, 3, 4, 5, 8, 11
...
1, 2, 3, 4, 5, 8, 39
Ja taas kasvatetaan seuraavaa lukua yhdellä:
1, 2, 3, 4, 5, 9, 10
1, 2, 3, 4, 5, 9, 11
1, 2, 3, 4, 5, 9, 12.
...
Ja niin edelleen.
Kun käytät tuota järjestystä, niin NextRow-funktio on paljon helpompi keksiä. Hauska tehtävä. Päivitän sitä sen verran, että otan numeron 40 mukaan, kuten lotossa tehtiin kierroksella 48/2016. Erilaisia rivejä on siis 18643560 kappaletta, kuten Veikkauksen sivuilla (peliohjeet / todennäköisyys) kerrotaan.
Pienin määrä lottorivejä, à 7 numeroa, että ainakin 4 oikein -tulos (jäljempänä "voitto") osuisi niihin on teoriassa 93. Käytännössä tällaista rivikokoelmaa ei pysty valitsemaan, koska osa mahdollisesti arvottavista riveistä tuottaisi väistämättä useamman voiton. Tämä päällekkäisyys tarkoittaa ylimääräisiä rivejä teoreettisen minimin lisäksi.
Optimaalisen rivikokoelman löytäminen ei ole suoraviivainen tehtävä enkä usko, että löytyy oikotietä onneen, mutta kokoelmassa täytyy olla yli 200 lottoriviä. Alla hieman alustusta aiheeseen. Arvottavan lisänumeron merkitystä en ole huomioinut.
Mikä tahansa yksittäinen lottorivi tuottaa voiton 202280 tapauksessa 18643560:sta. Jos kokoelman seuraavalla rivillä ei ole yhteisiä numeroita ensimmäisen kanssa, sekin tuottaa voiton 202280 tapauksessa. Ilman yhteisiä numeroita voidaan laatia vain 5 riviä. Kuudenteen riviin on poimittava mukaan kertaalleen jo käytettyjä numeroita ja jos kahdella rivillä on vain yksi yhteinen numero, riveihin osuu kaksi voittoa 400 tapauksessa. Jos kahdella rivillä on kaksi yhteistä numeroa, riveihin osuu kaksi voittoa 3200 tapauksessa jne.
Tehtävänä on siis tuon päällekkäisyyden minimointi siten, että jokaisella mahdollisesti arvottavalla rivillä 18643560:sta voittaisi yhden, mutta mahdollisimman pienen määrän voittoja.
Tehtävään kannattaa valita tehokas ohjelmointikieli koska kuten kirjoitit, tarkistaminen on hidasta. Jos unohdamme assemblerin, C-kieli lienee paras vaihtoehto. Esimerkiksi näin:
char rivi[7] = {1,2,3,4,5,6,7};
...
for (;;)
{
// Tarkista voittaako rivi[]
...
// nextrow
for (int i=7; rivi[i-1] == 40-7 i;)
if (--i==0)
exit(0); // Valmis, kaikki rivit läpikäyty
for (rivi[i-1] ; i <= 7; rivi[i-1] = rivi[i-2] 1);
}
Uloin for-luuppi funktion sisään ja "Tarkista voittaako rivi[]" -kohtaan silmukka, jossa tarkistataan kokoelman rivit. Jos rivi[] ei tuota voittoa yhdenkään kokoelmassa olevan rivin kanssa, kokoelmaan on lisättävä numeroita tai kokonainen rivi siten, että rivi[] tuottaa voiton.
Kokoelman rivien tarkistaminen kannattaa tehdä taitavasti, koska siitä saattaa tulla ohjelman ylivoimaisesti eniten aikaavievä osuus. Tarvittaessa kerron lisää. Onnea tehtävään!- Anonyymi
Mikä on tehokkain tapa tarkistaa voittaako rivi?
- Anonyymi
Anonyymi kirjoitti:
Mikä on tehokkain tapa tarkistaa voittaako rivi?
Tämän päivän PC-koneet ovat siksi tehokkaita, että C-kielellä koodattu ohjelma käy esimerkiksi kaikki 18643560 riviä läpi silmänräpäyksessä, oli tarkistustapa mikä tahansa.
Mutta tehokkain tapa on sellainen, missä kokoelman rivit säilytettään bittimaskeina (uint64_t), samoin esimerkin rivi[]. Testaaminen tapahtuu yksinkertaisesti and-operaattorilla ja laskemalla tuloksen ykkösbitit. Laskeminen on ylivoimaisesti tehokkainta prosessorin POPCNT-käskyllä (ks. __popcnt64() ja vastaavat funktiot), jos prosessorista sellainen löytyy. - Anonyymi
Anonyymi kirjoitti:
Tämän päivän PC-koneet ovat siksi tehokkaita, että C-kielellä koodattu ohjelma käy esimerkiksi kaikki 18643560 riviä läpi silmänräpäyksessä, oli tarkistustapa mikä tahansa.
Mutta tehokkain tapa on sellainen, missä kokoelman rivit säilytettään bittimaskeina (uint64_t), samoin esimerkin rivi[]. Testaaminen tapahtuu yksinkertaisesti and-operaattorilla ja laskemalla tuloksen ykkösbitit. Laskeminen on ylivoimaisesti tehokkainta prosessorin POPCNT-käskyllä (ks. __popcnt64() ja vastaavat funktiot), jos prosessorista sellainen löytyy.Kyseisiä algoritmejä on ollut 70. vuodasta lähtien! Kato netistä mallia!
- Anonyymi
Koodasin aikanaan Amigalla tuontyyppisen softan, ja voitin joka viikko muutamia satasia, mutta mitään isompaa pottia ei tullut. Syy tähän oli, että numerot pääsääntöisesti oli aina oikein, mutta se lisänumerojärjestelmä sotki sitten pakkaa juuri sen verran että mitään isompaa pottia ei omalle kohdalleni osunut.
Iterointia olisi pitänyt kehittää niin että otetaan huomioon todennäköisyys jokaiselle numerolle sen suhteen että tulisiko kyseeseen lisänumero, vai ns. 'virallinen' numero.
Empä tuon jälkeen ole kokeillut, mutta kokemusta on, ja aika positiivistakin suoraan sanottuna.
Tulipahan ainakin todistettua että toimii, ja että mahdollista tämä on.- Anonyymi
Amigan aikoihin rivit piti ehkä jättää paperiselle kupongille rastitettuina. Taisi olla hikinen urakka. Nykyään on helpompaa, kun rivit voi rastittaa netissä.
Lisänumerot eivät sotke tällaista järjestelmää. Varsinkaan, kun nykylotossa arvotaan vain yksi lisänumero ja ainoa voittoluokka, johon se käytännössä vaikuttaa on 6 1 oikein. 3 1 tuloksen voitto on yhtä tyhjän kanssa, joten ei ole väärin lukea pienimmäksi voitoksi 4 oikein tulos.
Tässä tarkoitettu järjestelmä on käytännössä järjetön siksi koska nykylotossa pienimpien voittojen euromäärät ovat kuihtuneet käytännösä olemattomiksi. Edellä on kerrottu, että rivien optimimäärä olisi 93 ja käytännössä yli 200. Järjestelmän hinnaksi tulisi siis ainakin 200 euroa ja se takaisi vain 4-oikein tuloksen, jolla voittaa 10 euroa!
Ohjelmointitehtävänä silti mielenkiintoinen ja vaativakin Laitahan Amiga-koodisi näytille... - Anonyymi
"voitin joka viikko muutamia satasia"
Höpö höpö. - Anonyymi
Anonyymi kirjoitti:
"voitin joka viikko muutamia satasia"
Höpö höpö.Lotossa ei ole mitään mahdollisuutta kehittää mitään järkevää järjestelmää joka toisi enemmän voittoja. Kaikki perustuu satunnaisuuteen.
- Anonyymi
Anonyymi kirjoitti:
Lotossa ei ole mitään mahdollisuutta kehittää mitään järkevää järjestelmää joka toisi enemmän voittoja. Kaikki perustuu satunnaisuuteen.
Lotto perustuu satunnaisuuteen, olet oikeassa. Mutta olet väärässä siinä, etteikö järkevällä järjestelmällä voisi vaikuttaa voittojen määrään.
Tunnetuin esimerkki voittojen määrään vaikuttamisesta lienee kautta aikain yleisimmän rivin lottoaminen. Jos rastitat numerot 1, 2, 3, 4, 5, 6 ja 7 ja voitat, joudut tiettävästi jakamaan (5 oikein tai paremman) voittoluokan voiton poikkeuksellisen suuren pelaajajoukon kanssa.
Toinen esimerkki on ero järjestelmä- ja haravapelien välillä. Järjestelmä takaa osumien määrää vastaavan voiton ja tuo suuren määrän pienempiä voittoja. Harava takaa vain 4- ja 5-oikein tuloksen, mutta huomattavasti pienemmällä kustannuksella. Toki voiton todennäköisyys sijoitettua euroa kohden on kummassakin pelissä sama. Vastaavasti ruletissa voi asettaa panoksensa yhdelle numerolle (1:30) tai esim. kolmelle (1:10).
Tämän ketjun aloittaja haki siis haravaa, joka antaisi varman voiton joka kerta. Sellaisessa olisi hyvinkin järkeä mm. lottoporukoiden peli-innon ylläpitäjänä. Tuskin mikään on lannistavampaa kuin pelata viikosta toiseen lottoporukassa, joka ei koskaan voita mitään.
Keskustelemme ohjelmoinnista ja sen suhteen järjestelmän pohtimisessa on järkeä, mitä Veikkauksen lotossa ei juuri ole.
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Marin on ehkä maailman kaunein "Nelikymppinen"
Marinin julkaisu on saanut yli 68 500 tykkäystä. Postauksen kommenttikentässä ylistetään paljon Marinin kauneutta, jota3282826Vernu Vasunta
On mahotonta miten marjanpoimijoita on kohdeltu! Eikö paremmalla kohtelulla olisi saanut paremman tuloksen?1052130En kelpaa sinulle
Varattuna - olen sinulle ongelma. Eroaminen vuoksesi voi olla turhaa, sillä me ei puhuta, kun olen varattu ja kumpikin v1201610Taidat vanhempi nainen
Haluta sen tien itsellesi. juokse vaan karkuun ! Pahentaa vaan asiaa.Pitäs toimia ihan toisin päin731154- 711022
- 61983
Voi nainen...
Kun luovutit meistä liian aikaisin, just kun aloin oppimaan sinua. Jos oisin alussa jo lukenut aiheesta oisin voinut toi41950Venäjä aikoo yksipuolisesti muuttaa rajalinjauksia Suomenlahden itäosassa
Venäjä aikoo muuttaa rajalinjauksia Suomenlahden itäosassa Venäjän saarten eteläpuolella. Ylen jutussa kerrotaan mm.148914Suomi lähettää tarkkailijoita merialueelle
Venäjä on ilmoittanut aikovansa ylittää Suomen merialueen rajat kysymättä lupaa kertomalla että Suomen merialueen raj290842- 40754