/* Tehtävä 26. Pääohjelman pikku apulaisia taulukoiden käsittelyyn */ public class Apulaiset { private static void asetaIndeksiKax ( int [] taulu ) { for (int i = 0; i < taulu.length; i++) taulu[i] = i*2; } private static void tulostaParittomat (int [] taulu ) { for (int i = 0; i < taulu.length; i++) if (taulu[i] % 2 != 0) System.out.print(taulu[i] + ","); } private static int etsiSuurimmanIndeksi (int [] taulu) { if (taulu.length == 0) return 0; int suurimmanindeksi = taulu[0]; for (int i=1; i < taulu.length; i++) if (taulu[i] > taulu[suurimmanindeksi]) suurimmanindeksi = i; // etsii "ensimmäisen" suurimman... // jos vertailuehto olisi >=, löytyisi viimeinen // pienimmät löytyvät vaihtamalla ehto < tai <=-merkkiin return suurimmanindeksi; } private static void pyöräytäYmpäri (int [] taulu) { if (taulu.length == 0) return; int vika = taulu[taulu.length-1]; for (int i = taulu.length -1; i > 0; i--) taulu[i] = taulu[i-1]; taulu[0] = vika; } private static void tulostaTaulu (int [] taulu) { boolean bFirst = true; for (int alkio : taulu) { if (!bFirst) System.out.print(","); else bFirst = false; System.out.print(alkio); } System.out.println(); } public static void main(String [] args) { int[] a = {10, 20, 30, 40, 50}; int[] b = {7,6,32,67,8,32,12,1,4,5,7,324,673,125,2725,324,2,5,7,32,4,7,4}; int[] c = new int[15]; Apulaiset.asetaIndeksiKax ( c ); Apulaiset.tulostaTaulu ( a ); Apulaiset.tulostaTaulu ( b ); Apulaiset.tulostaTaulu ( c ); Apulaiset.tulostaParittomat ( b ); System.out.println(); int suurin = Apulaiset.etsiSuurimmanIndeksi ( b ); System.out.println("suurin b:stä on :"+b[suurin] + " lokerossa "+suurin); Apulaiset.tulostaTaulu ( c ); System.out.println("------------"); Apulaiset.pyöräytäYmpäri ( c ); Apulaiset.tulostaTaulu ( c ); } } /** * Lukuryhmä on taulukko-olio, joka pitää itsensä järjestyksessä, kun sinne * lisätään alkioita lisää()-metodilla. Sen jäseniin ei pääse lisäämisen * jälkeen käsiksi muuten * kuin löytyykö()-metodilla, joka kertoo onko lukuryhmässä parametrina * annettua lukua. Tavallaan lukuryhmän voi nähdä eräänlaisena monijoukkona, * koska siellä voi olla sama luku monta kertaa. Tehtävä 27, Jaakko Nurro **/ public class Lukuryhma { private int [] luvut; //luvut ovat tehtävänannon mukaan taulukossa private int vikatäysi; // se lokero, jossa on ryhmän viimeinen luku /** * Konstruktorilla alustetaan minkä kokoinen lukuryhmä-olio on. Kokoa * ei voi toistaiseksi muuttaa, ja lukuryhmien kopioiminen on vaikeaa, * mutta tämän kerran tehtävien puitteissa tämä on OK. **/ public Lukuryhma(int lukumäärä) { luvut = new int[lukumäärä]; vikatäysi = -1; } /** * Ainut tapa lisätä lukuja lukuryhmään. Lukuryhmä pidetään järjestyksessä * siten että lisättävälle luvulle etsitään aina paikka peräkkäishaulla * lopusta alkaen ja kopioidaan samalla lisättävää lukua suuremmat luvut * kohti taulukon loppua pois tieltä. Huomaa, että jos lukuryhmään yrittää * lisätä enemmän alkioita kuin on varattu tilaa, tapahtuu poikkeus. **/ public void lisää(int luku) { int i = vikatäysi+1; // seuraava tyhjä lokero taulukossa while (i>0 && luvut[i-1]>luku) { // kopioidaan parametria luku suuremmat luvut taulukossa // seuraamaan parametria luvut[i]=luvut[i-1]; --i; //taulukkoa käydään siis lopusta alkuun } luvut[i] = luku; // lisätään parametrin luku arvo paikalleen ++vikatäysi; // lukuryhmässä on nyt yksi enemmän lukuja } /** * Etsii binäärihaulla parametrina luku saatua lukua luvut-taulusta. * Palauttaa true, jos luku löytyy taulusta, false, jos ei löydy. */ public boolean löytyykö(int luku) { int vasen = 0; int oikea = vikatäysi; int keski; while (vasen <= oikea) { keski = (vasen+oikea)/2; if (luku == luvut[keski]) return true; // löytyi ja lopetetaan! if (luku < luvut[keski]) oikea = keski-1; else vasen = keski+1; } return false; // hakualue tuli tyhjäksi eikä löytynyt } } import java.util.Scanner; /** * Tehtävä 27: Yksinkertainen luokka Lukuryhman käyttämiseen. * Luokan teki Jaakko Nurro 2006 */ public class LukuRyhmaLiittyma { private static Scanner lukija = new Scanner(System.in); public static void main(String [] args) { System.out.println("Montako lukua haluat syöttää?"); int lukumäärä = lukija.nextInt(); Lukuryhma luvut = new Lukuryhma(lukumäärä); for (int i=0; i39, konstruktorista tulee poikkeus, mikä on oikein. **/ public Lotto( int [] rivi, int [] lisanot) { for (int i = 0; i < 7; i++) this.oikeaRivi[ rivi[i] -1 ] = true; for (int i = 0; i < 3; i++) oikeaLisanot[ lisanot[i] -1 ] = true; } public void kysy (int [] rivi) { int oikeat = 0, oikeatl = 0; for (int i = 0; i < 7; i++) if (oikeaRivi[ rivi[i] -1 ]) oikeat++; else if (oikeaLisanot [ rivi[i] -1 ]) oikeatl++; System.out.println("---------------------------"); System.out.println("Oikeita: " + oikeat); System.out.println("Lisänot: " + oikeatl); System.out.println("***************************"); } } import java.util.Scanner; /** Tehtävä 28: * Käyttöliittymä Lotto-luokan käyttämiseen * Lotto-luokka on aika tyhmä, joten liittymä joutuu huolehtimaan * siitä, ettei lottoriveissä ole monta kertaa samoja numeroita * tai väärän kokoisia numeroita. Luokan nykersi Jaakko Nurro 2006. */ public class LottoLiittyma { private static Scanner lukija = new Scanner(System.in); /** Käytetään Lukuryhma-oliota tarkastamaan etteivät numerot toistu * lottorivissä. Sivuvaikutuksenaan metodi täyttää taulu-parametrin * viittaman taulu-olion ja syötetyt-parametrin viittaaman * Lukuryhmä-olion käyttäjän syöttämillä luvuilla. Tämän tarkoitus * on lähinnä näyttää miten oliot käyttäytyvät kun viitteitä niihin * annetaan parametreina metodeille. Jos käyttäjä syöttää jotain muuta * kuin kokonaisluvun, tulee poikkeus. */ private static void lueTaulukkoonLuvut(int [] taulu, Lukuryhma syötetyt) { for(int i=0; i0 && taulu[i]<40);//onko luettu oikealta väliltä if (!ok) System.out.println("Lottonumeroiden on oltava väliltä "+ "1-39. Syötä joku luku tuolta väliltä."); ok = ok && !syötetyt.löytyykö(taulu[i]);//onko ollut jo aiemmin if (!ok) System.out.println("Lottorivin ja lisänumeroiden pitää"+ " olla eri numeroita."); } while (!ok); syötetyt.lisää(taulu[i]);//lisätään luku käsiteltyjen lukuryhmään } } public static void main( String [] args) { int [] rivi = new int[7]; int [] lisät = new int[3]; // käytetään tätä luetut-oliota lottorivin ja lisänumeroiden // pitämiseen eri lukuina Lukuryhma luetut = new Lukuryhma(10); System.out.println("Syötä 7 numeron lottorivi:"); lueTaulukkoonLuvut(rivi, luetut);// taulukkoihin luetaan lukuja System.out.println("Syötä 3 lisänumeroa:"); lueTaulukkoonLuvut(lisät, luetut); // ettei lisänumeroissa olisi // jo rivinä olevia lukuja Lotto lotto = new Lotto (rivi, lisät); System.out.println("Nyt voit kysellä montako jossain"+ " lottorivissä on oikein"); while (true) { // toistetaan periaatteessa loputtomiin System.out.println("Syötä 7 numeron lottorivi. Jos haluat "+ "ohjelman päättyvän, voit syöttää jotain"+ "muuta kuin numeroita, niin ohjelma kaatuu"+ " virheeseen."); //luodaan uusi lukuryhmä-olio uudelle riville luetut = new Lukuryhma(7); // vanha 10-kokoinen olio hylätään //tässä voi tulla ohjelman keskeyttävä virhe lueTaulukkoonLuvut(rivi, luetut); lotto.kysy(rivi); //tarkastetaan rivi } } } /** * Ohjelmoinnin perusteet, syksy 2006, harjoitukset 6, tehtävä 29. * Kukaan ei tunnusta tehneensä tätä. */ public class Tehtava29 { public static void main(String[] args) { //Järjestetään komentoriviparametrit for (int n = 0; n < args.length - 1; n++) { int pienin = n; for (int i = n + 1; i < args.length; i++) { // Jos haluttaisiin aakkostaa isot ja pienet kirjaimet // samoina (eli 'a' == 'A' < 'Z' == 'z'), korvataan rivi // seuraavalla: // if (args[i].compareToIgnoreCase(args[pienin]) < 0) if (args[i].compareTo(args[pienin]) < 0) { pienin = i; } } String apu; apu = args[n]; args[n] = args[pienin]; args[pienin] = apu; } //Taulukko on järjestetty ja se voidaan tulostaa. for (int i = 0; i < args.length; i++) { System.out.println(args[i]); } } } /** * Ohjelmoinnin perusteet, syksy 2006, harjoitukset 6, tehtävä 30. */ =============================================== Paras tapaus: etsittävä alkio on taulukon ensimmäinen (peräkkäishaku) tai taulukon keskimmäinen (binäärihaku). Huonoin tapaus: etsittävää alkiota ei ole taulukossa lainkaan (sekä peräkkäis- että binäärihaulla huonoin tapaus). ph, paras bh, paras ph, huonoin bh, huonoin ------------------------------------------------------------------- 10 1 1 10 4 100 1 1 100 7 1 000 1 1 1 000 10 10 000 1 1 10 000 14 100 000 1 1 100 000 17 private static int binHae(int[] taulu, int haettava) { int vasen = 0; int oikea = taulu.length-1; int keski; while (vasen <= oikea) { keski = (vasen+oikea)/2; if (haettava == taulu[keski]) return keski; // löytyi ja lopetetaan! if (haettava < taulu[keski]) oikea = keski-1; else vasen = keski+1; } return -1; // hakualue tuli tyhjäksi eikä löytynyt } Silmukan sisällä tehtävät operaatiot vievät vakioajan. Silmukkaa toistetaan kunnes left on pienempi tai yhtäsuuri kuin right. Etsittävä alue puoliintuu jokaisella silmukan kierroksella. Katettu alue siis tuplaantuu kierroksittain. Kuinka monta kertaa meidän on siis toistettava että katettu alue on taulukon koko n? On ratkaistava (epä)yhtälö 2^t >= n jos t on toistojen määrä. Tästä seuraa se, että silmukka toistetaan noin log n kertaa, jossa n on taulukon koko ja log tarkoittaa kaksikantaista logaritmia. Peräkkäishaulla joudutaan keskimäärin tutkimaan puolet taulukon alkioista. Milloin binäärihaussa on katettu vastaava määrä alkioita? Binäärihakua tutkittaessa voidaan tarkastella ns. binääripuuta, joka kuvaa haun etenemistä. Binääripuussa suurin piirtein puolet taulukon sisällöstä ovat tasolla log n ja toinen puoli lähempänä haun alkua. Niinpä keskimääräisesti binäärihaulla joudutaan käymään läpi lähes saman verran alkioita kuin pahimmassa tapauksessa (log n). 31. Vinkkejä kurssikyselyyn: - Saa purkaa tuntojaan, mutta siitä on meidän vaikea keksiä miten parantaa - Selkeät parannusehdotukset ovat tervetulleita - Kurssikyselyn saa täyttää uudestaan kokeen jälkeen! Varsinkin jos täyttää sen vain koetta koskevilta osin, se ei edes vääristä tilastoja juurikaan. 32. Meitä varmasti kiinnostaa, miten voisimme tukea opintopiirejä paremmin. Tehtävissä on niin paljon pureskeltavaa ja purkamista, että varsinainen ryhmätyöhön ohjaaminen on voinut valitettavasti jäädä vähän vähille. Esseessä tärkeintä on pysähtyä vähän miettimään, jos saatte siitä jotain koherenttia irti, sen parempi vain. Kannattaa ottaa tällaiset yhden rastin arvoisetkin tehtävät tärkeinä kirjallisen ilmaisun harjoituksina, niitä ei ole koskaan liikaa.