Hoofdstuk 1. Week 3: Recursie. 1.1 Leesopdracht. 1.2 Eenvoudige recursie

Hoofdstuk 1 Week 3: Recursie 1.1

Leesopdracht

In Java Gently staat zeer weinig over recursie, de leesopdracht voor deze week bestaat dus alleen uit dit hoofdstuk van het dictaat.

1.2

Eenvoudige recursie

E´en van de krachtigste concepten in de Informatica is recursie. Tot nog toe hebben we alleen kennis gemaakt met methods die andere methods aanroepen. Er is dan een soort hi¨erarchie in methods. Het is ook mogelijk dat methods, al dan niet via een omweg, zichzelf aanroepen. Zo een method noemen we een recursieve method. Het redeneren over recursie gaat het makkelijkste als we onderscheid maken tussen: 1. de basisstap en 2. de recursieve stap Als we een probleem dat we met recursie aanpakken, dan bepalen we vooraf wat de basisstap en de recursiestap zijn. De basisstap bestaat uit een oplossing van het probleem in een simpele situatie waarin we het antwoord vrijwel direct kunnen opschrijven. Met recursiestappen proberen we het probleem stapsgewijs te reduceren tot de basisstap. Laten we een voorbeeld nemen. We willen n!, waarbij n ≥ 0 uitrekenen; d.w.z. 1 × 2 × 3 × · · · × (n − 1) × n. De basisstap ligt voor de hand; immers 0! is 1. Voor iedere andere waarde van n reduceren we het probleem. ( 1 voor n = 0 (basisstap) n! = (1.1) (n − 1)! × n voor n > 0 (recursiestap) Een mogelijke oplossing is gegeven in programma:

1

public static int faculteit( int n ){ if ( n == 0 ) return 1; else return n * faculteit( n-1 ); }

1.3

Tail-recursie

Het voorgaande probleem, het uitrekenen van faculteiten is een typisch probleem dat met tail-recursie (staart-recursie) is op te lossen. Tail-recursie kenmerkt zich doordat de recursieve method zichzelf ten hoogste eenmaal aanroept in het laatst uit te voeren statement van die method. Het laatst uit te voeren statement hoeft natuurlijk niet het laatste statement in de programmatekst van de method te zijn.

1.4

Recursie vs. iteratie

Tail-recursie is in feite een bijzondere vorm van herhaling, waarvan we de oplossing m.b.v. iteratie (d.w.z. met behulp van het while- of for-statement) de voorkeur verdient. public static int faculteit( int n ) { int fac = 1; for ( int i = 1 ; i <= n ; i++ ) fac *= i; return fac; } Bij iedere recursieve aanroep moet de nodige administratie verricht worden m.b.t. bijvoorbeeld de locale variabelen en parameters. Daarom heeft recursie een overhead t.o.v. iteratie. Het gebruik van recursie versus iteratie is meestal een afweging van schoonheid en duidelijkheid t.o.v. snelheid. 2

1.5

Machtsverheffen

Een ander voorbeeld van tail-recursie is het machtsverheffen. We zoeken een method voor het uitrekenen van xy waarbij y integer en y ≥ 0. We zouden voor het volgende algoritme kunnen kiezen: ( 1 voor y = 0 (basisstap) xy = (1.2) xy−1 · x voor y > 0 (recursiestap) Dit algoritme vraagt om y recursiestappen om xy te berekenen. Het volgende algoritme is slimmer:   voor y = 0 (basisstap) 1 y 2 y div 2 x = (x ) (1.3) voor y > 0 en y even (recursiestap)   y−1 x ·x voor y > 0 en y oneven (recursiestap) Dit algoritme vraagt om ongeveer Olog y recursiestappen om xy te berekenen. Dit laatste algoritme is dus beduidend effici¨enter. Het eerste algoritme berekent bijvoorbeeld 210 als 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2. Het laatste algoritme berekent 210 = (25 )2 = (24 · 2)2 = ((22 )2 · 2)2 . public static double macht( double x, int y ) { if ( y == 0 ) return 1.0; else if ( y % 2 == 0 ) return macht( x*x, y / 2 ); else return x * macht( x, y - 1 ); }

1.6

Afdrukken van een getal

Java kent verschillende methoden om een geheel getal naar de uitvoer te sturen. Hierbij wordt een integer getal omgezet in een rijtje ASCII-symbolen die afgedrukt worden. De 3

programmeurs van de standaard classes hebben dit probleem voor jullie opgelost. Veronderstel dat we dit nu zelf moeten programmeren, hoe doen we dat? We beschikken uitsluitend over een methode voor het afdrukken van characters. Het essenti¨ele probleem bij het afdrukken van getallen is dat we eerst het meest significante cijfer moeten afdrukken en vervolgens de minder significante cijfers, terwijl we met de operatie mod alleen het minst significante cijfer kunnen bekijken. Ergens in het algoritme moeten de cijfers in omgekeerde volgorde geplaatst worden. Deze verwisseling is zeer gemakkelijk recursief uit te voeren en met veel pijn en moeite iteratief. Het algoritme is simpel: 1. basisstap: getallen met 0 ≤ i < 10 drukken we direct af en 2. recursieve stap: van getallen met i ≥ 10 drukken we eerste recursief met WriteInt( i % 10 ) de eerste cijfers af en vervolgens het laatste cijfer. Een en ander resulteert in de method: public static void writeInt( int i ){ if (i < 10) System.out.print( i );

// basisstap; 1 cijfer

else { writeInt( i / 10 ); // recursie; meer cijfers System.out.print( i % 10 ); } }

1.7

De grootste gemene deler

Voor het uitrekenen van de grootste gemene deler van twee positieve getallen bestaat het Euclidische algoritme. Als de twee getallen gelijk zijn, dan is de grootste gemene deler gelijk aan het getal zelf. Als de twee getallen ongelijk zijn, dan kan men het kleinste getal van de grootste aftrekken; het zo gevormde paar getallen heeft dezelfde grootste gemene deler. Dit leidt tot het volgende recursieve algoritme:   voor x = y (basisstap) x (1.4) gcd(x, y) = gcd(x − y, x) voor x > y (recursiestap)   gcd(x, y − x) voor x < y (recursiestap) (gcd is een afkorting van greatest common divisor ) Laten we dit controleren aan de hand van een simpel voorbeeld. Neem twee getallen die het product van priemfactoren zijn; 4

bijvoorbeeld 2 · 2 · 5 · 13 = 260 en 7 · 13 = 91. De grootste gemene deler is nu 13. Bepaal nu met het Euclidische algoritme de grootste gemene deler van 260 en 91. We bepalen: gcd(260, 91). Trek de kleinste van de grootste af 260 − 91 = 169 dus gcd(260, 91) = gcd(169, 91). Dit zetten we voort: gcd(260, 91) = gcd(169, 91) = gcd(78, 91) = gcd(78, 13) = gcd(65, 13) = gcd(42, 13) = gcd(39, 13) = gcd(26, 13) = gcd(13, 13)

(1.5) (1.6)

Tot slot berekenen we gcd(13, 13). Nu zijn de twee getallen gelijk dus gcd(13, 13) = 13. Hieruit volgt gcd(260, 91) = 13. De code wordt dus: public static int gcd( int x, int y ) { if ( x == y ) return x; else if ( x < y ) return gcd( x, y-x ); else return gcd( x-y, x ); }

1.8

Schaakprobleem

Gegeven een schaakbord en een paard op een willekeurig veld. Bepaal voor ieder veld van het schaakbord in hoeveel paardesprongen dit veld vanuit het gegeven veld te bereiken is. Als we dit probleem willen aanpakken, met een z.g. top-down aanpak, dan moeten we het opbreken in kleinere deelproblemen. Een simpele opdeling is: • • • •

Zet het bord klaar Vraag de startpositie Bereken hoeveel sprongen nodig zijn Geef uitvoer

Dit kan b.v. leiden tot de volgende main() methode: 5

public static void main(String argv[]) { int xb,yb; Extractor invoer = new Extractor(); initBord(); System.out.print("Coordinaten beginpunt: "); xb = invoer.readInt(); yb = invoer.readInt(); sprong(xb,yb,0); printBord(); } Merk op dat we nog niets zeggen over hoe ieder van de onderdelen wordt opgelost, behalve het inlezen van de startpositie. We gaan nu ´e´en voor ´e´en de hiaten opvullen. Het simpelste is de initialisatie van het bord. We definie¨eren het bord als een 2-D array, waarop op iedere plaats het aantal sprongen van de kortste tot nu toe gevonden route wordt geadministreerd. Als we nog geen enkele route hebben gevonden, en zelfs het startpunt niet weten, gaan we ervan uit dat ieder punt in minder dan 2 miljoen zetten te bereiken is. Gezien de afmetingen van het bord moet dat lukken. We krijgen dan als code:

private static int[][] bord = new int[8][8]; // het bord public static void initBord() { int i,j; for ( i = 0; i <8; i++) for ( j = 0; j <8; j++) bord[i][j]=2000000; }

Het printen van het bord is ook simpel:

6

public static void printBord() { int x,y; for ( y = 7; y >=0; y--) { System.out.print((y+1) + "

");

for ( x = 0; x <8; x++) System.out.print(bord[x][y] + " "); System.out.println(); } System.out.println(); System.out.println("

a b c d e f g h");

}

Nu komt het lastigste: hoe berekenen we de kortste routes? Het idee is om dit recursief te doen. Stel we zijn na n sprongen op plek (x, y) terecht gekomen. Het eerste dat we moeten doen is kijken of we nog op het bord staan. Zo ja, dan moeten we kijken of de kortste route die tot nu toe gevonden is (gegeven door bord[x][y]) groter is dan n. Als dat het geval is, hebben we kennelijk een kortere route gevonden dan tot nu toe. We stellen dan eerst bord[x][y] gelijk aan n, en springen vanaf die positie in alle acht mogelijke richtingen, en herhalen daar de procedure voor al de niewe coordinaten, met n + 1 als aantal sprongen. In Java wordt dat

koper

zilver

goud

Figuur 1.1: Schematische voorstelling van de torens van Hanoi 7

public static void sprong( int x, int y, int lengte) { if (( x>=0 ) && (x<8) && ( y>=0 ) && (y<8) ) // we staan nog op het bord if (diepte < bord[x][y]) { bord[x][y] = lengte; lengte ++; sprong( sprong( sprong( sprong( sprong( sprong( sprong( sprong(

x-1, x+1, x-1, x+1, x-2, x+2, x-2, x+2,

y-2, y-2, y+2, y+2, y-1, y-1, y+1, y+1,

// kortere route gevonden

// administratie bijhouden // lengte pad ophogen // springen maar!! lengte); lengte); lengte); lengte); lengte); lengte); lengte); lengte);

} }

1.9

De torens van Hanoi

Een van de bekendste voorbeelden van recursie is de legende van de torens van Hanoi. Volgens de legende stonden er lang geleden voor de tempel van Hanoi drie zuilen, een koperen, een zilveren en een gouden zuil. Op de koperen zuil bevonden zich 100 schijven, de onderste de grootste, en van onder naar boven in grootte steeds afnemend, zodat nimmer een grotere op een kleinere schijf geplaatst was. Een oude monnik had zich tot taak gesteld deze schijven van de koperen zuil naar de gouden zuil te verhuizen, ´e´en voor ´e´en en er steeds voor zorgend dat geen grotere op een kleinere schijf geplaatst zou worden. De legende vertelt, dat het einde van de wereld bereikt zou zijn, indien de monnik zijn werk had voltooid. De monnik had snel in de gaten, dat ook de zilveren zuil nodig zou zijn en kwam na lang mediteren tot de volgende oplossing: 1. transporteer de bovenste 99 schijven van de koperen naar de zilveren zuil 2. transporteer de onderste, grootste, schijf van de koperen naar de gouden zuil 8

3. transporteer de 99 schijven nu van de zilveren zuil naar de gouden zuil. Hoewel de monnik stap 1. en stap 3. aan zijn oudste leerling opdroeg, zien we nu, dat we in feite voor deze stappen weer hetzelfde probleem tegenkomen, echter met 99 in plaats van 100 schijven en met de zuilen verwisseld. De oudste leerling van de monnik stelde aldus een vergelijkbaar algoritme op (met de zuilen verwisseld) en droeg zijn oudste leerling op het probleem van de 98 schijven op te lossen. Elke monnik krijgt de opdracht om n schijven van de van zuil naar de naar zuil te verplaatsen; eventueel door gebruik te maken van de via zuil. De monnik hoort van de opdrachtgever welk nummer correspondeert met respectievelijk de van, de via en de naar zuil. Elke monnik voerde in feite het volgende uit: • bestaat de toren uit meer dan ´e´en schijf, draag dan de oudste leerling op, de toren van aantal-1 schijven te verplaatsen van de van zuil naar de via zuil. • verplaats dan zelf de grootste schijf van de van naar de naar zuil. • bestaat de toren uit meer dan ´e´en schijf, draag dan de oudste leerling op, de toren van aantal-1 schijven te verplaatsen van de via zuil naar de naar zuil. Hieronder staat de gewenste uitvoer voor n = 4, waarbij als extra aanduiding de verdeling van de schijven, genummerd A t/m D in oplopende grootte, over de verschillende torens is weergegeven.

verhuis verhuis verhuis verhuis verhuis verhuis verhuis verhuis verhuis verhuis verhuis verhuis verhuis verhuis verhuis

schijf schijf schijf schijf schijf schijf schijf schijf schijf schijf schijf schijf schijf schijf schijf

van van van van van van van van van van van van van van van

1 1 2 1 3 3 1 1 2 2 3 2 1 1 2

naar naar naar naar naar naar naar naar naar naar naar naar naar naar naar

2 3 3 2 1 2 2 3 3 1 1 3 2 3 3

DCBA DCB. DC.. DC.. D... DA.. DA.. D... .... .... B... BA.. BA.. B... .... ....

.... A... A... .... C... C... CB.. CBA. CBA. CB.. C... C... .... A... A... ....

De recursieve code wordt dan

9

.... .... B... BA.. BA.. B... .... .... D... DA.. DA.. D... DC.. DC.. DCB. DCBA

public class Hanoi { public static void hanoi ( int n, int van, int via, int naar ) { if ( n > 0 ) { // Verplaats n-1 stenen naar de hulp toren // ’via’ met ’naar’ als hulp toren hanoi( n -1, van, naar, via ); // Schrijf de zet op die nodig is om de // onderste steen te verplaatsen System.out.println("verhuis schijf van " + van + " naar " + naar ); // Verplaats n-1 stenen van de hulp toren // ’via’ naar ’naar’ met ’van’ als hulp hanoi(n-1, via, van, naar); } } public static void main(String argv[]) { hanoi(4,1,2,3); } }

1.10

Welke atomen passen in een molecuul

Een probleem dat verwant is aan het z.g. knapzak probleem (dat jullie op het practicum krijgen) is dat van het vinden van alle combinaties van atomen, met bekende atoomgewichten, die een molecuul van een gegeven gewicht kunnen opleveren. We trekken ons hierbij 10

niets aan van chemische wetten. Laten we uitgaan van de volgende declaraties in de class Molecuul: import local.*; public class Molecuul{ private static class Atoom{ public String naam; public int nummer, massa; public Atoom( String n, int num, int m ){ naam = n; nummer = num; massa = m; } } public static Atoom[] atoomsoort; public static int aantal, combinatie[], mogelijkheden = 0; Dit levert ons declaraties van een lijst met elementen van de private class Atoom, de int aantal geeft de lengte van deze lijst. De array combinatie geeft het aantal van ieder atoom in de huidige combinatie, en mogelijkheden administreerd het aantal mogelijke moleculen dat tot nu toe gevonden is. We moeten deze variabelen natuurlijk wel initialiseren: public static void initAtoomsoort( String fnaam ){ FileExtractor invoer = new FileExtractor(fnaam); aantal = invoer.readInt(); invoer.readLine(); atoomsoort = new Atoom[aantal]; combinatie = new int[aantal]; for (int i=0; i < aantal; i++ ) atoomsoort[i] = new Atoom (invoer.readString(), invoer.readInt(), invoer.readInt() ); } 11

De volgende vraag is natuurlijk wanneer een combinatie een mogelijk molecuul opleverd. Dit is het geval als de som van de massa’s van alle atomen in de combinatie gelijk is aan het gezochte molecuulgewicht. Stel dat we een combinatie hebben gevonden. Dan moeten we eerst de teller van het aantal mogelijkheden verhogen, en we moeten natuurlijk het molecuul ook een beetje aardig weer kunnen geven. Dit gebeurt in de methode printMolecuul: public static void printMolecuul(){ mogelijkheden ++; System.out.print( mogelijkheden + ": " ); for (int i=0; i 0 ){ System.out.print(" " + atoomsoort[i].naam ); if ( combinatie[i] > 1 ) System.out.print( " " + combinatie[i] ); } System.out.println(); } Het eigenlijke werk komt nu. Gegeven een molecuulmassa M , proberen we van de eerste atoomsoort met massa A alle mogelijke aantallen n die passen er in te stoppen (n = 0, 1, . . . , M/A), en we rekenen uit hoeveel van de molecumassa overblijft voor ieder van die mogelijke aantallen (M − nA). Daarna kijken we welke verschillende moleculen er te maken zijn met massa M − nA, met de resterende atoomsoorten. Dit is dus een kleinere versie van hetzelfde probleem dat we hadden! We zijn klaar als we aantal atoomsoorten hebben geprobeerd, en de overgebleven massa is nul. Dan moeten we dus printMolecuul aanroepen. De volgende method geeft het gewenste resultaat: public static void mogelijkeMoleculen( int massa, int index ){ if ( index == aantal ){ // basisstap if ( massa == 0 ) printMolecuul(); } else // recursiestap for ( int i = massa / atoomsoort[index].massa; i>=0 ; i-- ) { combinatie[index] = i; mogelijkeMoleculen( massa - i*atoomsoort[index].massa, index + 1 ); } } 12

De main method wordt simpelweg: public static void main (String argv[]) { int molecuulmassa; Extractor invoer = new Extractor(); initAtoomsoort( argv[0] ); System.out.print("Molecuulmassa: "); molecuulmassa = invoer.readInt(); mogelijkeMoleculen( molecuulmassa, 0 ); } Voor een invoerfile met atoomgewichten: 5 H C N O U

nummer 1 6 7 8 92

massa 1 12 14 16 238

Levert dit als uitvoer voor een molecuulmassa van 18: Molecuulmassa: <18> 1: H 18 2: H 6 C 3: H 4 N 4: H 2 O

13

1.11

Practicum 1 Week 3: Recursie

Opgave 1

(Te paard!)

Opgavenaam: Paard Deze opgave is een variant op het schaakprobleem in het hoorcollege. We laten een paard uit een schaakspel springen zoals hij dat gewend is. Het bord breiden we aanzienlijk uit: we bekijken een oneindig twee-dimensionaal bord (vraag: moet je dit implementeren?). De velden op het bord nummeren we als roosterpunten in een twee-dimensionaal assenstelsel. Onder een paardenroute verstaan we nu een rij punten P0 , P1 , ... , Pn waarbij voor elke i ∈ {1, ..., n} geldt dat Pi−1 → Pi een paardesprong is. We noemen n de lengte van zo’n route. Voorbeeld: (2, 1), (4, 2), (5, 0), (4, −2), (3, 0), (4, 2), (6, 1) is een paardenroute van lengte 6 van (2, 1) naar (6, 1).

einde voorbeeld

1. Ontwerp een (recursieve) method public static int nRoutes(xb,yb,xe,ye,n) die het aantal paardenroutes bepaalt van (xb, yb) naar (xe, ye) ter lengte n. 2. Een stuk code is gegeven in de file Paard.java die op de volgende bladzijde is afgedrukt. Implementeer de method in deze class, die de gebruiker de gelegenheid geeft begin- en eindpunt en de lengte van de route op te geven en dat vervolgens het aantal mogelijke routes bepaalt. Voorbeeld: Bepalen aantal paardenroutes Coordinaten beginpunt: 2 1 Coordinaten eindpunt: 6 1 Aantal stappen: 6 Aantal routes:

3540

3. Bepaal eens, zonder je programma te gebruiken, hoeveel paardenroutes er zijn van het punt (0,0) naar het punt (30,30) in 9 stappen. De naieve implementatie van de functie nRoutes heeft nogal wat rekentijd nodig om dit antwoord te vinden. Bedenk een eenvoudig te berekenen criterium waarmee je 14

kunt bepalen dat het eindpunt niet is te bereiken in het toegestane aantal stappen. Maak hiervan gebruik in een tweede versie van je programma. Bewaar ook je eerste oplossing en vergelijk de tijd die je twee oplossingen nodig hebben op het geval van 9 stappen van (0,0) naar (30,30). Het is deze meer efficiente oplossing die ter beoordeling moet worden ingestuurd. Er wordt ook gecontroleerd op de efficientie van je oplossing. import local.*; public class Paard{ public static int nRoutes( int xb, int yb, int xe, int ye, int lengte ) { // jullie moeten hier iets toevoegen }

public static void main(String argv[]){ int xb, yb, xe, ye; Extractor invoer = new Extractor(); System.out.println("Bepalen aantal paardenroutes"); System.out.print("Coordinaten beginpunt: "); xb = invoer.readInt(); yb = invoer.readInt(); System.out.print("Coordinaten eindpunt: xe = invoer.readInt(); ye = invoer.readInt();

");

System.out.print("Aantal stappen:

");

System.out.println("\nAantal routes: " + nRoutes(xb,yb,xe,ye, invoer.readInt())); } } 15

Opgave 2

(Maximale winst)

Opgavenaam: MaxWinst Hint: deze opgave heeft wel wat weg van het molecuul-gewicht probleem uit het hoorcollege. Als je als fabrikant een beetje succes wilt hebben, dan kun je er maar niet op los produceren. Je zult d´ıe zaken moeten produceren die de grootste winst opleveren. Maar daarbij zul je ook duidelijk rekening moeten houden met de beschikbare productiemiddelen (grondstoffen, arbeidskrachten, beschikbaarheid van de apparatuur etc.). Een zorgvuldige planning zal de totale winst moeten maximaliseren. In deze opgave geven we een aanzet tot een programma dat hierbij dienst kan doen. Om niet geheel te verdrinken in alle factoren waar rekening mee moet worden gehouden, maken we de volgende veronderstellingen. • Er is een lijst met alle mogelijke artikelen die door ons bedrijf geproduceerd kunnen worden. • Van elk artikel wordt in de periode waar de planning betrekking op heeft ten hoogste ´e´en exemplaar gefabriceerd. • Bij elk artikel is de netto winst bekend. • Er is slechts ´e´en productiefactor die beperkt beschikbaar is. • Bij elk artikel is bekend hoeveel van deze productiefactor nodig is. We maken gebruik van de tekst die aan het eind van deze set is afgedrukt. Ook zijn er twee voorbeeld invoerfiles aanwezig (artikelen1 en artikelen2) 1. Compileer de gegeven Java-file en voer de gegenereerde executable uit met als invoerparameter de gegeven file artikelen1. 2. Construeer een procedure die de ingelezen gegevens overzichtelijk afdrukt. 3. Construeer een function die bij een gegeven rij artikelgegevens de maximaal haalbare winst berekent, rekening houdend met de beschikbare hoeveelheid productiefactor. 4. Completeer het programma zo, dat de gebruiker de hoeveelheid beschikbare productiefactor kan invoeren en dat vervolgens de maximaal te behalen winst wordt afgedrukt. 5. Verwijder het afdrukken van de ingelezen gegevens uit je hoofdprogramma. Het resulterende programma leest dus de gegevens uit een file, maar vraagt aan de gebruiker (vanaf het toestenbord) de hoeveelheid beschikbare productiefactor. Tot slot wordt de maximaal haalbare winst afgedrukt. Zie ook het voorbeeld. Voorbeeld: met de geleverde file artikelen1 als invoerfile: Geef beschikbare hoeveelheid productiefactor: <14> Maximaal haalbare winst: 42 16

import local.*; public class MaxWinst{ private static class Product{ public String naam; public int winst; public int tijd; public Product( String n, int t, int w ){ naam = n; winst = w; tijd = t; } } public static Product[] assortiment; public static int grootte; public static void initAssortiment( String fnaam ){ FileExtractor invoer = new FileExtractor(fnaam); grootte = invoer.readInt(); invoer.readLine(); assortiment =

new Product[grootte];

for (int i=0; i < grootte; i++ ) assortiment[i] = new Product(invoer.readString(), invoer.readInt(), invoer.readInt() ); } public static int maxWinst(

int restTijd, int laatste ){

/* jullie code hier */ } public static void main (String argv[]){ int uren; Extractor invoer = new Extractor(); initAssortiment( argv[0] ); } }

17