ITI0011:harjutus 18

Kirjeldus

Rekursiooniga tutvumiseks on soovitatav uurida:

http://pages.cs.wisc.edu/~vernon/cs367/notes/6.RECURSION.html

• Faktoriaal rekursiooniga https://mitpress.mit.edu/sicp/full-text/sicp/book/chapter-1/figs/fact-shape.gif
• Sama asja visualiseerimine java visualizeriga http://goo.gl/ByLxHY
• Fibonacci N'nda numbri saamise visualiseerimine: http://visualgo.net/recursion.html
• Soovi korral harjutamiseks: http://codingbat.com/java/Recursion-1

EX18 tarvis tuleb realiseerida 2 funktsiooni:

• maxAbsoluteValueInArray(int[], arrLength)

Näiteks [4,-5,1,-2] tagastab 5. Lahendus peaks kasutama rekursiivset loogikat, st funktsioon peab tagastama isennast. for ja while tsüklid pole lubatud. Näpunäiteid:

Oletame, et rivis on 4 inimest. Igaüks mõtleb ühe arvu, me tahame teada, kes mõtles kõige suurema arvu (ilma sohki tegemata). Info edastamiseks sosistatakse üksteisele kõrva. Saame kasutada järgnevat loogikat:

Esimene inimene rivis sosistab teisele, maksimaalne arv on max(1_inimese_arv, ülejäänud_rivi_max) Teine inimene, saab seda loogikat täiendada oma numbriga järgnevalt max(1_inimese_arv, max(2_inimese_arv,ülejäänud_rivi_max)) Kolmas inimene omakorda max(1_inimese_arv,max(2_inimese_arv,max(3_inimse_arv, ülejäänud_rivi_max))) Viimane teab, et ta on viimane ja tema ülesandeks on arvutada max(1_inimese_arv,max(2_inimese_arv,max(3_inimse_arv, 4_inimes_arv)))

Kui viimane saab arvutatud, siis ta saab sosistada eelviimasele vastuse, eelviimane üle-eelviimasele ja nii alguseni välja.

Arvudega

max(4, ülejäänud_rivi_max)
max(4, max(-5, ülejäänud_rivi_max))
max(4, max(-5, max(1, ülejäänud_rivi_max)))
max(4, max(-5, max(1, -2))) = 4

Absoluutväärtustega toimub analoogliselt.

• maxElementInArray(int[]), tagastab massiivi maksimaalse elemendi.

Tehke kindlasti esimesena maxABsoluteValueInArray, selle lahendamiseks mõelge loovalt ja kasutage array enda ruumi ajutiste väärtuste hoidmiseks

Mall

<source lang="java">

/**

* EX 18 Solution.
* @author <Your Name>
*/

public class EX18 {

public static void main(String[] args) { // Test here

System.out.println(maxElementInArray(new int[] { 12,4,2,1,9,11})); System.out.println(maxAbsoluteValueInArray(new int[] { 12,4,2,1,9,11, -14}, 7));

}

/** * * Returns absolute maximum (Distance from 0) value of an array RECURSIVELY. * Example * [4,2,1-5,-1] => 5 * @param arr * @param arrLength - array length when initialized * @throws IllegalArgumentException if arr is null or arrLength is negative * @return valueOfMaximumAbsoluteElement */ public static int maxAbsoluteValueInArray(int[] arr, int arrLength) throws IllegalArgumentException { // TODO: Implement return 0; }

/** * Returns maximum element of an array RECURSIVELY. * Example * [4,2,1-5-1] -> 4 * @param arr * @throws IllegalArgumentException if arr is null * @return valueOfMaximumElement */ public static int maxElementInArray(int[] arr) throws IllegalArgumentException { // TODO: Implement return 0; }

}

</source>