Ülesande püstitus
Analüüs
Disain & realisats
Andmed
Programmi strukt.
Pileti ja loosimise numbrite loomine
  Eriarvud
  Sorteerimine
  Tabamused
Sorteerimine lisa
 mull
 valik
 shell

Rakendus "Loto"

Ülesande püstitus

Koostada rakendus, mis võimal­dab imiteerida lotomängu sarnaselt näiteks Keno loto või Viking lotoga. Mängija sisestab või laseb arvutil genereerida teatud hulga juhuslikke üks­teisest erinevaid numbreid (näiteks 3 kuni 10). Loosimisel luuakse samuti teatud hulk juhuslikke arve (näiteks 10 kuni 20). Numbrid peavad olema mingis kindlas vahemikus (näiteks 1 … 64, 1 … 36 vm). Programm peab tegema kindlaks kokkulangevate numbrite arvu piletil ja loosimisel.
Kasutajaliides võiks sisaldada järgmisi elemente: loendite monitorid, kus kuvatakse pileti (Pilet), loosi (Loos) ja kokkulangevad numbrid (Pihtas). Muutujate liuguritega monitorid, mille abil saab mängija valida numbrite arvu piletil (np), numbrite arvu loosimisel (nl) ning maksimaalse võimaliku numbri piletil ja loosimisel (max). Samuti võiks olla muutuja monitor, mis näitab kokkulangevate numbrite arvu (tabas). Vastava tegevuse käivitamiseks võib teha käsunupud või kasutada selleks mingeid muid spraite.

Analüüs

Rakendus peab võimaldama luua kaks komplekti juhuslikke arve etteantavas vahemikus. Arvud salvestatakse vastavates loendites: üks sisaldab pileti numbreid, teine loosimise numbreid. Loosimise numbreid peab olema rohkem kui pileti numbreid. Kõik pileti numbrid peavad olema erinevad. Samuti ei tohi olla ühesuguseid numbreid loosimise loendis.
Selleks, et kasutajal oleks lihtsam võrrelda ja kontrollida pileti ja loosimise numbreid, peab programm kuvama need sorteerituna kasvavas järjestuses.
Programm peab leidma kokkulangevate numbrite arvu ja kuvama need numbrid eraldi loendis (kui on). Võib kehtestada ka mingid reeglid võidusumma määramiseks.
Seega peab rakenduse loomisel realiseerima järgmised ülesanded:

• etteantud hulga üksteisest erinevate kindlas vahemikus olevate juhuarvude genereerimine ja salvestamine loendis,
• loendite elementide järjestamine (sorteerimine),
• kahes loendis olevate kokkulangevate väärtuste kindlakstegemine ja eraldamine omaette loendisse.

Numbrite genereerimine ja sorteerimine toimub pileti ja loosimise jaoks ühtemoodi, erinevus on ainult väärtuste hulgas. Hiljem näeme, et erinevate arvude loomise ja kokkulangevate numbrite kindlakstegemisega, kaasneb veel üks sageli programmides esinev tegevus – otsimine. Arvestades, et nimetatud tegevused esinevad algoritmides ja programmides tihti (eriti sorteerimine ja otsimine), on otstarbekas nende tegevuste täitmiseks luua suhteliselt universaalsed protseduurid. Kahjuks puuduvad Scratchi praeguses versioonis vahendid parameetrite ja argumentide kasutamiseks andmevahetusel skriptide vahel. Seepärast pole võimalik luua täiesti universaalseid protseduure (skripte), mida saab näiteks kopeerimise või importimise teel viia ühest programmist teise ilma spetsiaalsete meetmete rakendamiseta protseduuride sidumiseks. Kuid kasutades võimalust spraitide ekspordiks ja importimiseks (koos skriptidega), saab tekitada siiski võimaluse üldise iseloomuga skriptide lülitamiseks erinevatesse projektidesse.
Et praegu saaks kasutada erinevate arvude loomisel ja sorteerimisel pileti ja loosimise numbrite jaoks samu skripte (protseduure), võib võtta kasutusele abiloendi, milles tehakse nimetatud tegevused, ja tulemused, nö lõplikul kujul, kopeerida abiloendist pileti ja loosimise loenditesse.
Alternatiivse variandina võiks pileti ja loosimise numbrite loomiseks ja sorteerimiseks teha kaks sõltumatut skriptide gruppi: üks pileti jaoks, teine loosimise jaoks. Skriptid erinevate arvude genereerimiseks ja sorteerimiseks peab sellisel juhul dubleerima ja seadistama vastavalt kasutatavatele andmetele (loenditele).

Disain ja realisatsioon

Andmed

Põhimuutujad

• max – maksimaalne number piletil ja loosimisel, minimaalne väärtus on alati 1,
• np– numbrite arv piletil,
• nl – numbrite arv loosimisel,
• tabas – kokkulangevate numbrite arv.

Lisaks neile on kasutusel mitmeid täiendavaid, peamiselt lokaalseid, muutujaid erinevates skriptides.

Loendid

• Pilet (np) – pileti numbrite loend (massiiv),
• Loos (nl) – loosi numbrite loend,
• Pihtas (tabas) – kokkulangevate numbrite loend (võib olla ka tühi),
• V(*) – abiloend pileti ja loosi numbrite loomisel ja sorteerimisel (vt allpool).

Programmi struktuur ja skriptid

On ette nähtud kolm suhteliselt sõltumatut skriptide gruppi: Tee pilet, Loosi ja Kontrolli. Iga grupp koosneb peaskriptist ja alamskriptidest. Täitmine algab pea-skriptist, mis teadete abil paneb tööle alamskriptid.

Kuna pileti ja loosi numbrite loomine ja sorteerimine toimub analoogselt, on otstarbekas salvestada tegemise ajal pileti ja loosimise numbrid kordamööda abiloendisse ja kopeerida tulemused sealt loenditesse Pilet ja Loos.

Pileti ja loosimise numbrite loomine

Pileti ja loosimise numbrite loomine ja sorteerimine toimub täiesti sarnaselt. Erinevus on ainult elementide arvus np või nl ning loendis, kuhu salvestatakse tulemused. Mõlemal juhul kasutatakse abiloendit V, kust loodud elemendid kopeeritakse loendisse Pilet või Loos. Siin on näidatud ainult pileti numbrite töötlemine.

Erinevate arvude loomine – skriptid Tee arvud ja Otsi

Skript Tee arvud loob üksteisest erinevad juhuarvud ja salvestab need loendis V.

Kõigepealt eemaldatakse loendist V kõik elemendid ning ükshaaval luuakse ja lisatakse loendisse uued elemendid. Iga uue elemendi korral võetakse kõigepealt muutuja nr väärtuseks 1 (nr<>0), luuakse juhuarv ja omistatakse see muutujale x. Skript Otsi kontrollib, kas x-ga võrdne väärtus on loendis V juba olemas või mitte. Seda näitab muutuja nrväärtus peale skripti töö lõppu. Loendi elemente võrreldakse järjest x-ga. Kui tingimus x=V(k) osutub tõeseks, omistatakse muutujale nr väärtus k ja skripti töö katkestatakse. Kui x-ga võrdset väärtust ei ole, jõutakse korduse lõpuni ja muutujale nr omistaks väärtus null. Esimesel juhul (nr<>0) genereeritakse uus juhuarv ja kontrollitakse uuesti. Seda tehakse seni, kuni muutuja nr väärtus saab nulliks (sellist väärtust ei ole). Seejärel lisatakse x loendi lõppu ja sama toimub järgmise elemendiga. Paneme tähele, et esimese elemendi korral kordust ei toimu, sest loend on veel tühi (pikkus on null) ning muutujale nr omistatakse kohe väärtus 0.

Paneme tähele, et esimese elemendi korral kordust ei toimu, sest loend on veel tühi (pikkus on null) ning muutujale nr omistatakse kohe väärtus 0.

Sorteerimine

Sorteerimine seisneb väärtuse järjestamises kasvavalt või kahanevalt. Enamasti sorteeritakse kasvavas järjestuses, kuid põhimõttelist vahet siin ei ole. Reeglina toimub sorteerimine samas loendis (massiivis). Sorteerimine leiab väga sageli kasutamist andmetöötluses. Selleks on loodud palju erinevaid meetodeid ja algoritme, mille täitmise ajas võivad olla väga suured erinevused. Siin kasutatakse ühte kõige lihtsamat algoritmi nn jadasorteerimist, mis on suurte loendite korral väga aeglane. Praegu ei ole andmehulgad eriti suured.

Algoritmi täitmisel toimub ca n2 võrdlust, vahetuste arv sõltub andmete sorteerituse astmest. Taoliste algoritmide kohta öeldakse, et nende keerukus on n2. Elementide arvu kasvamisel n korda, suureneb aeg n2 korda. Näiteks, kui elementide arv suureneb 10 korda, suureneb täitmise aeg 100 korda!

Vaadake täitmise demot

Kokkulangevate numbrite kontrollimine

Võrreldakse väärtusi kahes loendis Pilet ja Loos. Leitakse kokkulangevate väärtuste arv ja salvestatakse see muutujas tabas. Kokkulangevad numbrid (kui on) salvestatakse loendis Pihtas.

Mõned täiendavad sorteerimisalgoritmid

Mullsortimine

Mullsortimine on üks vanemaid sorteerimise algoritme. Massiiv vaadatakse korduvalt läbi. Iga kord võrreldakse naabreid ning kui V(i) > V(i+1), vahetakse need. Väiksemad väärtused „tõusevad“ ülespoole, suuremad laskuvad. Läbivaatamine kestab seni, kuni ei toimu ühtegi vahetust.
Keerukus n2. Meetod on 2-3 korda aeglasem kui valiksortimine. Üldjuhul veidi aeglasem kui jadasortimine. Kiire, kui väärtused on peaaegu järjestatud

protseduur Sort_Mull(V, n)  tun = 1  m = n - 1  kordus kuni tun = 0     tun = 0     kordus i = 1... m        kui V(i) > V(i + 1) siis        abi = V(i)        V(i) = V(i + 1)        V(i + 1) = abi        tun = 1     lõpp kui     m = m - 1  lõpp kordus

# Python def sort_mull(V):  n = len(V)  m = n - 1  tun = 1  while (tun != 0):       tun = 0       for i in range (m):            j = i + 1            if (V[i] > V[j]):                 V[i], V[j] = V[j], V[i]                 tun = 1                 m = m - 1

Valiksortimine minimaalse elemendi valimisega

Muudetakse indeksi i väärtust vahemikus 1 kuni n - 1, iga i korral leitakse minimaalne element vektori osas i kuni n ja vahetatakse see elemendiga i.
Keerukus n2, 2-3 korda kiirem kui mullsortimine.

protseduur Sort_Min(V, n)  kordus i = 1 kuni n - 1     min = V(i)     k = i     kordus j = i + 1 kuni n        kui V(j) < min siis           min = V(j)           k = j        lõpp kui     lõpp kordus     V(k) = V(i)     V(i) = min  lõpp kordus

void sordi_min(int V[], int n) // C {  int min, k;  for (int i = 1; i <= n-1; i++)  {  min = V[i]; k = i;  for (int j = i+1; j <= n; j++)  if (V[j] < min)  {min = V[j]  k = j; }  V[k]= V[i];  V[i] = min;  } }

Shelli meetod

Sarnane mullsortimisele, kuid kasutatakse muutuvat sammu: alguses suur, edaspidi järjest väheneb. Keerukus sõltub oluliselt sammu valikust. Üks paremaid sammu muutmise reegleid - ni = ni-1 / 1,3. Keerukus ca n*log2n. Oluliselt kiirem eelmistest, eriti kui n on suur:
n = 1000 - ca 10 korda, n = 100 000 - ca 500 korda, n = 1 000 000 - ca 5000 korda!

prots Sort_Shell(V, n)  h = n  tun = 1  kordus kuni h=1 & tun=0     h = täisosa(h/1,3)     kui h < 1 siis h = 1     tun = 0     kordus i = 1... n - h        kui V(i) > V(i + h) siis           abi = V(i)           V(i) = V(i + h)           V(i + h) = abi           tun = 1        lõpp kui     lõpp kordus  lõpp kordus

Sub Sort_Shell(V, n) ’ VBA  Dim h, i, j, tun, abi  h = n: tun = 1  Do Until h = 1 And tun = 0     h = Int(h / 1.3)     If h < 1 Then h = 1     tun = 0     For i = 1 To n - h        j = i + h        If V(i) > V(j) Then           tun = 1: abi = V(i)           V(i) = V(j): V(j) = abi        End If     Next i  Loop End Sub