Ohjelmoinnin peruskäsitteet:

Luku A
Korttiprosessori

  1. Mikä on korttiprosessori?
  2. Korttien vaihtaminen muuttujien välillä
  3. Kolmen kortin järjestäminen
  4. Taulukot ja korttien tutkiminen
  5. Pienimmän kortin etsintä
  6. Valintalajittelu

1. Mikä on korttiprosessori?

Käytämme korttiprosessoria demonstroimaan tietokoneohjelmointia. Korttiprosessori tarkoittaa yksinkertaisesti sitä, että opiskelija hakee käyttöönsä korttipakan (tai kaksi) ja järjestelee niitä tiukkojen sääntöjen mukaan pöydällä. Tällä tavalla on mahdollista kokeilla yksinkertaisia algoritmeja eli toimintaohjeita, joista kokonainen tietokoneohjelma koostuu.

Kortin saa asettaa pöydälle vain muuttujaan. Muuttuja on kortin talletuspaikka, joka osoitetaan nurin käännetyllä kortilla. Tässä muuttujille on annettu myös nimi, joka lukee kortin yläpuolella. Muuttuja voi olla joko tyhjä, kätketty tai paljastettu (alla A, B ja C):

ABC
Kortti A, B, C;

Korttien oikealle puolelle on kirjoitettu myös Java-ohjelmointikielinen koodi, joka vastaa suurinpiirtein korteilla tehtyä operaatiota. Siihen ei kuitenkaan aluksi tarvitse kiinnittää huomiota, tärkeintä on keskittyä itse operaatioihin.

Korttiprosessorin toimintaa ohjataan tiukoilla säännöillä. Sääntöjen tarkoituksena on matkia tietokoneen rajoituksia. Säännöt ovat:

  1. Kortti voi sijaita vain muuttujassa.
  2. Kortteja voi siirtää muuttujasta toiseen, mutta vain yhden kerrallaan.
  3. Vain kaksi kappaletta (tai ennalta päätetty hieman suurempi lukumäärä) kortteja saa olla paljastettuna kerrallaan. Erityisesti vertailuja saa tehdä vain kahdelle kortille.
  4. Jos aikaisempi algoritmi ratkaisee osan uudesta algoritmista, sitä saa käyttää oikotienä.

Kohta 3 on säännöistä sellainen, jota tulee algoritmeissa rikkoneeksi helposti. Alla olevissa algoritmien kuvauksessakin on usein paljastettuna enemmän kuin kaksi korttia. Ollennaisinta on kuitenkin se, että algoritmeissa paljastettujen korttien lukumäärä on vakio ja ennalta määrätty. Jos näin ei ole, korttiprosessori ei muistuta tietokonetta eikä algoritmi toimi tietokoneohjelman algoritmina..

2. Korttien vaihtaminen muuttujien välillä

Ensimmäinen korttiprosessorilla suoritettava algoritmi vaihtaa kahden muuttujan kortit keskenään. Tämä algoritmi on erityisen hyödyllinen ym. säännön 4. sovelluksena. Voimme viitata tähän algoritmiin aina, kun monimutkaisemmassa algoritmissa pitää vaihtaa kahden kortin paikat keskenään.

Aluksi luodaan kaksi korttimuuttujaa.

AB
Kortti A, B;

Sijoitetaan muuttujiin kortit. Tässä patakuningas ja ruutunelonen. Vaihtaminen tehdään kuitenkin ilman erityistä tietoa muuttujien sisällöstä.

AB
A = "patakuningas";
B = "ruutunelonen";

Vaihtaminen ei onnistu ilman kolmatta muuttujaa, koska samassa muuttujassa saa olla vain yksi kortti, eikä kortteja saa siirrellä kuin yhden kerrallaan.

ABSiirto
Kortti Siirto;

Siirretään kortit niin, että asetetaan ensin toisen muuttujan kortti talteen apumuuttujaan Siirto. Tämän jälkeen algoritmi on varsin suoraviivainen.

ABSiirto
Siirto = A;
A = B;
B = Siirto;

3. Kolmen kortin järjestäminen

Kolmen kortin järjestämisessä voimme käyttää yllä esitettyä vaihto-operaatiota. Kutsumme operaatiota funktioksi nimeltä vaihda

Aluksi meillä on kolme muuttujaa, joiden sisältöä emme tunne.

ABC
Kortti A, B, C;
A = ?;
B = ?;
C = ?;

Paljastamme kaksi ensimmäistä korttia ja vertailemme niitä keskenään. Kortit ovat jo järjestyksessä, joten vaihtoa ei tapahdu. Tämän osoitamme koodissa kirjoittamalla sen harmaalla.

ABC
if (A > B) {
  vaihda(A, B);
}

Paljastamme kaksi viimeistä korttia ja vertailemme niitä keskenään. Nyt vaihto tapahtuu ja siinä käytämme funktiota vaihda

ABC
if (B > C) {
  vaihda(B, C);
}

Korttiprosessori ei voi vielä tässä vaiheessa tietää, ovatko kortit järjestyksessä (sitäpaitsi eivät ole), koska vain paljastettuja kortteja voi käyttää päättelyssä. Siksi joudumme paljastamaan vielä uudestaan kaksi ensimmäistä korttia, vertailemaan ja myös vaihtamaan.

ABC
if (A > B) {
  vaihda(A, B);
}

Nyt voimme olla varmoja, että kortit ovat järjestyksessä ja voimme jatkaa eteenpäin.

Tehtävä A1: Kokeile korttiprosessoria neljän kortin lajittelussa. Onko siinä jo havaittavissa yleinen kaava korttien lajitteluun? Mikä se on?

4. Taulukot ja korttien tutkiminen

Korttien nimeäminen omilla nimillään tulee hyvin epäkäytännölliseksi jo siinä tapauksessa, että yhteen kuuluvia (esimerkiksi lajiteltavia) kortteja on neljä kappaletta tai enemmän. Sen vuoksi korttiprosessorissa on käytettävissä rakenne nimeltä taulukko. Taulukko on kokoelma muuttujia, joilla on yhteinen nimi ja joihin viitataan järjestysnumeron (indeksin avulla)

T[1]T[2]T[3]T[4]T[5]
Kortti[] T = new Kortti[5];

Taulukon läpikäynti

Taulukon kortin voi paljastaa nimen ja indeksin avulla. Taulukon kaikkien korttien tutkimisessa tarvitaan apumuuttuja, johon talletetaan viimeisimmän tutkitun taulukon indeksi. Käytämme taulukon indekseinä tässä patoja, taulukon sisällöksi laitamme herttoja.

IT[1]T[2]T[3]T[4]T[5]
Pata I = "pataässä";
Hertta[] T = new Hertta[5];

Koska indeksimuuttujan I arvona on "yksi" (eli ässä), voimme paljastaa taulukon kortin, jonka indeksi on 1. Tämän jälkeen kasvatamme indeksimuuttujan arvoa yhdellä kakkoseksi, ja paljastamme kortin indeksillä 2, ...

IT[1]T[2]T[3]T[4]T[5]
while (I <= 5) {
  // paljasta T[I]
  I = I + 1;
}

5. Pienimmän kortin etsintä

Edellisen taulukon läpikäyntiesimerkin pohjalta on helppo tehdä algoritmi, joka etsii taulukon (numeroarvoltaan) pienimmän kortin. Tarvitsemme edellisten muuttujien lisäksi muuttujan, johon talletetaan pienin. Alussa oletamme, että ensimmäinen on pienin. Huomaa, että esimerkin toteutukseen tarvittaisiin kaksi pakkaa paitsi, jos käyttäisimme muuttujassa Pienin numeroarvoltaan samanlaisia ruutuja tai ristejä.

PieninIT[1]T[2]T[3]T[4]T[5]
Pata I = "pataässä";
Hertta[] T = new Hertta[5];
Hertta Pienin = T[I];

Nyt voimme käydä lopputaulukon läpi aloittamalla indeksistä 2. Jokaista taulukon korttia verrataan muuttujan Pienin sisältöön. Jos taulukon kortti on pienempi kuin muuttujan Pienin sisältämä, kopioidaan kortti taulukosta muuttujaan.

Huomaa, että käytämme tässä kopiointia, mutta merkitsemme sen samalla tavalla (Pienin = T[I]) kuin vaihtoesimerkissä siirron (A = B). Ohjelmointikielissä muuttujien välillä tehdään nimenomaan kopiointia, ei siirtoja. Useissa algoritmeissa tällä ei kuitenkaan ole väliä, koska siirron lähteenä olevan muuttujan arvolla ei ole merkitystä siirron jälkeen. Tässä emme kuitenkaan halua poistaa taulukosta kortteja etsinnän tuloksena.

PieninIT[1]T[2]T[3]T[4]T[5]
I = I + 1;
while (I <= 5) {
  if (T[I] < Pienin)
    Pienin = T[I];
  I = I + 1;
}

Edellisen jälkeen muuttujan Pienin arvoksi jää "kolme", joka on taulukon pienimmän kortin numeroarvo. Samalla tavalla toteutetaan helposti suurimman kortin tai jonkin tietyn kortin etsintä. On tärkeää huomata, että vaikka algoritmi onkin tässä esitetty taulukolla, jonka koko on 5, niin se toimii minkä tahansa kokoisella taulukolla samalla tavalla.

Tehtävä A2: Tee korttiprosessorilla taulukosta etsintä, jonka tuloksena löytyy taulukon pienimmän alkion indeksi. Indeksi talletetaan omaan muuttujaansa.

Tehtävä A3: Muuta pienimmän alkion etsintää niin, että se rajoittuu taulukossa annetulle välille. Väli annetaan muuttujissa Min ja Max.

6. Valintalajittelu

Nyt voimme olettaa, että meillä on käytettävissä funktio etsi_pienin, jolle kerrotaan väli, josta etsintä tehdään. Tämän funktion (ja funktion vaihda) avulla on varsin suoraviivaista tehdä algoritmi, jolla korttiprosessori saa taulukon järjestykseen.

Ideana tässä valintalajitteluksi kutsutussa algoritmissa on asettaa kortit oikeille paikoilleen yksi kerrallaan. Taulukon kohtaan I etsitään aina pienin alkio väliltä I - viimeinen kortti. Aloitamme alkutilanteesta, jossa meillä on vain taulukko paljastamattomia kortteja ja kaksi algoritmissa tarvittavaa apumuuttujaa: I taulukon läpikäyntiin ja Pienin tallettamaan pienimmän kortin paikka. Tarvitsemme taas kaksi pakkaa tai voimme käyttää pienimmän paikan esittämiseen vaikkapa ristejä.

Tämän algoritmin kuvauksessa näytämme yhtä aikaa jopa neljä korttia. Tämä ei kuitenkaan tarkoita sitä, että rikkoisimme korttiprosessorin sääntöjä. Emme vertaile enempää kuin kahta korttia kerrallaan. Ylimääräisiä kortteja tarvitsemme taulukkoon viittaamiseen, mikä sallitaan, koska paljastettujen korttien määrä tiedetään ennalta.

IPieninT[1]T[2]T[3]T[4]T[5]
Pata I = "pataässä";
Hertta[] T = new Hertta[5];
// täytä taulukko
Pata Pienin;

Aloitamme ensimmäisen vaiheen etsimällä pienimmän kortin koko taulukosta. Vaihdamme sen taulukon ensimmäiseksi Jatkamme kasvattamalla indeksiä I yhdellä, etsimme taas pienimmän kortin lopputaulukosta ja vaihdamme sen taulukkoon paikkaan I. Eli vuoronperään: etsi, vaihda, etsi, vaihda, ...

IPieninT[1]T[2]T[3]T[4]T[5]
while (I < 5) {
  Pienin = etsi_pienin(I, 5);
  vaihda(T[I], T[Pienin]);
  I = I + 1;
}

Koska algoritmi toimii, luotamme siihen, että kortit ovat nyt järjestyksessä. ... Katsotaan kuitenkin:

IPieninT[1]T[2]T[3]T[4]T[5]

Tehtävä A4: Tehokkaampi lajittelu saadaan aikaiseksi vertailemalla ja tarpeen mukaan vaihtamalla taulukossa vain peräkkäisiä kortteja. Tässä tapauksessa yhdellä kierroksella saadaan varmasti paikoilleen yksi kortti (kuten valintalajittelussa), mutta muut kortit ovat myös hieman paremmassa järjestyksessä.. Tee korttiprosessorilla tällainen niinsanottu kuplalajittelu.

Jarkko Leponiemi