58127 C-ohjelmointi - Harjoitustyö

Ohjeet harjoitustyön tekemiseen

Harjoitustyö suostitellaan tehtäväksi ryhmässä (2-3 henkilöä). Työstä palautetaan lisäksi selvitys osallistujen osuudesta työhön. Ryhmätöiltä edellytetään, että niissä on myös testimoduuli tietorakennemoduuleille.

Aiheet

1. Järjestämisalgoritmeja

   Tee ohjelma, joka järjestää kokonaislukuja. Valitse kolme järjestysalgoritmia (esim. seuraavista valinta-, lisäys-, pika-, kupla- keko- ja lomitusjärjestäminen). Tee ohjelmalle menu, jonka avulla käyttäjä voi valita järjestysalgoritmin, muuttaa syöttö- ja tulostustiedostoja, poistua ohjelmasta jne. Normaalisti tuloksena on järjestetty data kirjoitettuna annettuun tiedostoon. Lisäksi menussa tulee olla valinta, jonka ollessa päällä tulostetaan aika joka tietyltä järjestämisalgoritmilta kului datan prosessoimiseen tiedostoon järjestettynä.

2. Ckone: ttk-91 simulaattori

   Ckone simuloi ttk-91 arkkitehtuurin suoritusta ja sillä saadaan samat lopputulokset kuin esim. Titokoneella. Ckoneessa ei ole Titokoneen debugger ympäristöä, assembleria, animaattoria ta graafista käyttöliittymää. Ckoneessa on lataaja.

   Titokone tuottaa yksinkertaistettua "binääriä" (tiedostotyyppi .b91), jossa kukin konekäsky on esitetty kokonaislukuna. Tämä on syötetiedosto Ckoneelle. Katso esimerkkiä alla. Omista ttk-91 ohjelmista saa Ckoneen syötetiedostoja kääntämällä ne Titokoneella.

   Simuloinnin lopuksi vedostetaan muisti ja rekisterit, josta näkee osaltaan ohjelman toimivuuden.

   Lopputulosta voi myös vertailla Titokoneella saatuun tulokseen.

   -- lähdekoodi ---
   ; sum - laske annettuja lukuja yhteen kunnes nolla annettu
   Luku DC 0 ; nykyinen luku
   Summa DC 0 ; nykyinen summa
   Sum IN R1, =KBD ; ohjelma alkaa käskystä 0
   STORE R1, Luku
   JZER R1, Done ; luvut loppu?
   LOAD R1, Summa ; Summa <- Summa+Luku
   ADD R1, Luku
   STORE R1, Summa ; summa muuttujassa, ei rekisterissa?
   JUMP Sum
   Done LOAD R1, Summa ; tulosta summa ja lopeta
   OUT R1, =CRT
   SVC SP, =HALT
   
   -- titokoneen tuottama "binääri"
   ___b91___
   ___code___
   0 9
   52428801
   18874378
   572522503
   36175883
   287834122
   18874379
   536870912
   36175883
   69206016
   1891631115
   ___data___
   10 11
   0
   0
   ___symboltable___
   sum 0
   summa 11
   kbd 1
   done 7
   halt 11
   crt 0
   luku 10
   ___end___
   
   

3. Levyn skedulointialgoritmien vertailua:

   Tee ohjelma, jonka avulla voit vertailla levyn skedulointialgoritmeja: puhdas jono (FIFO, First-Come-First-server), lyhin siirtymä (SSF, Shortest-Seek-First) ja hissi (elevator, SCAN). Kukin algoritmi käsittelee saapuvia levypyyntöjä oman poliitiikkansa mukaan.

   Ohjelma lukee palvelupyynnöt (urien numeroita ym.) komentoparametrina annetusta tiedostosta. Jos tiedostoa ei ole, niin ohjelma generoi palvelupyyntöjen jonon. Pyyntöjono talletetaan tiedostoon, jotta vertailu voidaan tehdä uudelleen.

   Palvelypyyntö koostuu pyynnön saapumisajasta millisekuntteina ja uran numerosta. Komentoriviparametrina annetaan myös hakuvarren siirtoaika kahden vierekkäisen uran välillä (esim. 1 ms). Palveluajan voit olettaa olevan, jollain aikavälillä tai voit käyttää jotain sopivaa jakaumaa palveluaikojen generoimiseen.

   Ohjelman tulostaa kuinka monen uran yli kukin algoritmi siirtyi. Lisäksi tulostetaan kunkin algoritmin keskimääräinen palveluaika.

4. Reaali-aika prosessien skedulointi (vuorotus):

   Tee ohjelma, jonka avulla voit simuloida RM (rate-monotonic) ja EDF (earliest deadline first) vuorotusmenetelmien toimintaa. Ohjelman syöte on komentoriviparametrina annettava tiedosto. Tiedostossa on useita rivejä. Kukin rivi kuvaa yhden toistuvan prosessin ominaisuuksia: jakson pituus, laskenta-aika, aloitusaika ja lopetusaika. Aloitus- ja lopetusajat tarvitaan vain, jos ne poikkevat jakson alusta tai lopusta. Aikojen voit ajatella olevan sekunteja, millisekunteja, minuutteja tai tunteja. (Ne voivat olla desimaalilukuja).

   Simulointisi täytyy kestää kokonaisen hyperperiodin ajan. Hyperperiodi on jaksonpituuksien pienin yhteinen jaettava. Tätä voi yksinkertaistaa simuloimalla koko periodien tulon ajan. Tällöin olet simuloinut vähintään yhden hyperperiodin.

   Algoritmien vertailua varten ohjelma tulostaa: keskimääräisen CPUn käyttöasteen, keskimääräisen CPU-odotusajan, keskimääräisen jononpituuden ja keskimääräisten myöhästyneiden lukumäärän.

5. Salaiset viestit

   Tee ohjelma, jolla voidaan koodata salaisia viestejä kuviin (bitmap). Tee toinen ohjelma, jolla viestit voidaan purkaa kuvista. Koodatessa muuta tarvittaessa jokaisen tavun vähitenmerkitsevä bitti tallettaaksesi tietoa viestistä. Purkaessa muodosta salainen viesti tavujen vähitenmerkitsevistä biteistä. Laske kuinka monta bittiä todella muutit kuvatiedostossa ja tulosta käyttäjälle tämä tieto.

   Anna komentoriviparametrina ainakin kuvatiedostot.

6. Yksinkertainen laskin

   Toteuta yksinkertainen laskin, joka lukee yhden lausekkeen yhdeltä riviltä. Rivin voi syöttää ohjelmalle joko tiedostosta tai näppäimistöltä.

   Laskutoimituksen lausekkeen voi kuvata joko tavanomaisesti kuten (15 *3 ) /7 + 5 *8 - 12324 % 10

   Tai käyttäen ns. käänteistä puolalaista notaatiota, jolloin em. kuvaus olisi 15 3 * 7 / 5 8 * + 12324 10 % -

   Toteuta ohjelmasi siten, että käytät pinoa apuna laskutoimituksessa. Tallenna välitulokset pinoon. Tuo käänteinen puolalainen laskutoimitus on helpompi toteuttaa. Harjoituksen vuoksi pinon toteutuksen pitää käyttää osoittimia ja dynaamisuutta. Katso tietorakenteiden kurssilta pinon perusoperaatiot ja toteuta ne osaksi ohjelmaasi.

   Käyttäjän pitää voida halutessaan antaa operaatiot sisältävän tiedoston nimi komentoriviparametrina.

7. Sana- ja virkelaskuri

   Tee ohjelma, joka lukee yhden tekstitiedoston. Käyttäjän pitää voida valita tiedoston syöttötapa. Hän voi joko antaa tiedoston nimen komentoriviparametrina tai ohjelma voi olettaa tiedon tulevan stdin-tiedostosta.

   Ohjelman pitää tulostaa tiedostosta löytyneet sanat (vähintään kaksi peräkkäistä kirjainmerkkiä) ja niiden esiintymisten lukumäärät. Kukin sana ja sen esiintymisten lukumäärä tulostetaan omalle rivilleen. Lisäksi tulostetaan kuinka monta virkettä esiintyi tekstissä ja jakauma siitä miten monta sanaa virkkeisiin kuului. Tulostiedoston nimi käsitellään samoin kuin syöttötiedoston.

   Käytä ratkaisussasi tietorakenteena tasapainotettua binääripuuta.

8. Kaupan kassan simulointi

   Tee ohjelma, joka simuloi (eli jäljittelee) kaupan kassan toimintaa. Kassalle saapuu asiakkaita ja meillä on vain yksi kassapiste, johon asiakkaat joutuvat jonottamaan. Kun piste vapautuu, siirtyy seuraava jonottaja palveltavaksi.

   Voit aluksi olettaa että asiakkaiden kassalle saapumisten väli vaihtelee satunnaisesti 1 ja 4 minuutin välillä. Samoin asiakkaiden palveluaika kassalla vaihtelee 1 ja 4 minuutin välillä. Varaudu kuitenkin muuttamaan tuota vaihteluväliä (molemmista päistä).

   Simulointi tapahtuu seuraavasti: Arvotaan ensimmäisen asiakkaan saapumisaika ja laitetaan tämä asiakas jonoon. Tapahtumajonossa ovat kaikki tapahtumat (asiakas saapui jonoon, asiakas poistui kassalta) niiden aikajärjestyksessä. Jonosta otetaan aina ensimmäinen tapahtuma (ja aika eteni siihen kohtaan) 1) asiakas saapui - laita asiakas palvelujonoon - arvo seuraavan asiakkaan saapusaika ja laita tämä tieto tapahtumajonoon 2) asiakas poistui kassalta - ota palvelujonosta ensimmäinen jonottaja - arvo palvelunkesto ja sijoita asiakkaan poistumishetki tapahtumajonoon

   Ohjelmasi pitää tulostaa kaikki tapahtumat ja niiden ajankohdat tiedostoon. Lisäksi simulaattorit keräävät kaikenlaista tilastotietoa, joten ohjelman pitää myös raportoida: palvelupisteen käyttöaste (palveluajat yhteensä / kokonaisaika), keskimääräinen jonotusaika (jonotusaikojen summa / jonottajien lkm), pisin hetkellinen jononpituus, pisin jonotusaika.

   Varaudu ohjelmassasi siihen, että palvelupisteitä voidaan lisätä ja että asiakkaiden saapumisaikojen ja palveluaikojen jakaumia (tai ainakin vaihteluväliä) voidaan vaihtaa esimerkiksi komentoriviparametreilla.

   Käytä toteutuksessasi dynaamista jonotietorakennetta ja sen perusoperaatioita. Jonon voi toteuttaa esimerkiksi linkitettynä listana.

9. Lennon varausjärjestelmä

   Lentoyhtiö FlyCheap on juuri aloittamassa toimintaansa ja se tarvitsee asiakaspalveluaan varten lennonvarausjärjestelmän, jolla asiakaspalvelijat (tai asiakkaat itse) voivat varata lentoja.

   Yhtiöllä on vain kolme konetta ja kaksi reittiä, joita ne lentävät korkeintaan kolme kertaa päivässä. Kuhunkin koneeseen mahtuu korkeintaan 30 matkustajaa. Tee yhtiölle yksinkertainen ohjelma, jossa voidaan varata paikka nimetylle matkustajalle tietylle reitille ja lähtöajalle. Kalenterisi voi kattaa esimerkiksi kolme päivää, yhden viikon tai kokonaisen kuukauden. Oikeita päivämääriä ei ole välttämätöntä käyttää. Matkustajan pitää voida myös ottaa kantaa paikkanumeroonsa. Ohjelmasi pitää siis pitää kirjaa lentokoneiden varaustilanteesta. Tiedot pitää myös pitää tallessa ohjelman suorituskertojen välillä.

   Yhtiö on erityisen kiinnostunut palvelemaan jo olemassa olevia asiakkaitaan tehokkaasti, joten toteuta järjestelmääsi erittäin nopea (esim. binääripuu) talletusrakenne matkustajakohtaisille tiedoille. Ohjelman pitää siis nopeasti voida tulostaa tietyn matkustajan kaikki varaukset. Sen sijaan yksittäisen vuoron vapaiden paikkojen etsimiseen voi käyttää hiukan enemmän aikaa, jos et keksi hyvää tietorakenneratkaisua.

   Käytä järjestelmäsi toteuttamiseen dynaamisia tietorakenteita, jotta yhtiö voi halutessaan helposti kasvattaa lentokoneiden kokoa ilman, että ohjelmistoasi tarvitsee vaihtaa. Voit esimerkiksi ottaa nuo rajat komentoriviparametreina, jolloin ne ovat suorituskerroittain vaihdettavissa ilman käännöstä.

10. Työntekijärekisteri

    Tee ohjelma, joka pitää kirjaa yrityksen työntekijöistä. Voit olettaa, että henkilöiden nimissä on vain kirjaimia ja että yrityksen palkkalistoilla ei ole kahta samannimistä henkilöä. Rekisterissä on työntekijöiden nimien lisäksi heidän palkkansa ja aloitusvuosi.

    Ohjelmasi pitää tarjota seuraavat toiminnot:

    • - työntekijän lisäys rekisteriin. Jos rekisterissä on jo saman niminen, niin lisäystä ei tehdä ja käyttäjää varoitetaan asiasta.
    • - työntekijän poistaminen rekisteristä. Jos työntekijää ei löydy, niin varoita käyttäjää, mutta älä lopeta ohjelman toimintaa tähän.
    • - työntekijän etsintä nimellä. Tulosta käyttäjälle palkka ja aloitusvuosi.
    • - työntekijöiden tietojen talletus tekstitiedostoon
    • - tietojen luku tekstitiedostosta.
    • - lopetus. Jos muutoksia ei ole tallennettu, niin varmista käyttäjältä ja tee tarvittaessa tallennus.

    Käytä ratkaisussasi hajautustaulua työntekijän nimen mukaan.

11. Ravintolan simulointi

    Toteuta jonorakenne käyttämällä linkitettyjä listoja. (Vain taulukkoa käyttäviä ratkaisuja ei hyväksytä.) Tee rakenteen avulla ohjelma, joka simuloi ravintolan toimintaa seuraavasti:

    Ravintolassa on ruokalista, jolta asiakas voi tilata haluamansa ruuan. Jokaiselle ruualla on oma valmistusaikansa. Ruokalistan voit lukea vaikkapa tiedostosta. Ravintolassa on neljä kokkia, joista jokainen voi valmistaa kerrallaan kahta eri ruokalajia. Salli ainakin kokkien määrän vaihtaminen komentoriviparametrina.

    Kun asiakas tilaa ruuan, hänen tilauksensa sijoitetaan tilausjonon viimeiseksi. Kun joku kokeista vapautuu (hänellä on valmistettavanaan enää yksi tai ei yhtään ruokaa), hän ottaa valmistettavakseen tilausjonon ensimmäisen tilauksen, joka tällöin poistetaan jonosta.

    Ohjelman käyttäjä antaa uusia tilauksia ja voi sopivalla käskyllä kasvattaa simulointijärjestelmän kelloa esim. yhdellä minuutilla kerrallaan. Ohjelma kertoo, milloin kukin ruokalaji on valmistunut.

    Katso simuloinnin ohjeita myös tehtävästä Kaupan kassan simulointi.

12. Sukupuu

    Tee ohjelma, jonka avulla käyttäjä voi tallentaa sukupuun. Sukupuuhun voi tallettaa tietoja henkilöistä (nimi, syntymäaika, kuolinaika), näiden välisistä suhteista (sekä viralliset avioliitot että epäviralliset suhteet - jälkimmäiset halutaan tallettaa esim. sen vuoksi, että voidaan helposti pitää kirjaa lasten vanhemmista) ja suhteista syntyneistä lapsista. Yksinkertaisuuden vuoksi voit tehdä järjestelmän sellaiseksi, että jokaisella henkilöllä on eri nimi.

    Ohjelmasi pitää tarjota ainakin seuraavat toiminnot:

    • henkilön lisäys (henkilö voidaan lisätä joko "itsenäisenä" tai joidenkin lapsena)
    • henkilön tietojen muutos
    • suhteen lisäys
    • annetun henkilön kaikkien jälkeläisten tulostus
    • annetun henkilön kaikkien esivanhempien tulostus
    • annetun henkilön kaikkien rekisteröityjen suhteiden tulostus.
    Ohjelmasi voi luottaa syötettyjen tietojen järkevyyteen. Sen ei tarvitse esim. tarkistaa, että joku ei ole naimisissa kahden henkilön kanssa yhtä aikaa tai että jonkun lapsi ei ole vanhempi kuin henkilö itse.

    Ohjelmasi täytyy käyttää dynaamista muistinvarausta - vain taulukoihin perustuvia ratkaisuja ei hyväksytä.

13. Kokkaavan ystävän apu

    Ystäväsi on päättänyt ryhtyä mestarikokiksi, mutta hänellä on jatkuvasti ongelmia ruoka-aineiden suhteen. Niinpä sunnuntain lasagne-ateria muuttui tonnikalavoileiviksi, kun kaapissa ei ollutkaan jauhelihaa. Tällaista linjaahan ei kukaan kestä kovin pitkään. Kirjoita siis ohjelma, jonka avulla ystäväsi voi tallettaa reseptejä ja ruoka-aineita, sekä tarkastaa paljonko jotain ruoka-ainetta on jäljellä. Ohjelman käyttöliittymä voi olla rivipohjainen, mitään koko ruudun täyttäviä valikkosysteemiä ei tarvita.

    Tietorakenneratkaisun pitää pohjautua dynaamiseen muistinvaraukseen ja osoittimien käyttöön. Puhdasta taulukkototeutusta ei hyväksytä.

14. Rastilla käyneet suunnistajat

    Suunnistuskilpailuissa sama rasti voi olla käytössä useilla eri radoilla. Tehtävänä on selvittää ketkä suunnistajista ovat käyneet tietyllä rastilla ja missä järjestyksessä. Tuloksena annetaan suunnistajat rastillakäyntijärjestyksessä. Lisäksi rastilla käyneen suunnistajan nimen lisäksi kerrotaan aika, jolloin suunnistaja kävi kyseisellä rastilla. Ohjelmalle annetaan seuraavat tiedostot:
    • Suunnistajien lähtöajat (esim. sarja07.html)
    • Eri sarjojen radat (esim. radat07.lst)
    • Väliajat, josta ilmenee sarjoittain tilanne rasteilla ja rastivälien ajat (esim. vali07.html)
    Tiedostot ja rastinkoodin ohjelma saa komentoriviparametreina.

15. Lämmönjohtuminen

    Stationaarisen tilan lämmönjohtumisyhtälö kahdessa ulottuvuudessa on
    d²T(x,y) /dx² + d²T(x,y)/dy² = 0.

    Sen ratkaisu antaa lämpötilan tasapainojakauman mielivaltaisessa kaksiulotteisessa kappaleessa, kun reuna-ehdot on tunnettu. Yhtälön voi ratkaista numeerisesti hyvin yksinkertaisesti seuraavalla tavalla. Jaa haluttu tila neliölliseen hilaan. Tee mikä tahansa arvaus ratkaisulle T⁰(x,y), missä x ja y ovat nyt diskreettejä pisteitä neliöllisessä hilassa. Sen jälkeen iteroi ratkaisua siten, että jokaisessa pisteessä uuden iteraatio-askeleen i+1 uusi arvo Tⁱ⁺¹ lasketaan kaavalla

    Tⁱ⁺¹(x,y) = 1/4 (Tⁱ(x+1,y) + Tⁱ(x-1,y) + Tⁱ(x,y+1) + Tⁱ(x,y-1)

    eli yksinkertaisesti keskiarvona neljän lähimmän naapuripisteen lämpötilasta edellisellä iteraatio-askeleella. Kirjoita ohjelma, joka ratkaisee lämmönjohtumisyhtälön kahdessa ulottuvuudessa suorakulmaisessa kappaleessa, jonka korkeus on 2 m ja leveys 1 m. Suorakulmion pohjalla ja sivuilla lämpötila on 1000 K, mutta sen yläreunalla 0 K. Mikä on keskilämpötila kappaleessa, kun tasapaino on saavutettu?