Ohjelmoinnin perusteet, kesä 2003
Koetehtävä 4, arvosteluperusteet

Antti Vähäkangas


Tehtävänanto
------------

4. Toteuta seuraava palvelu vuorovaikutteisena ohjelmana:
Aamuisin ohjelmalle syötetään ensin korkeintaan tuhat kokonaislukua
missä järjestyksessä milloinkin. Lukuja voi siis olla vähemmänkin.
Päivän mittaan sitten usen kysellään onko jokin luku aamulla
syötettyjen lukujen joukossa. Illalla ohjelma suljetaan. Tehokkyyssyistä
lukujen hakeminen on välttämättä toteutettava binäärihakua käyttäen.


Pisteytys ja yleiset virheet
----------------------------

Kussakin kohdassa on mainittu yleisimpiä virheitä.
Lisäksi on mainittu kohdasta saatava maksimipistemäärä.

o järjestäminen
  - parametrienvälitys virheellinen
  - toteutettu suoraan main-metodiin
  - esitetty järjestämisalgoritmi ei järjestä oikein
  4p

o binäärihaku
  - parametrienvälitys virheellinen
  - toteutettu suoraan main-metodiin
  - silmukan lopetusehdot tai etsintäalueen päivittäminen väärin
  - metodin paluuarvo puuttuu tai palautusarvo on virheellinen
  - verrataan indeksejä kun pitäisi verrata arvoja
  - unohdettu varautua siihen, että etsittävää arvoa ei löydy
  - palautetaan etsitty luku indeksin sijaan ja kuitenkin
    tulkitaan paluuarvo -1 siten, että lukua ei löytynyt
  4p

o käyttöliittymä ja tietorakenteet
  - voi syöttää vain 1000 lukua
  - ei do-while kontrollia käyttäjän syötteestä
  - lukee luvut väärin
  - kysely toimii väärin
  4p

Yhteensä 12p


Pistejakauma
------------

0  ***
3  *
4  *
5  **
6  *
7  *
8  ******
9  *****
10 ****
11 ***
12 *********


Esimerkkiratkaisu
-----------------

/* Ohjelmoinnin perusteet, koe 6.6.2003/AW
 
   Tehtävän 4 esimerkkiratkaisu
   Binäärihaku toimii vain järjestetyn taulukon kanssa. Siten tehtävänä 
   on toteuttaa metodit 

   o järjestä(int[] taulu) 
   o binHae(int[] taulu, int haettava)

   sekä vuorovaikutteinen pääohjelmametodi.

   Antti Vähäkangas
*/
public class Teht4 {

    private static void vaihtoJarjesta(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;
		}
    }

    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
    }

    
    public static void main(String[] args) {
	int lkm = -1;              // Montako lukua luetaan?
	int[] taulu = null;        // Luvut luetaan tänne
	boolean jatka = true;      // Jatketaanko lukujen kyselyä

	// Luetaan syötettävien lukujen lkm
	do {
	    System.out.print("Montako lukua syötetään (max 1000)? ");
	    lkm = Lue.kluku();
	} while(lkm < 0 || lkm > 1000);
	
	taulu = new int[lkm];

	// Luetaan luvut
	for (int i=0; i<taulu.length; ++i) {
	    System.out.print("Anna " + (i+1) + ". luku: ");
	    taulu[i] = Lue.kluku();
	}

	// Järjestetään taulukko
	vaihtoJarjesta(taulu);

	// Kysellään lukuja
	while (jatka) {
	    System.out.println("e - etsintä");
	    System.out.println("l - lopetus");
	    System.out.print("Valintasi: ");
	    char merkki = Lue.merkki();
	    if (merkki=='l')
		jatka=false;
	    if (merkki=='e') {
		System.out.print("Anna etsittävä luku: ");
		if (binHae(taulu, Lue.kluku()) != -1)
		    System.out.println("Luku on taulukossa");
		else
		    System.out.println("Luku ei ole taulukossa");
		
	    }
	}
	
    }
      
}