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
2003
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
VVM Riikka Purra ministerin asemassaan valehteli ja rikkoi perustuslakia.
Valtiovarainministeri Riikka Purra (PS) kiisti Ylen ykkösaamussa luvanneensa ennen vaaleja, ettei pienituloisilta leikat489654Purra ennen vaaleja: "pienituloisten etuuksista leikkaaminen ei meille käy"
"...perussuomalaisten ero muun muassa kokoomukseen, joka haluaa leikata pienituloisten etuuksista, se ei meille käy."383596Ammattiliittojen jäsenmaksut valtion maksettavaksi
Ammattiliitot neuvottelvat jäsenilleen paremmat palkat, jotka lisäävät valtio verotuloja. Tästä syystä valton tulee maks323155Toksinen persuvasemmisto
Kun toksiset ihmiset eivät kykene hallitsemaan sinua, saamaan sinua näkemään asiat niin kuin he haluaa, toimimaan niin k202800Rikkaiden ja yritysten veroaleen ei ole varaa
Ei pieni Suomi pysty elättämään vanhenevaa väestöä nykyisellä veroasteella. Ainakin 5-prosenttiyksikköä pitää kokonaisve192365Riikka Purra: Autoilu tulee Suomen valtiolle pyöräilyä edullisemmaksi! Siksi pyöräetu poistettiin!
🐸🐸🐸🐸🐸 Perussuomalaisten trollitehdas kiukkuaa kun Riikka Purra päästi taas sammakoita suustaan että autoilu tulee S3451867"Minua ei kiinnosta opiskelu eikä töissä käyminen"
Voiko lausunnosta päätellä lainkaan mikä puolue saattaisi ajaa tuollaisen kansalaisen elämäntavan mahdollistamista? htt361447- 1011292
Tikkunenällä on kovat luulot itsestään
Mut ei tarjottavana muuta kuin katkeruutta, ilkeyttä ja ilkeä luonne hyih.. oikea miesten nielijä Onneksi kaivatullani131243- 931093