Ohjelmoinnin perusteet
Kurssikoe 17.10.2007
Tehtävä 3 - pisteytys ja mallivastaus
Janne Salo

Tehtävänanto:

Toteuta seuraava arvauspeli vuorovaikutteisena ohjelmana:
Ennen pelin alkua pelinjohtaja syöttää ohjelmalle sata kokonaislukua satunnaisessa järjestyksessä.  
Luvut saavat olla mitä tahansa kokonaislukuja. Sama luku saa esiintyä useammankin kerran.

Tämän jälkeen pelaaja alkaa käyttää ohjelmaa. Pelaaja yrittää arvata pelinjohtajan koneeseen syöttämiä lukuja. 
Peli päättyy, kun pelaaja onnistuu arvaamaan jonkin pelinjohtajan syöttämän luvun. 
Pelin tulos on tarvittujen arvausten määrä, jonka ohjelma lopuksi tulostaa.

Saat olettaa, että kaikki syötetyt luvut ovat kelvollisia kokonaislukuja.

Arvattavien lukujen hakeminen on tehokkuussyistä ohjelmoitava binäärihakua käyttäen.

Pisteytys:

Pisteytyksen kannalta tehtävässä oli selvästi havattavissa neljä erillistä osiota: lukujen lukeminen taulukkoon,
taulukon järjestäminen, arvausten kysely käyttäjältä sekä binäärihaku. Lisäksi huomiota kiinnitettiin ohjelman yleiseen
rakenteeseen.

Pisteitä ei vähennetty vähäisistä kirjoitus- ja syntaksivirheistä tai sellaisista virheistä, jotka liittyivät tehtävän kannalta
vähemmän olennaisiin asioihin, kuten Scanner-olion luonti.

Vaaditun ohjelman toimintalogiikka oli seuraavanlainen:

Luo taulukko
Jokaista taulukon alkiota kohden
	Pyydä käyttäjältä luku
Järjestä taulukko
Toista
	Pyydä käyttäjältä luku
	Suorita binäärihaku
Kunnes käyttäjä on arvannut jonkin taulukossa esiintyvän luvun

Pisteytys osioittain:

1. Yleisrakenne (2p)

Osiosta sai täydet pisteet, jos ohjelma suurin piirtein näytti Java-luokalta ja koodi oli luettavaa.
Myös ohjelman järkevä jako metodeihin (käytännössä siten, että binäärihaku ja järjestäminen ovat omina metodeinaan ja
varsinainen toimintalogiikka toteutetaan pääohjelmametodissa) oli suotavaa, mutta pisteitä ei vähennetty, 
vaikka erillisiä apumetodeita ei olisikaan käyttänyt. Monessa vastauksessa oli kehitelty myös (hieman tarpeettomasti) erilaisia
oliopohjaisia ratkaisuja. Tästä ei rangaistu, jos ohjelma näytti pääpiirteittäin toimivalta.

2. Lukujen lukeminen taulukkoon (3p)
- Taulukon luominen (1p)
- Silmukka, jossa lukuja pyydetään käyttäjältä ja laitetaan taulukkoon (2p)

Muutamissa vastauksissa lukuja ei kysytty käyttäjältä, vaan ne arvottiin taulukkoon. Tehtävänannossa oli tärkeä huomata sanat 
"pelinjohtaja syöttää ohjelmalle sata kokonaislukua". Ilmaisu "satunnaisessa järjestyksessä" oli (yhdessä binäärihakuvaatimuksen kanssa)
pikemminkin vihje siitä, että taulukko tulee järjestää. Koska tehtävänanto saattoi olla hieman epäselvä, vähennettiin tästä vain 1p.
Scannerin käytön tarkka syntaksi ei ollut osiossa olennaista. Syötteitä ei myöskään tarvinnut tarkistaa.

Taulukon luonnissa yleinen virhe oli tehdä yhtä alkiota liian pieni taulukko ("new int[99]").

3. Taulukon järjestäminen (4p)

Osiossa vaadittiin jonkin järjestämisalgoritmin toteuttamista.

Osiossa kiinnitettiin erityistä huomiota toteutetun järjestysalgoritmin oikeelliseen toimintaan. Siksi pisteitä vähennettiin mm. erilaisista
indeksointivirheistä, jos ne vaikuttivat algoritmin toimintaan (1 tai 2p, riippuen virheen vakavuudesta).

Jos algoritmi järjesti taulukon, mutta eri järjestykseen kuin binäärihaku tarvitsi (nouseva vs. laskeva), vähennettiin 2p.

Jos järjestämisalgoritmia ei ollut toteutettu, mutta vastauksessa oli huomautettu, että binäärihaku tarvitsee toimiakseen järjestetyn
taulukon ja lisäksi kuvattu sanallisesti jokin järjestämisalgoritmi, kohdasta sai yhden pisteen.

4. Lukujen kysely käyttäjältä (3p)
- Silmukka, jossa käyttäjältä pyydetään arvaus, kunnes saadaan luku, joka löytyy taulukosta (2p)
- Arvausten määrän laskeminen (1p)

5. Binäärihaku (4p)

Osiossa vaadittiin binäärihakualgoritmin toteuttamista.

Osioissa kiinnitettiin erityistä huomiota algoritmin toiminnan oikeellisuuteen, joten algoritmin toimintaan vaikuttavista syntaksi- yms.
virheistä vähennettiin 1-2 pistettä, riippuen virheen vakavuudesta.

Yleisin virhe oli indeksien ja alkioiden sekoittaminen keskenään (esim. verrattiin "keski == haettava", kun olisi pitänyt verrata "taulu[keski] == haettava"),
mistä vähennettiin 2p. Toinen yleinen virhe oli hakualueen oikean reunan indeksin asettaminen osoittamaan taulukon ulkopuolelle, mistä vähennettiin 1p.


Mallivastaus:

import java.util.Scanner;

public class Arvauspeli {

	private static Scanner lukija = new Scanner(System.in);

	private static boolean 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 true;     // löytyi ja lopetetaan!

			if (haettava < taulu[keski])
				oikea = keski-1;
			else
				vasen = keski+1;
		}
		return false;  // hakualue tuli tyhjäksi eikä löytynyt
	}
	

	private static void vaihtoJärjestä(int[] taulu) {
		for (int i=0; i < taulu.length-1; ++i) 
			for (int j=i+1; j < taulu.length; ++j)
				if (taulu[i] > taulu[j]) { // onko järjestys väärä?
					int apu = taulu[i];
					taulu[i] = taulu[j];
					taulu[j] = apu;
				}
	} 
	
	public static void main(String[] args) {
		int[] luvut = new int[100];
		
		System.out.println("Tervetuloa arvauspeliin!");
		System.out.println("Pelinjohtaja, syötä ensin "+luvut.length+" kokonaislukuja");
		
		for (int i = 0; i < luvut.length; i++) {
			System.out.println("Anna "+(i+1)+". luku: ");
			luvut[i] = lukija.nextInt();
		}

		vaihtoJärjestä(luvut);
        
		System.out.println("Pelaaja, nyt voit aloittaa arvaamisen. Onnea peliin!");
                int arvauksia = 0;
                boolean löytyi = false;
        
                do {
        	   arvauksia++;
        	
        	   System.out.println("Arvauksesi: ");
        	   int arvaus = lukija.nextInt();
        	
        	   löytyi = binHae(luvut, arvaus);
        	   if (!löytyi)
        		System.out.println("Arvauksesi oli väärä. Yritä toki uudelleen!");
        	
                } while (!löytyi);
        
                System.out.println("Oikein! Tarvitsit yhteensä "+arvauksia+" arvausta.");
	}

}