7.4.oefeningen.md

Oefeningen 7.4 · Slide 111

Theorie

Oefening 7.4.1

Schrijf de algoritmen voor de publieke methodes invoegenNa, invoegenVoor en vervang in pseudo-code uit. Analyseer telkens de uivoeringstijd van het algoritme.

Implementatie van invoegenNa()

invoegenNa(I: p: geheel getal, x: Element) : /
    * Preconditie: de lisjt l bestaat en is nog niet vol.
    * Postconditie: het element x werd na de p-de positie ingevoegd in de lisjt l.
    * Gebruikt: /
BEGIN
    VOOR i = aantal TOT p + 2 STAP - 1 DOE
        data[i] <- data[i - 1]
    EINDE VOOR

    aantal <- aantal + 1

    data[p + 1] <- x
EINDE

Implementatie van invoegenVoor()

invoegenVoor(I: p: geheel getal, x: Element) : /
    * Preconditie: de lisjt l bestaat en is nog niet vol.
    * Postconditie: het element x werd voor de p-de positie ingevoegd in de lisjt l.
    * Gebruikt: /
BEGIN
    VOOR i = aantal TOT p + 1 STAP - 1 DOE
        data[i] <- data[i - 1]
    EINDE VOOR

    aantal <- aantal + 1

    data[p] <- x
EINDE

Oefening 7.4.2

Schrijf een nieuwe methode verwissel( ) voor lijsten. Deze methode verwisselt in een lijst l het element van een gegeven positie p1 met het element van een tweede gegeven positie p2.

Oefening a

Breid de klasse List uit met een publieke methode verwissel( ). Geef het algoritme voor deze methode in pseudo-code.

verwissel(I: p1, p2: geheel getal): /
    * Preconditie: de lisjt l bestaat
    * Postoncditie: het element op positie p1 in de lijst l werd verwisseld met het element op de positie p2
    * Gebruikt: /
BEGIN
    tmp <- data[p1]
    data[p1] <- data[p2]
    data[p2] <- tmp
EINDE

Oefening b

Maak enkel gebruik van de publieke methodes uit de klasse List voor het schrijven van het algoritme. Verwijs niet naar een eventuele implementatie. Geef het algoritme van de methode verwissel in pseudo-code.

verwissel(I: l: List, p1, p2: geheel getal): /
    * Preconditie: l is een lijst, p1 en p2 zijn bestaande posities van l
    * Postoncditie: het element op positie p1 in de lijst l werd verwisseld met het element op positie p2; de gewijzigde lisjt werd geretourneerd.
    * Gebruikt: geefElem, vervang
BEGIN
    tmp <- l.geefElem(p1)

    l.vervang(p1, l.geefElem(p2))
    l.vervang(p1, tmp)

    RETOUR (l) //Moet niet perse
EINDE

Oefening 7.4.3

Een veelterm kunnen we voorstellen a.d.h.v. een lijst. De lijst bevat alle coëfficiënten van de veelterm. Het eerste element van de lijst correspondeert met de coëfficiënt van de 0-de graadsterm, het tweede element met de coëfficiënt van de eerste graadsterm, enz.. Schrijf alle methodes uit de klasse Veelterm in pseudocode uit. Implementeer de klasse vervolgens in Java.

Veelterm
- coëfficiënten: List
+ Veelterm(n: geheel getal) + getGraad( ) : geheel getal + setCoëff(coëff : reëel getal, i: geheel getal) : / + getCoëff(i: geheel getal) : reëel getal + maakSom(v1: Veelterm, v2: Veelterm) : Veelterm

• De constructor maakt een lijst aan voor de opslag van de coëfficiënten van een veelterm die maximaal van de n-de graad kan zijn.
• De methode getGraad geeft de graad van de veelterm terug. Als het een ‘lege’ veelterm betreft dan is het resultaat van de methode - 1.
• De methode setCoëfficiënt wijzigt de veelterm zodat de coëfficiënt van de gegeven graadsterm gelijk is aan de gegeven coëfficiënt.
• De methode getCoëfficiënt geeft de coëfficiënt van de gegeven graadsterm terug.
• De methode maakSom maakt de som van twee gegeven veeltermen en geeft het resultaat terug.