**************************************** Ohjelmoinnin jatkokurssi, syksy 2009 3. harjoitukset, 16.-20.11.2009 **************************************** ******************* Tehtävät 6&7 sekä 8 ******************* import java.util.Scanner; public class OmaString { public static final int MAKSIMIPITUUS = 100; private char [] mjono; // merkkijononon esitys char-taulukkona private int pituus; // montako alkioita mjono:n alusta on käytössä //----------------------------------------------------------------------- //konstruktorit: //----------------------------------------------------------------------- /* * luo tyhjää merkkijonoa esittävän OmaString-olion * Huom: taulukon koko on aina 100 (MAKSIMIPITUUS); */ public OmaString() { this.mjono = new char[MAKSIMIPITUUS]; this.pituus = 0; } /* * luo OmaString-olion annetusta String-oliosta * Esim: Jos parametri on "kissa vie", taulukkoa täytetään * alusta alkaen merkki merkiltä ja pituus-kenttä saa arvon 9. */ public OmaString(String s) { this.mjono = new char[MAKSIMIPITUUS]; this.pituus = s.length(); // Korkeintaan MAKSIMIPITUUS kappaletta merkkejä otetaan mukaan: if(this.pituus > MAKSIMIPITUUS) this.pituus = MAKSIMIPITUUS; for(int i=0; i < this.pituus; i++) this.mjono[i] = s.charAt(i); } /* * luo aidon kopion parametrina annetusta OmaString-oliosta, * myös taulukko kopioidaan */ public OmaString(OmaString m) { this.mjono = new char[MAKSIMIPITUUS]; this.pituus = m.length(); for(int i=0; i this.pituus) return false; if(this.pituus == MAKSIMIPITUUS) return false; // Siirretään loppua eteenpäin for (int i=this.pituus; i>ind; i--) this.mjono[i] = this.mjono[i-1]; // lisätään uusi merkki this.mjono[ind] = merkki; this.pituus++; return true; } /* * poistaa OmaString-merkkijonosta merkin kohdasta ind. Jos ind on liian * suuri tai liian pieni, mikään ei muutu. Metodi palauttaa arvon true, * jos poisto onnistui, muuten false. */ public boolean delete(int ind) { // indeksi kunnossa? if((ind > this.pituus-1) || (ind < 0)) return false; // siirretään merkkejä alkuun päin for(int i = ind; i < this.pituus-1; i++) this.mjono[i] = this.mjono[i+1]; this.pituus--; return true; } /* * palauttaa arvonaan OmaString-merkkijonoa vastaavan String-olion */ public String toString() { String palautus = new String(this.mjono); palautus = palautus.substring(0, this.pituus); return palautus; } //************************************************************** //Harjoitus 8: listään aksessorit //compareTo, equals, charAt, indexOf(char), indexOf(OmaString) //************************************************************** /* Vertaa this-OmaStringiä parametrina annettuun OmaStringiin. * palauttaa arvon -1, 0 tai 1 * (palauttaa myös 1, jos parametri on null) */ public int compareTo(OmaString toinen) { // hoidellaan virhetilanne palauttamalla 1 (hmmm ja hmm!) if (toinen == null) return 1; int lyhyempi; if (this.length() < toinen.length()) lyhyempi = this.length(); else lyhyempi = toinen.length(); // vertaillaan kaikkia merkkejä lyhyemmän vertailtavan pituuteen asti for (int n = 0; n < lyhyempi; n++) { if (this.charAt(n) < toinen.charAt(n)) return -1; else if (this.charAt(n) > toinen.charAt(n)) return 1; } // lyhyempi oli pidemmän alkuosa vai olivatko samat? if (this.length() < toinen.length()) return -1; else if (this.length() > toinen.length()) return 1; else return 0; } /* * Tutkii this-OmaStringin ja parametrina annetun OmaStringin samuutta: * * true jos samat, muuten false */ public boolean equals(OmaString toinen) { return this.compareTo(toinen) == 0; } /* palauttaa merkin annetusta indeksistä * (jos indeksi on virheellinen, palauttaa '\u0000'-merkin) */ public char charAt(int ind) { if (ind < 0 || ind >= this.pituus) return '\u0000'; return this.mjono[ind]; } /* Etsii merkkiä OmaString-oliosta * palauttaa ensimmäisen löytyneen merkin indeksin * tai -1, jos ei löytynyt */ public int indexOf(char merkki) { for (int n = 0; n < this.length(); n++) if (this.charAt(n) == merkki) return n; // ei löytynyt! return -1; } /* Etsii OmaString-oliota OmaString-oliosta * palauttaa ensimmäisen löytyneen olion aloitusindeksin * tai -1, jos ei löytynyt tai parametri oli null */ public int indexOf(OmaString haettava) { if (haettava == null) return -1; // katsotaan joka merkin kohdalla voisiko etsitty alkaa tästä for (int i = 0; i < this.length() - haettava.length() + 1; i++) { // etene jos merkit ovat samoja, aina merkki.length()-arvoon saakka int j = 0; while (j < haettava.length() && this.charAt(i + j) == haettava.charAt(j)) j++; // kaikki merkit mätsäsivat, siis löytyi ja alkaen i:stä! if (j == haettava.length()) return i; } // ei löytynyt, nyyh return -1; } //************************************************************* //Lopulta pääohjelma pääsee esittelemään OmaStringin käyttöä! //************************************************************ public static void main(String[] args) { Scanner lukija = new Scanner(System.in); System.out.print(kehystä("Anna jokin teksti tutkittavaksi:") + "\n>"); String apu = lukija.nextLine(); String historia[] = new String[100]; OmaString oma = new OmaString(apu); int valinta = 0; int indeksi, histIndeksi=0; historia[histIndeksi] = oma.toString(); char vanha, uusi; do { System.out.println("------------------------"); System.out.println("->" + oma + "<-"); System.out.println("------------------------"); System.out.println("Mitä haluat tehdä?"); System.out.println("0. Lopetus!"); System.out.println("1. Pituus?"); System.out.println("2. Korvaa merkki"); System.out.println("3. Poista merkki"); System.out.println("4. Lisää merkki"); //compareTo, equals, charAt, indexOf(char), indexOf(OmaString): System.out.println("5. Vertaa merkkijonoa toiseen"); System.out.println("6. Etsi merkkiä"); System.out.println("7. Etsi merkkijonoa"); System.out.println("8. Näytä muutoksien historia"); System.out.println("9. Uusi merkkijono!"); System.out.println("------------------------"); System.out.print(">"); valinta = lukija.nextInt(); if(valinta == 1) { System.out.println(kehystä("Merkkijonon pituus on: " + oma.length())); } if(valinta == 2) { histIndeksi++; System.out.println(kehystä("Anna korvattava merkki:")); System.out.print(">"); vanha = lukija.next().charAt(0); System.out.println(kehystä("Anna korvaava merkki:")); System.out.print(">"); uusi = lukija.next().charAt(0); oma.replace(vanha, uusi); historia[histIndeksi] = oma.toString(); } if(valinta == 3) { histIndeksi++; System.out.println(kehystä("Anna poistettavan indeksi:")); System.out.print(">"); indeksi = lukija.nextInt(); if(!oma.delete(indeksi)) { System.out.println(kehystä("Virheellinen indeksi!")); histIndeksi--; } historia[histIndeksi] = oma.toString(); } if(valinta == 4) { histIndeksi++; System.out.println(kehystä("Anna lisättävä merkki:")); System.out.print(">"); uusi = lukija.next().charAt(0); System.out.println(kehystä("Anna lisättävän indeksi:")); System.out.print(">"); indeksi = lukija.nextInt(); if(!oma.insert(indeksi, uusi)) { System.out.println(kehystä("Virheellinen indeksi!")); histIndeksi--; } historia[histIndeksi] = oma.toString(); } if(valinta == 5) { System.out.print(kehystä("Anna verrattava merkkijono:") + "\n>"); // Jos näin ei tee, Scanner-olioon jää jumittamaan rivinvaihto // seuraavan next...()-kutsun kiusaksi lukija.nextLine(); // nyt pitäisi olla muuta luettavaa kuin rivinvaihto apu = lukija.nextLine(); OmaString toinen = new OmaString(apu); int tulos = oma.compareTo(toinen); if (tulos == -1) System.out.println(kehystä("Alkuperäinen merkkijono on pienempi.")); if (tulos == 1) System.out.println(kehystä("Alkuperäinen merkkijono on suurempi.")); else System.out.println(kehystä("Merkkijonot ovat samat.")); } if(valinta == 6) { System.out.print(kehystä("Anna etsittävä merkkijono:") + "\n>"); char merkki = lukija.next().charAt(0); indeksi = oma.indexOf(merkki); if (indeksi != -1) System.out.println(kehystä("Löytyi indeksillä " + indeksi)); else System.out.println(kehystä("Eipä löytynyt, nyyh :/")); } if(valinta == 7) { System.out.print(kehystä("Anna esittävä merkkijono:") + "\n>"); // ks. yltä miksi pitää lukea tämä rivi lukija.nextLine(); apu = lukija.nextLine(); OmaString merkki = new OmaString(apu); indeksi = oma.indexOf(merkki); if (indeksi != -1) System.out.println(kehystä("Löytyi alkaen indeksistä " + indeksi)); else System.out.println(kehystä("Eipä löytynyt, nyyh :/")); } if(valinta == 8) { System.out.println(kehystä("Historia:")); for(int i=0; i <= histIndeksi; i++) System.out.println(i + " " +historia[i]); System.out.println("------------------------"); } if(valinta == 9) { System.out.print(kehystä("Anna merkkijono tutkittavaksi:") + "\n>"); lukija.nextLine(); apu = lukija.nextLine(); OmaString newString = new OmaString(apu); oma = newString; histIndeksi=0; historia[histIndeksi] = oma.toString(); } } while(valinta !=0); } //---------------------------------------------- // Kehystää merkkijonon (käyttöliittymää varten) //---------------------------------------------- public static String kehystä(String s) { String apu = ""; for(int i=0; i < s.length(); i++) apu +="-"; apu += "\n" + s + "\n"; for(int i=0; i < s.length(); i++) apu +="-"; return apu; } } ********* Tehtävä 9 ********* import java.util.Scanner; public class Humanisoi { public static void main(String [] args) { Scanner lukija = new Scanner(System.in); while (lukija.hasNextLine()) { OmaString rivi = new OmaString(lukija.nextLine()); for (char c = '0'; c <= '9'; c++) rivi.replace(c, '*'); System.out.println(rivi); } } } ********** Tehtävä 10 ********** Ohessa muutaman Wiklan vertailuohjelman ajokerran tuloksia eli järjestysalgoritmien suoritusaikoja millisekunteina. Tulokset heijastelevat hyvin järjestelyalgoritmien tunnettuja ominaisuuksia vaikka näistä ei menisi vielä päättelemään mitään tilastollisesti pätevää. Esim. satunnaisen taulukon testi erityisesti kannattaa toistaa. Satunnaislukuja 0...999 Algoritmi Taulukon koko 100 1000 10000 50000 100000 Vaihto 1 5 261 4929 19298 Kupla 1 7 398 9922 39669 Lisäys 0 3 112 2772 11050 Pika 0 2 2 10 18 Luvut 0...999 nousevassa järjestyksessä 100 1000 10000 50000 100000 Vaihto 1 3 188 4605 18669 Kupla 0 4 192 4841 20020 Lisäys 0 0 2 3 3 Pika 0 1 1 4 8 Laskevassa järjestyksessä oleva taulukko 100 1000 10000 50000 100000 Vaihto 1 6 340 8545 34502 Kupla 1 6 342 8353 34265 Lisäys 1 4 223 5480 22234 Pika 0 1 3 7 10 Taulusta huomaa hyvin, että jos taulukko on jo halutussa järjestyksessä, lisäysjärjestäminen käy sen vain läpi, eikä yritä järjestää mitään. Toisaalta vaikka pikajärjestäminen on hitaampi järjestetyssä taulukossa kuin lisäysjärjestäminen, sen käyttämät ajat pyvyvät kauttaaltaan kymmenissä millisekunneissa kun muilla algoritmeilla voi kulua sekunteja. Järjestämisen vertailujen määrä onkin avainkysymys: kupla- ja vaihtojärjestäminen vertaavat jokaista taulukon alkiota lähes jokaiseen muuhun taulukon alkioon (ks. tarkemmin mihin tarkemmin verrataan). Lisäysjärjestäminen ei joudu tekemään tätä jos taulukko on järjestyksessä. Pikajärjestäminen vähentää vertailujen määrää hieman binäärihaun tapaan hajoita-ja-hallitse -periaatteella. Järjestettävä taulukko jaetaan osiin jakoalkion kohdalta, niin että jakoalkiota isommat alkiot tulevat eri osioon kuin sitä pienemmät. Tämän jälkeen jakoalkiota isompia ei enää tarvitse verrata pienempiin, koska niiden välinen järjestys tiedetään. Eri osiot voidaan taas jakaa rekursiivisesti uusien valittujen jakoalkioiden perusteella pienempiin osioihin, kunnes ei ole mitään jaettavaa osiota, jolloin koko taulukko on järjestyksessä. Jos jakoalkio valitaan onnistuneesti, joka jaon tuloksena olevat osiot ovat kooltaan noin puolet jaettavasta osiosta. Niinpä vähän niinkuin binäärihaussa jakojen määrän suhde taulukon kokoon on logaritminen, eli kutakin alkiota verrataan korkeintaan logaritmiseen osaan taulukon koko lokeroiden määrästä. Koska alkiot on kuitenkin käytävä läpi, aikavaativuus on suuruusluokkaa n*log n. (vrt binäärihaun vaativuus oli aidosti logaritminen). Pikajärjestäminen on kuitenkin altis ilkeässä järjestyksessä oleville taulukoille. Mitä jos joka jako jakaa jaettavan osion 1 ja o-1 alkion kokoisiin osiin, missä o on osion koko? Miten laatisit kurssilla esitetylle pikajärjestämisalgortmille mahdollisimman ilkeän taulukon? Miten välttää 'ilkeiden järjestyksien' mahdollisuus? Lisää infoa kiinnostuneille Tietorakenteet-kurssilla ja algoritmilinjalla.