Tietorakenteet ja algoritmit I
Harjoitus 1


3. Suunnittele huolella algoritmi joka saa parametrinaan kaksi kokonaislukutaulukkoa A
ja B ja joka luo ja palauttaa uuden kokonaislukutaulukon jossa on kaikki ne alkiot jotka
löytyvät molemmista taulukoista A ja B (siis niiden leikkauksen). Kukin alkio tulee tu-
lokseen vain kerran vaikka se esiintyisi molemmissa syötetaulukoissa useasti. Piirrä ensin
kuva ongelmasta, sitten kirjoita ylös ratkaisuperiaate selväsanaisesti suomeksi. Tämän
jälkeen ala täsmentämään ratkaisuperiaatetta täsmällisemmäksi algoritmiksi 1-3 vaiheessa
siten, että lopullinen ratkaisuperiaate on hyvin täsmällisesti kuvattu ja se on mekaanisesti
muutettavissa toimivaksi aliohjelmaksi. Älä muuta syötetaulukoita äläkä käytä valmiita
joukkotyyppejä apuna. Mikä on algoritmisi aikavaativuus? Voisiko sitä parantaa?



Kuva: A: [5 4 2 4], B: [2 4 4 6] -> Tulos: [2 4]
Algoritmin mukaan sitten kuvaan mukaan läpikäyntejä. Ja kuvia
erilaisista syötteistä.


Versio 1:

Muodostetaan uusi tulostaulukko C. Käydään läpi taulukon A alkiot yksi
kerrallaan ja tarkastetaan löytyykö ko. alkiota B ja jos löytyy, niin
löytyykö taulukosta C. Jos löytyy B, mutta ei löydy C lisätään ko. alkio
tulostaulukkoon.

Versio 2:

Muodosta tulostaulukko C (kokoa ??)
Kullekin taulukon A alkiolle x tee seuraavaa:
	Tarkasta löytyykö x taulukosta B
	Jos ei löydy:
		älä tee mitään
	Jos löytyi:
		Tarkasta löytyykö x taulukosta C
		Jos löytyi:
			älä tee mitään
		Jos ei löytynyt:
			Lisää x tulostaulukkoon
Palauta tulostaulukko

Versio 3:

aputulos = uusi taulukko (samankokoinen kuin A)
tulosmäärä = 0
Kullekin taulukon A alkiolle x tee seuraavaa
	löytyiB = epätosi
	Kullekin taulukon B alkiolle y tee seuraavaa
		Jos x on sama kuin y, niin:
			löytyiB = tosi, lopeta sisempi toisto
	Jos löytyiB on tosi, niin:
		löytyiC = epätosi
		Kullekin taulukon C alkiolle y tee seuraavaa
			Jos x on sama kuin y
				löytyiC = tosi, lopeta sisempi toisto
		Jos löytyiC on epätosi
			Aseta x aputulostaulukkoon kohdalle tulosmäärä
			tulosmäärä = tulosmäärä + 1

Luo uusi lopullinen tulostaulukko jonka koko on tulosmäärä
Kopio taulukon aputulos tulosmäärä ensimmäistä alkiota lopulliseen
tulostaulukkoon.
Palauta lopullinen tulostaulukko

Versio 4:

Tarkennetaan vielä lopullisen tulostaulukon kopiointi:
tulos = uusi taulukko (kokoa tulosmäärä)
Toista i = 0..tulosmäärä-1:
	lopullinentulostaulukko[i] = aputulos[i]


Aikavaativuus: O(|A|*|B|)  (taulukoiden alkiomäärien tulo).
Kurssin edetessä opitaan tehokkaampi tapa selvittää onko alkio x
taulukossa B jolloin aikavaativuus saadaan muotoon O(|A| + |B|), eli
_huomattavasti_ tehokkaammaksi jos taulukot ovat suuria.