viikko5.html

---
layout: material
title: Viikko 5
---
<p>
	Viikon teemana on hajautusrakenteiden ja yleisemmin hajautuksen soveltaminen.
</p>

<div class="exercise" id="t1">

	<header>
		<h1>Tehtävä 1</h1>
	</header>

	<div>

		<p>
			Sinulle on annettu taulukko kokonaislukuja,
        ja tehtäväsi on selvittää,
        onko taulukossa kahta lukua, joiden summa on
			<code>x</code>
			.
		</p>

		<p>
			Esimerkiksi jos taulukko on {3, 4, 2, 8} ja
			<code>x</code>
			on 5,
        voidaan valita luvut 3 ja 2.
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>boolean etsiSumma(int[] luvut, int x)</code>
		</p>

		<p>
			Taulukko
			<code>luvut</code>
			sisältää 1..10 <sup>5</sup>
			kokonaislukua väliltä –10 <sup>9</sup>
			..10
			<sup>9</sup>
			.
        Luku
			<code>x</code>
			on kokonaisluku väliltä –10
			<sup>9</sup>
			..10
			<sup>9</sup>
			.
		</p>

		<p>
			Metodin tulee palauttaa
			<code>true</code>
			,
        jos summan saa kahdesta luvusta,
        ja muuten
			<code>false</code>
			.
		</p>

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>etsiSumma(new int[] {1, 2, 3}, 5)</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>etsiSumma(new int[] {1, 2, 3}, 6)</code>
					</td>
					<td>
						<code>false</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>etsiSumma(new int[] {1, 3, 3}, 6)</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>etsiSumma(new int[] {1, 2, 3}, 6)</code>
					</td>
					<td>
						<code>false</code>
					</td>
				</tr>
			</tbody>
		</table>
	</div>
</div>
<div class="exercise" id="t2">

	<header>
		<h1>Tehtävä 2</h1>
	</header>

	<div>

		<p>
			Uolevi on äärettömässä ruudukossa ja lähtee
        liikkeelle ruudusta (0, 0).
        Hän kulkee joka askeleella yhden ruudun
        vasemmalle, oikealle, ylöspäin tai alaspäin.
        Milloin Uolevi palaa ruutuun, jossa hän on ollut aiemmin
        (mihin tahansa matkan varrella olleeseen ruutuun)?
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>int reitinPituus(String reitti)</code>
		</p>

		<p>
			Parametri
			<code>reitti</code>
			kuvaa Uolevin reitin.
        Se sisältää järjestyksessä suunnat, joihin Uolevi liikkuu.
        Jokainen suunta on yksi merkeistä V, O, Y ja A.
        Merkkijonon pituus on 1..10
			<sup>5</sup>
			merkkiä.
		</p>

		<p>
			Metodin tulee palauttaa, montako askelta Uolevi liikkuu,
        ennen kuin hän palaa uudestaan samaan ruutuun.
        Jos Uolevi ei palaa koskaan samaan ruutuun reitin aikana,
        metodin tulee palauttaa 0.
		</p>

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>reitinPituus("YYVVAAOO")</code>
					</td>
					<td>
						<code>8</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>reitinPituus("YVAOYVAO")</code>
					</td>
					<td>
						<code>4</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>reitinPituus("YYYYYYYY")</code>
					</td>
					<td>
						<code>0</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>reitinPituus("OYVVAOOO")</code>
					</td>
					<td>
						<code>6</code>
					</td>
				</tr>
			</tbody>
		</table>
	</div>
</div>
<div class="exercise" id="t3">

	<header>
		<h1>Tehtävä 3</h1>
	</header>

	<div>

		<p>
			Sinulle on annettu taulukko sanoja,
        ja tehtäväsi on etsiä siitä suurin mahdollinen
        ryhmä anagrammeja eli sanoja,
        joissa on jokaista kirjainta yhtä monta.
		</p>

		<p>
			Esimerkiksi jos sanat ovat {"talo", "katu", "lato"},
        suurin ryhmä on {"talo", "lato"} ja siinä on kaksi sanaa.
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>int suurinRyhma(String[] sanat)</code>
		</p>

		<h2>Esimerkit</h2>

		<p>
			Sanojen määrä on 1..10
			<sup>5</sup>
			,
        ja jokaisessa sanassa on 1..10 kirjainta
        väliltä a..z.
		</p>

		<p>Metodin tulee palauttaa suurimman ryhmän koko.</p>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>suurinRyhma(new String[] {"apina", "banaani", "cembalo"}</code>
					</td>
					<td>
						<code>1</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>suurinRyhma(new String[] {"talo", "katu", "lato"}</code>
					</td>
					<td>
						<code>2</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>suurinRyhma(new String[] {"ab", "ab", "ba", "ba"}</code>
					</td>
					<td>
						<code>4</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>suurinRyhma(new String[] {"iines", "otto", "sieni", "toto"}</code>
					</td>
					<td>
						<code>2</code>
					</td>
				</tr>
			</tbody>
		</table>
	</div>
</div>
<div class="exercise" id="t4">

	<header>
		<h1>Tehtävä 4</h1>
	</header>

	<div>

		<p>
			Sinulle on annettu DNA-ketju,
        joka muodostuu merkeistä A, C, G ja T.
        Tehtäväsi on selvittää,
        kuinka pitkä on lyhin DNA-ketju, joka ei ole
        annetun ketjun osajonona.
		</p>

		<p>
			Esimerkiksi DNA-ketju ACGTACGT
        sisältää osajonona kaikki 1:n pituiset
        DNA-ketjut eli A, C, G ja T.
        Kahden pituiset osajonot ovat järjestyksessä
        AC, CG, GT, TA, AC, CG ja GT,
        eli esimerkiksi ketju AA puuttuu osajonoista.
        Niinpä lyhimmän ketjun pituus on 2.
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>int lyhinPuuttuva(String mjono)</code>
		</p>

		<p>
			Merkkijono
			<code>mjono</code>
			on
        DNA-ketju, jonka pituus on 1..10
			<sup>5</sup>
			merkkiä.
		</p>

		<p>
			Metodin tulee palauttaa lyhimmän ketjun pituus,
        joka ei ole osajonona annetussa ketjussa.
		</p>

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>lyhinPuuttuva("CCCCCCCC")</code>
					</td>
					<td>
						<code>1</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>lyhinPuuttuva("ACGTACGT")</code>
					</td>
					<td>
						<code>2</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>lyhinPuuttuva("ACAAGCAG")</code>
					</td>
					<td>
						<code>1</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>lyhinPuuttuva("ACACACGT")</code>
					</td>
					<td>
						<code>2</code>
					</td>
				</tr>
			</tbody>
		</table>

		<p> <strong>VINKKI:</strong>
			javan String.substring(beginIndex, endIndex) metodista saattaa olla hyötyä.
		</p>
	</div>
</div>
<div class="exercise" id="t5">

	<header>
		<h1>Tehtävä 5</h1>
	</header>

	<div>

		<p>
			Sinulle on annettu DNA-ketju,
        ja tehtäväsi on etsiä siitä pisin osajono,
        jossa on yhtä monta jokaista merkkiä A, C, G ja T.
		</p>

		<p>
			Esimerkiksi ketjussa ACGTACGT
        pisin osajono on koko ketju,
        jossa on 2 kertaa jokaista merkkiä.
        Vastaavasti ketjussa TTATCGTT
        pisin osajono on ATCG,
        jossa on kerran jokaista merkkiä.
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>int pisinTasainen(String mjono)</code>
		</p>

		<p>
			Merkkijono
			<code>mjono</code>
			sisältää DNA-ketjun,
        jonka pituus on 1..10
			<sup>5</sup>
			merkkiä.
		</p>

		<p>
			Metodin tulee palauttaa pisimmän osajonon pituus,
        jossa on jokaista merkkiä yhtä monta.
        Jos mitään tällaista osajonoa ei ole,
        metodin tulee palauttaa 0.
		</p>

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>pisinTasainen("ACGTACGT")</code>
					</td>
					<td>
						<code>8</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>pisinTasainen("CAATGTCG")</code>
					</td>
					<td>
						<code>8</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>pisinTasainen("TTATCGTT")</code>
					</td>
					<td>
						<code>4</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>pisinTasainen("AAAAAAAA")</code>
					</td>
					<td>
						<code>0</code>
					</td>
				</tr>
			</tbody>
		</table>
	</div>
</div>