Janne Korhonen, 31.10.2006

Ohjelmoinnin perusteet, kurssikoe

Tehtävä 3 - pisteytys ja mallivastaus

Tee ohjelma, joka ensin kysyy syötettävien kokonaislukujen lukumäärän, 
pyytää yksi kerrallan tuon määrän lukuja ja sijoittaa ne yksitellen 
taulukkoon. Luettuaan luvut ohjelma tarjoaa seuraavan palvelun:

Ohjelmalta kysytään lukuja yksi kerrallaan ja ohjelma selvittää, 
löytyykö luku taulukosta. Etsimiseen on käytettävä binäärihakua. Kaikkien
syöttölukujen on oltava arvoltaan välillä 1-100000, paitsi kyselyiden 
loppuminen ilmaistaan syöttämällä kysytyksi luvuksi luku 0.

Saat olettaa, että kaikki syötteet annetaan kelvollisina kokonaislukuina.
Syöttölukujen arvot on kuitenkin tarkastettava ja mahdollisista virheistä
ilmoitettava.

Pisteytys

Pisteytyksen kannalta tehtävä oli jaettu osatehtäviin, joista jokaisesta
sai erikseen pisteitä. Osiosta sai täydet pisteet kunhan koodissa oli 
toteutettu kaikki osiossa halutut asiat. Puutteet ja selkeät virheet 
vähensivät osiosta saatujen pisteiden määrää. Pienistä kirjoitus- yms. 
virheistä ei juurikaan vähennetty pisteitä.

Vastausten odotettiin olevan suunnilleen seuraavan mallin mukaisia. 
Yleensä järjestysalgoritmi ja binäärihaku olivat omat metodinsa, mutta 
muuten kaikki muu tehtiin päämetodissa.

Pyydetään käyttäjältä luettavien lukujen määrä
Luo taulukko
Jokaista taulukon alkiota kohden
	Toista
		Pyydä luku
		Tarkista luku
	Kunnes luku on väliltä 1-100000
Järjestä taulukko
Toista
	Pyydä käyttäjältä luku
	Jos luku on välillä 0-100000
		Suorita binäärihaku
	Muuten ilmoita virheestä
Kunnes käyttäjä on syöttänyt nollan

Osiot

Osio 1: Yleisrakenne & muu - 2p
 -Java-luokan yleinen rakenne, päämetodin määrittely ja metodikutsut 

Osio 2: Taulukon luonti ja lukujen lukeminen taulukkoon - 3p
 -Taulukon pituuden pyytäminen ja taulukon luonti (1p), lukujen kysely 
  taulukkoon (1p) ja taulukkoon menevien lukujen koon tarkastaminen (1p).
  Taulukon pituuden tarkastamisen unohtamisesta ei sakotettu, koska 
  tehtävän saattoi helposti tulkita niin, ettei kyseistä tarkistusta vaadittu.

Osio 3: Järjestäminen - 4p
 -Toteutettiin jokin algoritmi, joka järjesti taulukon tai piti sen koko ajan
  järjestyksessä uusia lukuja syötettäessä. Jos järjestys teki taulukon
  eri järjestykseen (nouseva vs. laskeva) kuin binäärihaku oletti, vähennettiin -2p.

Osio 4: Lukujen hakemisen silmukka - 3p
 -Käyttäjältä pyydettiin luku, jonka tarkistettiin olevan välillä 0-100000 (1p).
  Kun saatiin sopiva luku, tehtiin binäärihaku ja kerrottiin tulos 
  käyttäjälle (1p). Tätä toistettiin, kunnes käyttäjä syötti luvun 0 (1p).

Osio 5: Binäärihaku - 4p
 -Toteutettiin toimiva binäärihaku. Yleisin virhe oli indeksien ja alkioiden
  sekoittaminen jossain kohdassa (-2p). Jos toteutti jonkin muun
  hakualgoritmin tästä osiosta sai korkeintaan 2p (ja yleensä ei
  pisteitä järjestyksestä).

Mallivastaus

import java.util.Scanner;

public class Tehtava3 {
	
	private static Scanner lukija = new Scanner(System.in);

	public static void main(String[] args) {
		
		int[] luvut = null;
		
		System.out.println("Ensin syötetään luvut taulukkoon.");
		System.out.println("Lukujen tulee olla väliltä 1-100000");
		System.out.println("\nKuinka suuren taulukon haluat?");
		
		// Kysytään taulukon koko
		do{
			int koko = lukija.nextInt();
			
			if(koko > 0)
				luvut = new int[koko];
			else
				System.out.println("Taulukon koon oltava positiivinen.");
		}while(luvut == null);
		
		// Pyydetään käyttäjältä luvut taulukkoon
		for(int i = 0; i < luvut.length; ++i){
			System.out.println("Anna luku "+i);
			do{
				luvut[i] = lukija.nextInt();
				if(luvut[i] < 1 || luvut[i] > 100000)
					System.out.println("Luvun oltava väliltä 1-100000");
			}while(luvut[i] < 1 || luvut[i] > 100000);
		}
		
		jarjesta(luvut);
		
		System.out.println("Nyt voit kysellä taulukosta lukuja. Nolla lopettaa.");
		
		// Lukujen kysely
		int syote;
		do{
			System.out.println("Anna haettava luku.");
			syote = lukija.nextInt();
			if (syote < 0 || syote > 100000)
				System.out.println("Haettavan luvun oltava väliltä 1-100000. Nolla lopettaa");
			else if (syote != 0){
				if(binHae(syote, luvut))
					System.out.println("Luku "+syote+" löytyi taulukosta!");
				else
					System.out.println("Lukua "+syote+" ei ole taulukossa.");
			}
		}while(syote != 0);
		
		System.out.println("Heihei!");
	}
	
	public static void jarjesta(int[] taulu){
		// Lisäysjärjestäminen
		for(int i = 1; i < taulu.length; ++i){
			int apu = taulu[i];
			int j = i;
			while (j > 0 && taulu[j-1] > apu){
				taulu[j] = taulu[j-1];
				--j;
			}
			taulu[j] = apu;
		}
	}
	
	public static boolean binHae(int luku, int[] taulu){
		int vasen = 0;
		int oikea = taulu.length - 1;
		int keski;
		
		while(vasen <= oikea){
			keski = (vasen+oikea)/2;
			if(taulu[keski] == luku)
				return true;
			else if(taulu[keski] > luku)
				oikea = keski-1;
			else if(taulu[keski] < luku)
				vasen = keski+1;
		}
		return false;
	}

}