уторак, 16. јун 2015.

Kako da isprogramirate program Lotto u C programskom jeziku?

Kad kažemo program za Lotto uglavnom se misli na neki jednostavan program koji nam slučajnim biranjem brojeva izvlači 7 brojeva u rasponu od 1 do 39 i prikazuje na ekranu. Međutim može li taj program da se napravi malo bolje pa da nam prikaže brojeve koje imaju veću verovatnoću da će biti izvučeni? Možemo li mi da ubacimo malo logike i da makar malo eliminišemo i smanjimo količinu mogućih kombinacija? Moje mišljenje je da u Lotto-u imate 39 kuglica i svaka od njih ima istu šansu da bude izvučena svaki put kad se izvlače brojevi i da je tu nemoguće bilo šta promeniti. Čak sam mnogo godina sumnjao da je Lotto namešteno; da li ste kad čuli da je izvučeno 5 sedmica u jednom izvlačenju? Međutim, postoje ljudi koji igraju Lotto redovno. Postoje ljudi koji su čak dobili i sedmicu. Oni su adekvatniji da pričaju o tome, ali kad ste programer ljudi će tražiti od vas svašta da programirate. U svakom slučaju tema jeste izazov i tera vas na razmišljanje. Takođe je jedan veliki napredni korak za kodiranje.


( Državna Lutrija Srbije, doboš sa loto kuglicama )

Državna Lutrija Srbije tvrdi da je od 2005 godine do danas, izvučeno 68 dobitnika sedmice, od toga 30 u Beogradu. Takođe kaže da se 4 puta desilo da su izvučene po 2 sedmice u jednom izvlačenju. Danas se Lotto u Srbiji igra dvaput sedmično. Izvlačenje se može gledati utorkom i petkom na TV Prva. Krajem 80tih u bivšoj Jugoslaviji, niste mogli zamisliti kuću u nekom mestu koja nije igrala Lotto, danas je to retkost, ali i pored toga dobitna kombinacija sedmica je i dalje impresivna.

Cena samo 1 kombinacije je 60 dinara ili oko pola evra, tako da za 1 listić treba izdvojiti oko 5 evra. Ako pogledamo neku uplatu kad je izvučena sedmica, odmah nam je jasno da za jedan listić nam minimum treba 2 četvorke da bi smo imali bilo kakav dobitak ili 1 petica na 10 listića.

Utorak, 28 aprila 2015 godine u 33 kolu je izvučeno:

  • 1 Sedmica .........….. 303,340,942.50 DIN ili ..............524,670.62 EUR
  • 12 Šestica ......….....….....283,891.25 DIN ili .........…….2,362.79 EUR
  • 531 Petica ....……….…..….6,415.62 DIN ili …........……. 53.39 EUR
  • 8,596 Četvorki ...………..…..600.00 DIN ili ………..….…..4.99 EUR
  • 61,852 Trojki …………...……60.00 DIN ili …………...…..0.49 EUR

Odmah nam je jasno da vam se ne isplati igrati Lotto sa što više kombinacija. Da je trojka 600.00 dinara to bi bila neka druga priča. Međutim, hajde da vidimo kako da eliminišemo neke Lotto kombinacije na nivou male verovatnoće da će se desiti tokom izvlačenja. 


Prvo ćemo da vidimo koliko to otprilike postoji loop kombinacija ( Loto ima 15.380.937 kombinacija ) ili nizova od 7 brojeva. Matematički bi to predstavili kao 39^7. Ali u C programskom jeziku to bi izračunali funkcijom pow() koja se nalazi u biblioteci math.h. Možemo odmah dodati i druge datoteke zaglavlja koje će nam biti potrebne kasnije.

/* Lotto

Manuel Radovanovic

www.manuelradovanovic.com */

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<math.h>

int main ()

{

        unsigned long long counter = 0ULL;

        counter = pow(39, 7);

        printf( "Combination: %llu \n", counter );

        return 0;

}


Prvo smo deklarisali najveću celobrojnu promenjivu tipa long long. Taj tip je ekvivaletan int64 u C# programskom jeziku. U tip long long možete da čuvate brojeve u rasponu od − 9 223 372 036 854 775 807 do + 9 223 372 036 854 775 807. Ako dodate prefiks unsigned tipu long long onda će se vaš raspon brojeva kretati od 0 do 18 446 744 073 709 551 615. Kad kompajlirate i pokrenete navedeni kod dobiće:

Combinations: 137231006679 hacker@~/workspace/c$ 

Međutim to nije tačan broj mogućih kombinacija Lotto-a jer u Lotto-u nemate duplih brojeva. Tačan broj je manji.


( Lotto kuglice )

Bez obzira koji se Lotto kuglice izvuku, na kraju će tv voditeljka uvek kuglice poslagati od manjeg broja prema većem!

Znači bez obzira da li su izvučeni brojevi 1342 ili 2134 ili 4213; oni su uvek na kraju isti, tj. 1234.
To takođe znači da npr. broj na poziciji 6 ne može biti veći od 38 ili manji od 6. Zanimljivo! Znači, deklarišemo jednu niz promenjivu u koju možemo da čuvamo 7 brojeva. Obratite pažnju da kad deklarišemo promenjivu, morate joj dodeliti neku vrednost inače će te dobiti čudne brojeve na ekranu. Programski jezik  sam izabere bilo koji broj i dodeli promenjivoj ukoliko vi to ne uradite. Niz vam se deklariše kao i svaka druga promenjiva, samo što dodate [ ] zagrade i u njima navedete broj elemenata u nizu. Brojevi elemenata uvek počinju od 0 i zato za naših 7 brojeva pišemo 6 jer od 0 do 6 imate 7 elemenata. Zadajte navedene vrednosti nizu koje sam ja naveo. Zašto? 

short p[6];

p[0] = 1;

p[1] = 2;

p[2] = 10;

p[3] = 11;

p[4] = 12;

p[5] = 13;

p[6] = 13;


Retko se dešava da se na Lotto-u izvuku svi dvocifreni brojevi. Takođe retko se dešava da se izvuku više od dva jednocifrena broja! 

To rešavamo tako što odmah definišemo da prvi broj u nizu može biti samo jednocifren broj, tj. broj od 1 do 9. Drugi broj može biti jednocifren ali i dvocifren. Ali takođe on ne može biti 1 jer onda nebi bio veći od predhodnika, i ne može biti veći od 34 jer onda nebi bio manji od brojeva na pozicijama iza njega. Od treće pozicije brojevi mogu biti samo dvocifreni. Da bi smo sve to isprogramirali pravimo jednu while petlju i uslovljavamo prolaz naših brojeva. Takođe postavljamo i jednu label-u jump koja će nam trebati.

while (p[0] < 10) {

jump:

     // 7 position numbers
        p[6]++;

          // 6 position numbers
             if (p[6] == 40) {
                  
                  p[5]++;
                  p[6] = 13;

                   // 5 position numbers
                      if (p[5] == 39) {

                          p[4]++;
                          p[5] = 13;

                          // 4 position numbers
                             if (p[4] == 38) {

                                 p[3]++;
                                 p[4] = 12;

                                 // 3 position numbers
                                    if (p[3] == 37) {

                                    p[2]++;
                                    p[3] = 11;

                                    // 2 position numbers
                                       if (p[2] == 36) {

                                       p[1]++;
                                       p[2] = 10;

                                       // 1 position numbers
                                          if(p[1] == 35) {
                                           
                                          p[0]++;
                                          p[1] = 2;

                                       }
                                  }
                             }
                        }
                   }
             }

             if (p[0] == 10) break;

             if (p[6] > p[5] && p[5] > p[4] && p[4] > p[3] && p[3] > p[2] &&

                  p[2] > p[1] && p[1] > p[0]) {



Kao što naredbu If definišemo kao naredbu za uslovljavanje, tako i petlju možete definisati kao naredbu koja ponavlja neki ciklus onoliko puta koliko ste zadali uslov. Navedena petlja počinje sa uvećavanjem 7 pozicije u nizu i prekida se čim 1 pozicija postane 10. Znači! Petlja while se izvršava tako što zadnju poziciju uvećava za 1. Ako je zadnja pozicija veća od 39, tačnije 40 onda se predhodna pozicija uvećava za 1 dok se zadnja pozicija vraća na najmanji broj u zadnjoj poziciji. To je kod nas 14, ali ga podešavamo kao 13, isto kao i kod pozicije 6 jer čim zadnja pozicija uđe u petlju while, on će biti uvećam za 1. Zatim čim 6 pozicija dođe do maksimalnog broja takođe uvećava poziciju 5 za 1 i ona se vraća na minimum i tako sve dok prva pozicija ne dođe do svog maksimuma. Pozicija 1 je jednocifren broj i njegov maksimum je broj 9. Zato čim dođe uvećanjem do 10 petlja se prekida. 

Posle zadajemo glavni uslov koji nam definiše da isti brojevi ili brojevi manji od predhodne pozicije ne mogu proći. Glavni uslov nam propušta nizove samo ako su pozicije složene od manjeg broja prema većem. U prošlom primeru, programiranju kalkulatora, pogledajte ovde, smo koristili if naredbe. U ovom primeru mi ugnježdavamo naredbe if jednu u drugu. Tako ubrzavamo program jer nema potrebe da program ispituje npr. uslovljavanje 4 pozicije ako nije došlo do promene u 5 poziciji.

Retko se dešava da se u izvlačenju Lotto brojeva izvlače brojevi zaredom, poput 1234... 789... ! To se retko dešava i sa samo tri broja u nizu!

Rešenje ovde je vrlo jednostavno. Ako od 3 pozicije, druga je veća za 1 od prve pozicije i u isto vreme treća pozicija je veća za 1 od druge, onda imamo nabrajanje poput 123... Zato ćemo zadati petlje za sve pozicije od prve do zadnje. Ako se nigde ne nabraja ni 3 broja u nizu, onda neće ni više brojeva u nizu. Kad pronađemo nepravilan niz vraćamo ga na label-u jump

// ignore numbers in row in any 3 numbers

if(p[1] == (p[0] + 1) && p[2] == (p[1] + 1)) goto jump;

if(p[2] == (p[1] + 1) && p[3] == (p[2] + 1)) goto jump;

if(p[3] == (p[2] + 1) && p[4] == (p[3] + 1)) goto jump;

if(p[4] == (p[3] + 1) && p[5] == (p[4] + 1)) goto jump;

if(p[5] == (p[4] + 1) && p[6] == (p[5] + 1)) goto jump;


Retko se dešava da su u izvlačenju Lotto brojeva svi izvučeni brojevi parni ili neparni brojevi! Čak se retko dešava i da imate samo 1 ili 2 parna ili neparna broja!

Izračunavanje parnog ili neparnog broja se najlakše izračunava artimetičkom operacijom modulos. U  programskom jeziku modulos se definiše simbolom % . Kad utvrdimo da li je neki broj u poziciji paran onda promenjivu even uvećavamo za 1. Tako znamo tačno za svaki niz koliko ima parnih brojeva. Ukoliko npr. niz ima 6 parnih brojeva, to takođe znači da on ima samo 1 neparan broj u nizu i takav broj izbacujemo, vraćajući ga na label-u jump. Svaku promenjivu za deklarisanje uvek deklarišete na početku programa tj. main() funkcije, radi preglednosti. Takođe promenjivu even moramo da vratimo posle izračunavanja opet na 0 posle svakog ciklusa u petlji. 

short even = 0;

// ignore if more than 5 numbers are even or odd numbers

if(p[6] % 2 == 0) even ++;

if(p[5] % 2 == 0) even ++;

if(p[4] % 2 == 0) even ++;

if(p[3] % 2 == 0) even ++;

if(p[2] % 2 == 0) even ++;

if(p[1] % 2 == 0) even ++;

if(p[0] % 2 == 0) even ++;

if( even == 7 || even == 6 || even == 1 || even == 0 ) goto jump;

even = 0; 

Retko se dešava da su u izvlačenju Lotto brojeva svi izvučeni brojevi sadržavaju više od 4 broja drugih desetica ( brojevi od 11 do 19 ). To isto važi za treće i 4 brojeve desetica! 

Prvo se deklarišu 3 promenjive, koje će nam brojati koliko imamo drugih, trećih i četvrti desetica. ukoliko neki niz sadrži više desetica od 4, taj niz eliminišemo.

short num10s = 0;

short num20s = 0;

short num30s = 0;


// ignore if more than 4 numbers are from 10 - 19

if(p[6] > 9 && p[6] < 20) num10s ++;

if(p[5] > 9 && p[5] < 20) num10s ++;

if(p[4] > 9 && p[4] < 20) num10s ++;

if(p[3] > 9 && p[3] < 20) num10s ++;

if(p[2] > 9 && p[2] < 20) num10s ++;

if(p[1] > 9 && p[1] < 20) num10s ++;

if( num10s > 4 ) goto jump;


// ignore if more than 4 numbers are from 20 - 29

if(p[6] > 19 && p[6] < 30) num20s ++;

if(p[5] > 19 && p[5] < 30) num20s ++;

if(p[4] > 19 && p[4] < 30) num20s ++;

if(p[3] > 19 && p[3] < 30) num20s ++;

if(p[2] > 19 && p[2] < 30) num20s ++;

if(p[1] > 19 && p[1] < 30) num20s ++;

if( num20s > 4 ) goto jump;


// ignore if more than 4 numbers are from 30 - 39

if(p[6] > 29 && p[6] < 40) num30s ++;

if(p[5] > 29 && p[5] < 40) num30s ++;

if(p[4] > 29 && p[4] < 40) num30s ++;

if(p[3] > 29 && p[3] < 40) num30s ++;

if(p[2] > 29 && p[2] < 40) num30s ++;

if(p[1] > 29 && p[1] < 40) num30s ++;

if( num30s > 4 ) goto jump; 


Koliko sad imamo Lotto kombinacija?

Možemo aktivirati naš brojač counter, zatim ispisom na ekran možemo videti koliko sad imamo kombinacija i koje su. Čak možemo prikazivati npr. i koliko svaka kombinacija ima parnih brojeva.   

counter ++;

          printf("Positions are %hd %hd %hd %hd %hd %hd %hd - %hd \n",

                                                p[0],p[1], p[2], p[3], p[4], p[5], p[6], even);

          printf("Counter: %llu \n", counter); 

Ukoliko sada pokrenete ovaj program dobićete:

...
Positions are 9 31 33 35 36 38 39 - 2
Counter: 1155920
Positions are 9 32 33 35 36 38 39 - 3
Counter: 1155921
hacker@~/workspace/c$


Kao što vidite sa 137 miliona mogućih Lotto kombinacija, mi smo ih sveli na tačno 1 155 920. Naravno da je i to mnogo. Moguće je nastaviti i dalje umanjivati verovatnoću izvlačenja Lotto brojeva, međutim to nije nikakva garancija da će te dobiti na Lotto-u . Ipak je lakše pogoditi verovatnoću nego sam broj.

Kako da moj program bira Lotto kombinaciju umesto mene?

Sad je jednostavno dodati samo jednu rand() funkciju zajedno sa srand() funkcijom i da kažemo programu da se zaustavi na kombinaciji koju je izabrao. Bez srand() funkcije rand() funkcija bi stalno birala isti niz.

srand ( time(NULL) );
unsigned long long rnum = rand() % 1155921 + 1;

if (counter == rnum) {

     printf("\n\nYour WIN lotto numbers are: %hd %hd %hd %hd %hd %hd %hd\n\n",
                                                                        p[0],p[1],p[2],p[3],p[4],p[5],p[6]);

break;
}

To je sve pokrenite program i dobićete:

...
Positions are 2 6 10 15 16 19 28 - 5
Counter: 229655
Positions are 2 6 10 15 16 19 29 - 4
Counter: 229656


Your WIN lotto numbers are: 2 6 10 15 16 19 29


hacker@~/workspace/c$


Kako to sve izgleda možete pogledati i na video-u.


( C - Tutorial - 2. Lotto )