previous next Up Title Contents Index

"Paras" ratkaisu:

Molemmat mainitut ongelmat voidaan kiertää ottamalla käyttöön 40-alkioinen taulukko, jossa kutakin mahdollista numeroa kohti varataan yksi alkio:

Taulukon indeksi ilmaisee suoraan, mistä numerosta on kyse.
Kun tietty numero arvotaan, taulukkoon merkitään numeron ilmoittamaan lokeroon tieto siitä, että numero on arvottu.
Kun pitää tutkia, onko tietty numero arvottu, tutkitaan vain numeron ilmoittaman alkion sisältö.
Arvotut numerot voidaan tulostaa helposti suuruusjärjestyksessä käymällä taulukko läpi alusta alkaen ja tulostamalla niiden alkioiden indeksit, joissa on merkintä luvun arpomisesta.

Huomaa, että varsinaiset numerot ja lisänumerot voidaan merkitä samaan taulukkoon käyttämällä erilaisia merkintöjä (esim. varsinaiselle numerolle 1 ja lisänumerolle 2).

Numeroiden tulostusvaiheessa taulukko käydään läpi kahteen kertaan: ensimmäisellä läpikäynnillä tulostetaan varsinaiset numerot ja toisella lisänumerot.

Koska taulukon jokainen alkio ei tässä ratkaisussa ole aktiivisessa käytössä (taulukossa on 10 merkintää 40 lokerossa), taulukkoa voidaan kutsua nimellä "harva taulukko".

Ratkaisun haittapuolena on se, että kymmenen luvun tallettamiseksi tarvitaan paikat 40 luvulle, mutta tällaista muistin tuhlausta ei tässä yhteydessä voitane pitää kohtuuttomana.

previous next Up Title Contents Index