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 edes jommasta kummasta taulukosta A tai B (siis niiden yhdisteen). Kukin alkio
esiintyy tulostaulukossa vain kertaalleen vaikka se esiintyisi molemmissa syötetaulukossa
tai jommassa kummassa syötetaulukossa useasti. Älä hyödynna valmiita joukkotyyppejä
tai niiden operaatioita äläkä muuta syötaulukoita tai niiden sisältöä. Piirrä ensin kuva on-
gelmasta, 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 muutet-
tavissa toimivaksi aliohjelmaksi (ohjelmointikielelle). Mikä on algoritmisi aikavaativuuden
kertaluokka? Voisiko sitä parantaa?


Kuva: A: [5 4 2 4], B: [1 6 2] -> Tulos: [5 4 2 1 6]

Versio 1:
Muodostetaan uusi tulostaulukko C. Käydään läpi taulukon A alkiot yksi
kerrallaan ja tarkastetaan löytyykö ko. alkiota taulukosta C. Jollei
löydy, lisätään ko. alkio tulostaulukkoon. Tehdään sama taulukolle B.

Versio 2:
Muodosta tulostaulukko C (kokoa ??)
Kullekin taulukon A alkiolle x tee seuraavaa:
	Tarkasta löytyykö x taulukosta C
	Jos löytyi:
		älä tee mitään
	Jos ei löytynyt:
		Lisää x tulostaulukkoon
Kullekin taulukon B alkiolle x tee seuraavaa:
	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 ja B  yhteensä)
tulosmäärä = 0
Kullekin taulukon A alkiolle x tee seuraavaa
	löytyi = epätosi
	Kullekin taulukon C alkiolle y tee seuraavaa
		Jos x on sama kuin y
			löytyi = tosi, lopeta sisempi toisto
	Jos löytyi on epätosi
		Aseta x aputulostaulukkoon kohdalle tulosmäärä
		tulosmäärä = tulosmäärä + 1
Kullekin taulukon B alkiolle x tee seuraavaa
	löytyi = epätosi
	Kullekin taulukon C alkiolle y tee seuraavaa
		Jos x on sama kuin y
			löytyi = tosi, lopeta sisempi toisto
	Jos löytyi 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|)^2)  (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.