Keskustelu: Ohjelmointikysymykset: C++ Taulukon "täyttäminen"

Miten saa ns. täytettyä taulukkoa, jonka koko arvotaan. Eli siis jos arvon satunnaisluvuksi esim 42, tulee taulukko[42]={0}. Tähän asti pääsen ongelmitta.

Seuraavaksi pitäisi saada "täytettyä" taulukkoa satunnaisesti, eli ohjelma arpoo taulukon jäsenen ja ko. alkio muuttuu nollasta 1:ksi. Arvontaa voidaan suorittaa, kunnes kaikki alkiot ovat 1, eli samaa alkiota ei voi kahdesti arpoa. Silloin taulukko on täynnä.

Tuo arpomisen osuus menee, mutta miten saan sijoitettua alkioon +1 ja rajaamaan arvonnan tuloksen aina niihin jäseniin, jotka ovat vielä 0?

Taulukon alkioon voidaan sijoittaa arvo sijoitusoperaattorilla '='.

int main() {
	int luvut[42] = {0};

	//Sijoitetaan 11. alkion arvoksi luku 1.
	luvut[10] = 1;
}

Arvonta itsessään on helppoa. Arvot silmukassa lukuja väliltä 0 - 41 ja sijoitat arvoksi luvun 1. Arvonnan jälkeen tarkistat onko kaikkien alkioiden arvo 1. Jos on voit lopettaa ja jos ei ole, niin pitää jatkaa.

Yksi vaihtoehto on se, että if-lauseella arvonnan jälkeen katsoisit, onko kyseisessä kohdassa jo ennestään 1. Silloin on aina riski, että viimeisiin lukuihin osuminen vaatii monta yritystä, mutta pienellä taulukolla tämä ei ole yleensä ongelma.

Toinen vaihtoehto on pitää kirjaa, montako vapaata kohtaa vielä on. Tällöin voi arpoa aina varmasti vapaan kohdan, mutta oikea kohta pitää etsiä silmukalla (eli silmukassa lasketaan vapaita kohtia ja laitetaan ykkönen, kun löytyy sille arvottu paikka). Tämä ratkaisu käy hitaaksi, jos taulukko on kovin suuri. Toisaalta tähän voi siirtyä vaikka sitten, kun edellinen ratkaisu alkaa tuottaa liikaa törmäyksiä.

Kolmas vaihtoehto on pitää kirjaa kaikista vapaista kohdista. Arvonta löytää siis aina varmasti vapaan kohdan, ja se poistetaan vapaiden listasta. (Tai vapaiden listan voi vain sekoittaa ja ottaa sieltä järjestyksessä indeksejä.) Tässä huono puoli on tilankäyttö, eli tarvitaan toinen kokonainen taulukko.

Neljäs vaihtoehto on, että törmäystilanteessa vain etsitään järjestyksessä seuraava vapaa kohta. Tämän ratkaisun heikkous on epätasainen satunnaisjakauma: esimerkiksi kun taulukosta on yksi paikka täytetty, on kaksinkertainen todennäköisyys, että seuraavaksi täytetään viereinen kohta.

Muuttuuko käytettävissä olevat vaihtoehdot, jos aina arvonnan jälkeen koko ohjelma ajetaan loppuun, jonka jälkeen sen voi aloittaa alusta? Silloin siis pitäisi aina jäädä muistiin, mitkä taulukon paikat on jo täytetty.

Sain arvonnan ja sijoituksen toimimaan jo yksittäiselle kierrokselle, mutta tuota täyteen saamista pitää vielä miettiä. Olen tosiaan niin vasta-alkaja ohjelmoinnissa, että monimutkaisemmat jutut vaatii viikon miettimistä.

cshele kirjoitti:

Muuttuuko käytettävissä olevat vaihtoehdot, jos aina arvonnan jälkeen koko ohjelma ajetaan loppuun, jonka jälkeen sen voi aloittaa alusta?

Ratkaisuvaihtoehdot eivät muutu. Kuten Teuro yllä esitti, ratkaisusta riippumatta koodissasi on jossain kohti rivi, jossa asetat taulukon oikeaan kohtaan ykkösen. Siinä vaiheessa voit ajaa mitä tahansa muutakin, vaikka sellaisen ”koko ohjelma” -nimisen osan ohjelmaa.

Käytännössä ratkaisutavasta riippumatta koodi on tällainen:

const int koko = 42;
int vapaita = koko;
int taulukko[koko] = {0};
while (vapaita) {
  // Valitaan seuraava paikka jollain edellä kuvatuista ratkaisuista.
  int paikka = arvo_seuraava_paikka();

  // Jos paikka ei ole vapaa, yritetään uudestaan.
  if (taulukko[paikka]) {
    continue;
  }

  // Täytetään paikka ja päivitetään laskuria.
  taulukko[paikka] = 1;
  vapaita -= 1;

  nyt_ajetaan_ns_koko_ohjelma();

  // Jos ei ole vapaita, pitää lopettaa joka tapauksessa.
  if (!vapaita) {
    break;
  }
  // Muuten voit esim. kysyä käyttäjältä, haluaako hän jo lopettaa.
}

Jos tätä koittaisi ratkaista tosi isolle taulukolle, niin tulisi mieleen käyttää Metabolixin esittämistä vaihtoehdoista vaihtoehtoja 1 ja 3 ja vaihtaa 1:stä kolmoseen jossain sopivassa kohdassa, tyyliin kun 90% luvuista on arvottu menetelmällä 1. Tässä olisi sekin etu että tarvittava aputaulukko olisi vain esim. 10% arvottavan taulukon koosta.

Metabolixhan ehdottikin menetelmän vaihtoa lennossa, mutta 1->2 jossa mielestäni ei ole järkeä.

Toisaalta ajattelisin että isoille taulukoille pelkkä 3 on myös erittäin toimiva strategia eikä vaadi kuin tuplamäärän muistia.