Ohjelmointi 2 2016 / Demo 2

Demot » Demo 2, 25.1.2016

English version

Tähdellä (*) merkitty ne tehtävät, jotka ehdottomasti kannattaa tehdä. Palautus viimeistään maanantaina klo 13:00 mennessä. Voit palauttaa osan tai kaikki tehtäväsi etukäteenkin ja täydentää vastauksia määräaikaan mennessä.

Itsearvio A1 (0p mutta pakollinen)

Jollet tehnyt jo maanantain demopalautuksessa, niin täytä edellisen (esim. demo1:n arvion demo 2 kerralla) kerran itsearviolomake.

Kirjoita alla olevaan tekstilaatikkoon kunkin edellisen demokerran tehtävän kohdalle === katkoviivan alle:

• millainen oli oma vastauksesi verrattuna malliin/demojen palautuksessa käsiteltyyn tehtävään
• olisiko omassa vastauksessasi pitänyt olla jotakin enemmän/vähemmän
• jos et ollut tehtävää tehnyt, niin miksi?
• jos et ollut tehtävää tehnyt, niin mitä ymmärsit vastaavasta mallivastauksesta tai demojen palautuksessa käsitellystä vastauksesta
• osaisitko nyt tehdä vastaavan tehtävän ja miten, kun olet mallin nähnyt?

Erityisesti täytettävä perustehtävien "Tehtävä X" osalta, missä X on jokin numero. Sekä kaikkien muiden, mitä olet tehnyt (mahdollisesti esim. Tauno, B-G). Toki mielellään ymmärtämisen osalta myös tehtävän B osalta, vaikket olisi tehnytkään.

Lisää tarvittavat otsikkorivit lopuille tehtäville samaan tyyliin kuin alla on tehty.

Video 1 (1 p)

Muista että voit saada demopisteitä myös indeksoimalla luento/demovideoita, ks: videohakemisto. Demopisteen saat lisäämällä vähintään 3 linkkiä. Video-tehtävä ei saa olla yksi pakollisesta kahdesta tehtävästä.

Tauno (0.25 + 0.25 p)

Tee iTaunolla seuraavat tehtävät:

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

Toki saat aina kirjoittaa Tauno-tehtävät suoraankin koodiksi. Tällöin mielellään silmukoita käyttäen.

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.

Muista että nyt sinun tarvitsee lisätä itse indeksimuuttujia, jotta pääset käsiksi taulukon alkioihin.

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

Palauta tehtävä kirjoittamalla alla olevaan tekstilaatikkoon mitä opit ja mitä mieltä olit kerran Ville-tehtävistä ja auttoivatko Ville-tehtävät sinua yhtään. Muutama rivi riittää.

A2. Kurssin alkukysely (0.5 p)

Vastaa kurssin alkukyselyyn. Tehtävän vastaukseksi kerro lyhyesti mikä on muuttunut suhteessa ensimmäiseen vastaukseesi vastaavaan kyselyyn?

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ä kompleksisuutta?

Mikäli sinulla ei ole puhelinluetteloa tai et ole sellaista koskaan nähnyt, keksi joku muu riittävän iso järjestetty aineisto, jolla kokeilet. Ota esimerkiksi Kotus-sanalista ja pura se johonkin ja avaa sieltä kotus-sanalista_v1.xml tekstieditorilla, jossa näkyy rivinumerot.

Tehtävä 3, Napoleonin hauta -pasianssi

Katso ensin demo 1:n mallivastaus opettajan 6- -muuttamisesta.

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 (Linux ja Mac : wine napoleon.exe)

Alla on taulukon pohjaa lähtökohdaksi. Täytä se loppuun ja kerro sitten sanallisesti mitä tehdään kunkin kortin kanssa.

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. (Linux ja Mac : wine 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 käsin 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ä.

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:

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
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. TIMissä kopioi tuo Kombinaatiot.java-tiedostosta tuohon seuraavaan laatikkoon. Tiedoston Pallopeli.java package-rivin pitää vastata sitä hakemistoa (suhteessa src-hakemistoon) mihin olet tuon tiedoston tehnyt.

Katso vertailun vuoksi myös Haskell-versio.

Kopioi alle Kombinaatiot.java:

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

Ennen Ohjelmointi 2-kurssilla palautettiin demot niin, että täytettiin tiedostoa files.txt, johon merkittiin tehtävän tiedosto, tehtävän numero ja tehtävästä ansaitus pisteet. Tee metodi pisteet, jolle viedään parametrinä merkkijono (jonon oltava samaa muotoa kuin yksi files.txt:ssä oleva rivi, ks. esimerkkejä alla) 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. api RegExp). 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.