wiki:k2013/demot/demo2
Last modified 5 years ago Last modified on 2013-05-28 15:18:59

Demot » Demo 2, 21.1.2013 - Kesällä to 30.5.2013

Tähdellä (*) merkitty ne tehtävät, jotka ehdottomasti kannattaa tehdä. Palautus: NettiDemoWWW

Ville V1

Tee JAVA Villestä tehtävät 3.1-3.6 Merkkijonojen käsittely. 1.4 Ville-tehtävien palautus NettiDemoWWW:llä.

A1. Kurssin alkukysely

Vastaa kurssin alkukyselyyn. Tehtävän vastaukseksi palautetaan tiedosto ohjelmointi.txt jossa on jokin kysymys, jonka haluaisit esittää luennoitsijalle. Parhaisiin vastataan luennoilla. HUOM! Ei kesän kurssilla voimassa.

Tehtävä 1, erilainen lajittelu

Ks. tehtäviä 3.2 ja 3.3. Tehdään järjestämisalgoritmista vielä yksi versio k-kirjaimisille nimille (meillä on lappuja, joissa on jokaisessa yksi sana jossa on k kpl kirjaimia):

0. i = k
1. Laita i:n kirjaimen mukaan kukin lappu omaan kasaansa nurinpäin
   (eli on kasa A-kirjaimille, B-kirjaimille, ...) 
2. i = i - 1
3. Kerää kasat oikeinpäin päällekkäin siten että ylimmäksi tulee A-kasa
4. jos i > 0, niin jatka 1.
5. Nimet järjestyksessä.

Jos jokaisessa nimessä olisi 10 kirjainta, niin mikä olisi tämän "jakamisalgoritmin" kompleksisuus (karkeasti ottaen: montako kertaa kutakin lappua pitäisi katsoa)?

Vinkki: Tee itsellesi reilut 10 lappua, joihin kuhunkin laitat yhden satunnaisen 3-kirjaimisen sanan käyttäen vaikka vain kirjaimia A, B ja C. Sitten sotke nämä laput ja tee em. algoritmi HUOLELLISESTI ja laske monesti yhteensä joudut lappuja katsomaan. Näin saat vaativuuden n-lappua, 3 kirjainta. Tästä voi päätellä vaativuuden (kompleksisuuden) 10-kirjaimisille sanoille ja yleisesti k-kirjaimisille sanoille.

Tehtävä 2, puolitushaku

Kokeile puolitushakua puhelinluetteloon 3:lla keksimälläsi nimellä (joku esiintyy luettelossa, joku ei). Huomaa että kun oikea sivu on löytynyt, on puolittamista jatkettava vielä sivun sisällä! Kirjaa ylös "nimien katsomisten" lukumäärä kussakin tapauksessa. Katso Puolitushaku. Tehtävän 3.10 kompleksisuus O-mielessä olisi siis O(log n) (esim. merkintä O(n) tarkoittaa että operaatioiden määrä on muotoa k1 * n + k2). Vastaako puhelinluettelokokeilusi tätä kompeksisuutta?

Tehtävä 3, Napoleonin hauta -pasianssi

Algoritmi "Napoleonin hauta" -pasianssiin sen tarkistamiseksi, käykö tutkittava kortti tiettyyn "pakkaan" ja voiko toisaalta jostakin pakasta ottaa kortin. Ks. liite ja koeta keksiä taulukkopohjainen toteutus jossa "kaikki" pakat ovat "samanlaisia"! Ohjelmana:

n:\kurssit\winohj\vclclx\delphi\korttipe\napoleon.exe

Vinkki: Katso tiistain luentovideo alkaen 2:17.

Tehtävä 4*, punaiset toiseen laitaan

Keksi ilman lajittelua (siis älä käytä valmista lajittelualgoritmia) toimiva algoritmi joka siirtää pöydälle riviin levitetystä korttipakasta punaiset kortit vasempaan laitaan ja mustat oikeaan laitaan (vaikkei punaisia ja mustia olisi yhtä monta).

Vihje: vrt. tehtävä 3.14. Käytä osoittimia. Voit testata algoritmissasi ohjelmalla

n:\kurssit\winohj\vclclx\delphi\korttipe\jarjesta.exe.

Tehtävä 5, seuraava päiväys

Olkoon päiväys muodossa pp.kk. Kirjoita "suomenkielinen" algoritmi (ei Java-ohjelmaa), joka lisää päiväystä yhdellä (esim. 25.1 + 1 => 26.1, 31.1 + 1 => 1.2 jne.).TDD: Kirjoita ensin riittävästi esimerkkejä eri vaihtoehdoista.

Tehtävä 6*, kertoma

Kirjoita Java-funktiot kertoman laskemiseksi sekä do-while -silmukalla että while -silmukalla. TDD: Kirjoita ensin kertomat 10 saakka.

n! = 1*2*3...(n-1)*n, esim 3! = 1*2*3 = 6
0! = 1

Pöytätestaa (ks. 4.4.2) Java-funktiosi syötöillä 0, 3 ja 6. Päättele myös toimisiko 1:llä.

Vinkki: Katso tiistain luentovideo alkaen 37:00.

Tehtävä 7, moniulotteiset taulukot

Sijoita 3 korttia kohdan 4.4.5 2-ulotteiseen mallitaulukkoon sekä tee tehtävä 4.13 (muttei mallitehtävän vastauksia). Sijoituksia voit tehdä seuraavalle pohjalle: taulukot.txt.

Tehtävä 8*, ehtojen sieventäminen

"Sievennä" seuraavat ehdot (ks. moniste 4.7.4 Loogiset operaatiot):

Malli: ei ( a < 5) sivennettynä: ( a >= 5 )

a) ei hyväksytty joss ( dp < 40% tai vk1 < 6 tai summa < 12 )
b) ei lennä ulos kapakasta joss (kello < 4.00 ja selvinpäin)
c) NOT ( vikoja>90%  AND kesto<5 kk)
d) ( (kello<7) tai sataa ) ja NOT ( ( kello>=7 ) ja ei sumua )
e) kotiin jos ( pimeä ja kylmä ) tai ( pimeä ja pelottaa )

Tehtävä B1, nimen osien järjestyksen vaihtaminen

Täydennä liitteenä oleva etu- ja sukunimen vaihtamisohjelma Etusuku.java TODO-merkityistä kohdista (pituus ei tule olemaan montaa riviä :-). Tarkoituksena on käyttää apuna tuolla olevaa erota-funktiota. Sen käyttämiseksi jono pitää ensin luoda StringBuilderiksi:

StringBuilder sukunimi = new StringBuilder(nimi);

Tämä tehtävä jatkuu myöhemmin, joten tähän kannattaa tutustua.

Tehtävä B2, transitiivisuus

Luentomonisteen versiossa 2004 Luvussa 9.6 väitettiin että kahden olion yhtäsuuruudelta vaaditaan että

Olkoon seuraavassa a1,a2 ja a3 kolme luokan oliota ja b boolean arvo.

reflektiivisyys:  a1.equals(a1) pitää olla aina tosi
symetrisyys:      a1.equals(a2) == a2.equals(a1)
transitiivisuus:  a1.equals(a2) = b; a2.equals(a3) = b;  =>
                  a1.equals(a3) = b;

Näistä transitiivisuutta koskeva väite on väärä. Todista tämä vastaesimerkillä.

Tehtävä B3, pallopeli

Täydennä liitteenä oleva pallopelin todennäköisyyden laskuohjelma Pallopeli.java TODO-merkityistä kohdista. Ota ensin Kombinaatiot.java ja talleta se projektisi src-kansion alle demo/d1 hakemistoon. Tai kopioi tuolta Kombinaatiot.java-tiedostosta se aliohjelmat tuohon Pallopeli.java-tiedostoon (silloin poista import static-rivi). Tiedoston Pallopeli.java package-rivin pitää vastata sitä hakmeistoa (suhteessa src-hakemistoon) mihin olet tuon tiedoston tehnyt.

Katso vertailun vuoksi myös Haskell-versio.

Tehtävä B4, sanojen lukumäärä

Katso avustuksista luokkaa StringTokenizer. Tee sitä käyttäen Java-ohjelma, joka ky­syy yhden rivillisen sanoja ja tulostaa montako "kissa"-sanaa oli rivillä.

Anna rivi>kissa istuu puussa kissa naukuu ja kissa kehrää[RET]
Rivillä oli 3 "kissa" sanaa.

Rivin saa kysyttyä käyttäjältä:

   String rivi=""; 
   System.out.print("Anna rivi >");
   Scanner lukija = new java.util.Scanner(System.in);
   rivi = lukija.nextLine();

Tehtävä G1-2, pisteiden laskeminen files.txt -tiedostosta

Tee metodi pisteet, jolle viedään parametrinä merkkijono (jonon oltava samaa muotoa kuin yksi files.txt:ssä oleva rivi, ks vaikka demo1 palautuksesi siitä, miltä files.txt näyttää) ja funktio palauttaa reaalilukuna pisteiden lukumäärän (vinkki: Regular Expression ja java.util.regex.Pattern-luokka, vaatii vähintään SDK 1.4.1, ks. http://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html). RegExpejä on kiva opetalla esim. ohjelmalla http://www.weitz.de/regex-coach/

Esimerkkejä riveistä ja siitä, mitä palautetaan:

teht1.txt = [T1-2:1.5] - oikea muoto         =>  1.5
teht1.txt = [T1-2,1.5] - ei :                =>  0.0
teht1.txt = (T1-2:1.5) - väärät sulut        =>  0.0
teht1.txt = [T1-2:1,5] - pilkku eikä piste   =>  1.0
teht1.txt = T1-2:1.5   - sulut puuttuu       =>  0.0
teht1.txt   [T1-2:1.5] - =-merkki puuttuu    =>  0.0
teht1.txt = [1-2:1.5]  - T-merkki puuttuu    =>  0.0
teht1.txt = [B1-2:1.5] - T-merkki puuttuu    =>  0.0

Napoleonin hauta

"Napoleonin hauta" -pasianssi löytyy esim: n:\kurssit\winohj\vclclx\korttipe\napoleon.exe

1. Säännöt

  1. Mailla ei ole väliä
  2. Tarkoituksena on saada kortit viiteen kasaan:
    • kortit 7-K nurkkiin ja
    • 6,5,4,3,2,A,6,5,4,3,2,A,...,2,A keskelle.
  3. Pelin alussa on vain jakopakka ja tyhjät paikat 11 muulle "pakalle".

2. Pakat ja niiden säännöt

  • Kulmapakkoihin saa laittaa nousevassa järjestyksessä kortit 7,8,9,10,J,Q,K. Kulmapakoista ei saa ottaa kortteja.
  • Keskipakkaan (kuvassa ruutu 3) saa laittaa laskevassa järjestyksessä kortit: 6,5,4,3,2,A ja tämän jälkeen taas uudestaan 6,5,... Keskipakasta ei saa ottaa kortteja.
  • Apupakkoihin (ristikkäin, kuvassa A,J,10,Q) saa laittaa minkä tahansa yhden kortin ja sen saa siirtää siitä mihin tahansa pakkaan johon se käy. Eli apupakassa on aina 0 tai 1 korttia.
  • Kuutospakkaan saa laittaa pelkkiä 6:sia. Tämä on varasto 6 korteille, koska muuten keskipakkaa olisi vaikea saada valmiiksi. Pakkaan saa laittaa 6:en ja sieltä saa ottaa kortin silloin kun haluaa.
  • Käsipakka (kuvassa risti 9) on säilö niille korteille, jotka eivät käy muualle. Käsipakan päällimmäisen kortin saa ottaa ja sen voi sijoittaa mihin tahansa pakkaan johon ko. kortti käy. Käsipakkaan saa aina laittaa kortin päällimmäiseksi. Jakopakkasta otetaan seuraava tutkittava kortti. Jakopakka pidetään selkäpuoli ylöspäin. Jakopakkaan ei saa sijoittaa kortteja.

Attachments