wiki:k2015/demot/demo2
Last modified 3 years ago Last modified on 2015-01-22 13:15:34

Demot » Demo 2, 26.1.2015

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

English version

Itsearvio A1 (0p mutta pakollinen)

Jollet tehnyt jo maanantain demopalautuksessa, niin täytä edellisen (esim. demo1:n arvion demo 2 kerralla) kerran itsearviolomake: arvio.txt (lataa ja muokkaa) ja palauta NettiDemoWWW:hen nimellä A1 tiedosto arvio.txt tai jos täytät käsin paperille demon aikana etkä jaksa kirjoittaa koneelle, niin ota kuva tai skannus paperista ja paluta arvio.X (missä X on joku seuraavista: pdf, jpg, png).

VIDEO 1

Muista että voit saada demopisteitä myös indeksoimalla luento/demovideoita, ks: videohakemisto. Lisää vähintään 3-linkkiä ja kerro tiedostoon video.txt mitkä linkit lisäsit. Tehtävän numeroksi VIDEO1. Jatkossa voi joka demokerralle merkitä vastaavasti yhden VIDEO-tehtävän kolmesta linkistä vaikka erikseen Video-tehtävää ei olisi mainittukaan. Video-tehtävä ei saa olla yksi pakollisesta kahdesta tehtävästä.

Tauno T1 (0.5 p)

Tee iTaunolla- seuraavat tehtävät:

  1. Laske yhteen taulukon luvut.
  2. Laske yhteen taulukon parillisissa paikoissa olevat luvut.

Paina aina Taunolla tehtyjen muokkaustan jälkeen linkkejä Copy from Tauno ja sitten kokeile painikkeita Aja ja Testaa. Kun tulee vihreää, saattaa koodi olla oikein.

Halutessasi voit tehdä kokeilun myös Eclipsellä (tai saat suoraan kirjoittaa vastaukset tuohon Todo-kohtaan):

  1. luo Eclipsessä uusi projekti vaikka nimelle demot (jos sellaista ei jo ole sinulla).
  2. luo src-kansion alle uusi paketti demo.d3
  3. luo paketin alle uusi Java-luokka TaulukonSummia
  4. Kopioi Java-pohja tuon tiedoston sisällöksi

Ville V1 (0.5 p)

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

A2. Kurssin alkukysely (0.5 p)

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

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:

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

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 jos ( dp < 40% tai vk1 < 6 tai summa < 12 )
b) ei lennä ulos kapakasta jos (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än voit tehdä myös TIMissä

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
symmetrisyys:     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ä hakemistoa (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

https://trac.cc.jyu.fi/projects/ohj2/raw-attachment/wiki/k2014/demot/demo2/napoleon.png

  • 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.