| datum |
laatst gewijzigd op dinsdag 21 april 2009, laatst gepubliceerd op woensdag 28 april 2010 |
| broncode |
Download Recursie.vb of Recursie.cs |
| hoofdstuk |
7. 8. 9.  |
| onderwerp |
8.13. 8.14. Recursie 9.1.  |
| rubrieken | 






|
Dit artikel is gepubliceerd op woensdag 28 april 2010 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
8.14.1. FaculteitsberekeningOm de faculteit te berekenen van een bepaald getal zouden we onderstaand programma kunnen schrijven.
Enkele voorbeelden van faculteitsberekening : - de faculteit van 5 : 5! = 5 x 4 x 3 x 2 x 1 = 120
- de faculteit van 4 : 4! = 4 x 3 x 2 x 1 = 24
- de faculteit van 3 : 3! = 3 x 2 x 1 = 6
- de faculteit van 2 : 2! = 2 x 1 = 2
- de faculteit van 1 : 1! = 1 = 1 Uitzonderlijk geval : - de faculteit van 0 : 0! = 1 Visual Basic Broncode Module Example1
Sub Main()
Console.WriteLine(GetFaculty(0))
Console.WriteLine(GetFaculty(1))
Console.WriteLine(GetFaculty(2))
Console.WriteLine(GetFaculty(3))
Console.WriteLine(GetFaculty(4))
Console.WriteLine(GetFaculty(5))
Console.ReadLine()
End Sub
Function GetFaculty(ByVal value As Integer) As Integer
GetFaculty = 1
For factor As Integer = value To 2 Step -1
GetFaculty *= factor
Next
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 1
1
2
6
24
120 Aan de hand van een iteratie structuur kunnen we de faculteit van een bepaald getal bepalen door alle gehele getallen kleiner en gelijk aan dat bepaalde getal en groter dan één ( of groter dan nul ) met elkaar te gaan vermenigvuldigen.
Een alternatieve oplossing is ook mogelijk, namelijk gebruik maken van "recursie".
Recursie wordt technisch gezien bekomen door een method in bepaalde situaties zichzelf te laten aanroepen.
Recursie is bruikbaar wanneer je een probleem kan oplossen door eerst een kleiner deelprobleem op te lossen.
Het voordeel van recursie is dat je hiermee vaak de code korter en eleganter kan maken.
Werkwijze om recursie te gebruiken :
1. bedenk hoe het probleem vereenvoudigd kan worden tot een kleiner analoog deelprobleem 2. zoek naar het/de trivia(a)l(e) geval(len) ( situatie(s) waarin er geen vereenvoudiging meer kan of nodig is door het op te lossen met een kleiner analoog deelprobleem )
Laten we de werkwijze uitdiepen door terug te keren naar ons voorbeeld van faculteitsberekening.
Het oorspronkelijke probleem is dat we de faculteit van een bepaald getal moeten kunnen bepalen.
We gaan na of we dit met recursie kunnen oplossen door te kijken of we het probleem kunnen vereenvoudigen door eerst een kleiner ( analoog ) deelprobleem op te lossen. 5! = 5 x 4 x 3 x 2 x 1 = 120
4! = 4 x 3 x 2 x 1 = 24 Als we een goed kijken naar de voorbeelden dan zie je dat het bepalen van de faculteit van 5 en 4 grotendeels gelijk is, maar er bij het bepalen van de faculteit van 5 enkel nog een vermenigvuldiging met 5 zelf bovenop komt.
We kunnen de faculteit van 5 dus bepalen, door eerst de faculteit van 4 te bepalen en vervolgens met 5 te vermenigvuldigen : Dezelfde redenering gaat ook op voor een aantal andere getallen : 4! = 4 x 3! = 4 x 6 = 24
3! = 3 x 2! = 3 x 2 = 6
2! = 2 x 1! = 2 x 1 = 2
1! = 1 x 0! = 1 x 1 = 1 In het algemeen kun je dus stellen dat : Nogmaals : het probleem van de faculteit van een bepaald getal ( bv 5 ) te bepalen kan dus vereenvoudigd worden door eerst een kleiner analoog deelprobleem op te lossen, namelijk de faculteit van dat bepaald getal verminderd met 1 te bepalen ( bv 4 ).
De redenering gaat niet meer op voor 0, want de faculteit van 0 is gewoon simpelweg 1. Dit is dus het triviaal geval, gezien we hier het probleem van de faculteit te bepalen van 0, niet meer kunnen vereenvoudigen door eerst de faculteit van 0 verminderd met 1 te bepalen.
Het bepalen van de faculteit van dat bepaald getal verminderd met 1 is een analoog deelprobleem omdat het ook het bepalen van de faculteit van een getal is.
Het bepalen van de faculteit van dat bepaald getal verminderd met 1 is een kleiner deelprobleem omdat het dichter aanleunt bij het triviaal geval. "Kleiner" hoef je dus niet letterlijk te nemen, maar met "kleiner deelprobleem" bedoeld men dus een deelprobleem die dichter aanleunt bij het/de trivia(a)l(e) geval(len). Het bepalen van de faculteit van 4 is dus een kleiner deelprobleem voor het bepalen van de faculteit van 5, omdat 4 dichter aanleunt bij 0.
De recursieve oplossing zou er dus als volgt kunnen uitzien : Visual Basic Broncode Module Example2
Sub Main()
Console.WriteLine(GetFaculty(0))
Console.WriteLine(GetFaculty(1))
Console.WriteLine(GetFaculty(2))
Console.WriteLine(GetFaculty(3))
Console.WriteLine(GetFaculty(4))
Console.WriteLine(GetFaculty(5))
Console.ReadLine()
End Sub
Function GetFaculty(ByVal value As Integer) As Integer
If value = 0 Then
GetFaculty = 1
Else
GetFaculty = value * GetFaculty(value - 1)
End If
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 1
1
2
6
24
120 Ga altijd na in de recursieve implementatie of de uitvoeringsinstantie zich in een triviaal geval bevindt ( dus hier controleren : value = 0 ), om in dat geval de triviale waarde op te leveren ( bij functies ) of de triviale actie uit te voeren ( bij procedures ) ( dus hier triviale terugkeerwaarde 1 instellen : GetFaculty = 1 ). Bevindt men zich niet in het triviaal geval, dan kan recursief gewerkt worden, door de terugkeerwaarde te baseren op de terugkeerwaarde in het analoog "kleiner" geval ( bij functies ) of door de actie uit breiden met de actie voor het analoog "kleiner" geval ( bij procedures ).
Zoals reeds gesteld werd kan men dus zowel recursieve functies als procedures creëren.
Bovenstaande recursieve oplossing is niet korter in aantal regels dan de niet recursieve variant, met andere probleem-stellingen zal dit echter wel vaak het geval zijn. Visual Studio : In Visual Studio kan men in het Call Stack-toolvenster goed constateren welke uitvoeringsinstantie welke andere uitvoeringsinstantie aanroept. Terug naar boven 8.14.2. Bepalen van de Grootste Gemene DelerDe "grootste gemene deler" van 2 getallen x en y, met |x| >= |y| is :
1. |x| als y = 0 2. |y| als |x| mod |y| = 0 3. = grootste gemene deler van |y| en ( |x| mod |y| ) ( als niet 1. of 2. ) Visual Basic Broncode Module Example3
Sub Main()
Console.WriteLine(GetCommonDivisor(3, 9))
Console.WriteLine(GetCommonDivisor(3, -9))
Console.WriteLine(GetCommonDivisor(8, 3))
Console.WriteLine(GetCommonDivisor(-3, -8))
Console.WriteLine(GetCommonDivisor(6, 0))
Console.WriteLine(GetCommonDivisor(0, 6))
Console.WriteLine(GetCommonDivisor(8, 12))
Console.WriteLine(GetCommonDivisor(9, 9))
Console.ReadLine()
End Sub
Function GetCommonDivisor(ByVal value1 As Integer, _
ByVal value2 As Integer) As Integer
If value1 < 0 Then
GetCommonDivisor = GetCommonDivisor( value1, value2)
ElseIf value2 < 0 Then
GetCommonDivisor = GetCommonDivisor(value1, value2)
ElseIf value1 < value2 Then
GetCommonDivisor = GetCommonDivisor(value2, value1)
ElseIf value2 = 0 Then
GetCommonDivisor = value1
Else
GetCommonDivisor = GetCommonDivisor(value2, value1 Mod value2)
End If
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 3
3
1
1
6
6
4
9 Als je de uitvoeringsinstanties bekijkt voor de aanroep op regel (1) met bovenstaande implementatie, dan zie je hoe :
GetCommonDivisor(-3, -8) wordt gebaseerd op : GetCommonDivisor(3, -8) wordt gebaseerd op : GetCommonDivisor(3, 8) wordt gebaseerd op : GetCommonDivisor(8, 3) wordt gebaseerd op : GetCommonDivisor(3, 8 Mod 3) ( of dus GetCommonDivisor(3, 2) ) wordt gebaseerd op : GetCommonDivisor(2, 3 Mod 2) ( of dus GetCommonDivisor(2, 1) ) wordt gebaseerd op : GetCommonDivisor(1, 2 Mod 1) ( of dus GetCommonDivisor(1, 0) ) wat resulteert in : 1
Deze keer wordt het resultaat van 1 uitvoeringsinstantie rechtstreeks gebaseerd op het resultaat van de aangeroepen uitvoeringsinstantie. Terug naar boven
8.14.3. MachtsverheffingOok machtsverheffing kan recursief geïmplementeerd worden.
Als triviaal geval zou je exponent 0 kunnen nemen, want eender welk getal tot de 0de macht is 1.
Bij een positieve exponent kan je stellen dat : X ^ Y = X * ( X ^ ( Y - 1 ) ) Bij een negatieve exponent kan je stellen dat : Visual Basic Broncode Module Example4
Sub Main()
Console.WriteLine(GetPower(2, 3))
Console.WriteLine(GetPower(2, 2))
Console.WriteLine(GetPower(2, 1))
Console.WriteLine(GetPower(2, 0))
Console.WriteLine(GetPower(2, -1))
Console.WriteLine(GetPower(2, -2))
Console.WriteLine(GetPower(2, -3))
Console.ReadLine()
End Sub
Function GetPower(ByVal base As Integer, _
ByVal exponent As Integer) As Integer
If exponent = 0 Then
GetPower = 1
ElseIf exponent > 0 Then
GetPower = base * GetPower(base, exponent - 1)
ElseIf exponent < 0 Then
GetPower = 1 / GetPower(base, -exponent)
End If
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 8
4
2
1
0.5
0.25
0.125 Terug naar boven
8.14.4. FibonacciDe "Fibonacci"-reeks is een reeks van getallen die begint met 2 maal het getal 1, elk daarop volgend getal is gelijk aan de som van de vorige 2 getallen uit de reeks.
Fibonaccireeks : 1 1 2 3 5 8 13 21 34 55 ...
Als we een functie zouden willen schrijven voor het bepalen van een bepaald getal - gebaseerd op de rang - uit deze reeks ( Function GetFibo(ByVal ordinal As Integer) As Integer ) zouden we recursief te werk kunnen gaan.
Om het tiende fibonaccigetal te bepalen, kunnen we eerst 2 analoge kleinere deelproblemen oplossen, namelijk het bepalen van het achtste ( 21 ) en het negende ( 34 ) fibonaccigetal, om deze vervolgens op te tellen en tot het tiende fibonaccigetal te komen ( 55 ).
Triviaal is hier het opvragen van het eerste of tweede fibonaccigetal, deze kunnen niet bepaald worden door eerst een kleiner analoog deelprobleem op te lossen, maar deze zijn simpelweg 1. Visual Basic Broncode Module Example5
Sub Main()
Console.WriteLine(GetFibo(1))
Console.WriteLine(GetFibo(2))
Console.WriteLine(GetFibo(3))
Console.WriteLine(GetFibo(4))
Console.WriteLine(GetFibo(5))
Console.WriteLine(GetFibo(6))
Console.WriteLine(GetFibo(7))
Console.WriteLine(GetFibo(8))
Console.WriteLine(GetFibo(9))
Console.WriteLine(GetFibo(10))
Console.ReadLine()
End Sub
Function GetFibo(ByVal ordinal As Integer) As Integer
If ordinal = 1 OrElse ordinal = 2 Then
GetFibo = 1
ElseIf ordinal > 2 Then
GetFibo = GetFibo(ordinal - 1) + GetFibo(ordinal - 2)
End If
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 1
1
2
3
5
8
13
21
34
55 Efficiënt is echter anders, een te groot aantal uitvoeringsinstanties moet worden uitgevoerd vooraleer het uiteindelijke resultaat kan bepaald worden.
Voor het recursief bepalen van het eerste of tweede fibonaccigetal moet slechts 1 uitvoeringsinstantie worden uitgevoerd, voor het derde fibonaccigetal zijn dit reeds 3 uitvoeringsinstanties, voor het vierde fibonaccigetal zijn dit er 5, voor het vijfde fibonaccigetal zijn dit er 9, voor het zesde fibonaccigetal zijn dit er 15, voor het zevende fibonaccigetal zijn dit er 25, voor het achtste fibonaccigetal zijn dit er 41, voor het negende fibonaccigetal zijn dit er 67, voor het tiende fibonaccigetal zijn dit er 109, ... .
Dat wil dus bijvoorbeeld zeggen dat voor het bepalen van het tiende fibonaccigetal er 109 Integers in het geheugen worden gereserveerd.
Conclusie is dat niet alles wat recursief op te lossen valt ook perse zo moet worden geïmplementeerd, houd steeds ( de groei van ) het aantal uitvoeringsinstanties in het oog.
Een niet-recursieve oplossing valt hier te verkiezen : Visual Basic Broncode Module Example6
Sub Main()
Console.WriteLine(GetFibo(1))
Console.WriteLine(GetFibo(2))
Console.WriteLine(GetFibo(3))
Console.WriteLine(GetFibo(4))
Console.WriteLine(GetFibo(5))
Console.WriteLine(GetFibo(6))
Console.WriteLine(GetFibo(7))
Console.WriteLine(GetFibo(8))
Console.WriteLine(GetFibo(9))
Console.WriteLine(GetFibo(10))
Console.ReadLine()
End Sub
Function GetFibo(ByVal ordinal As Byte) As Integer
GetFibo = 1
If ordinal > 2 Then
Dim fibo1 As Short = 1
Dim fibo2 As Short = 1
Dim count As Byte = 2
Do Until count = ordinal
Dim backup As Integer = fibo2
fibo2 += fibo1
fibo1 = backup
count += 1
Loop
GetFibo = fibo2
End If
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 1
1
2
3
5
8
13
21
34
55 Terug naar boven
8.14.5. Quick SortEen van de meest performante "in-place" sorteermethoden is de "Quick Sort", die het eenvoudigst recursief te implementeren is.
Deze methode bestaat erin steeds ( middelste ) "pivot" element te bepalen, en de overige tabelelementen op basis van hun verhouding ten aanzien van de "pivot" te gaan pivoteren rond die "pivot".
Veronderstel volgende ongesorteerde tabel : indices : 0 1 2 3 4 5 6 7
waarden : 88 75 93 81 21 74 84 35 Bepaal een middelste element of middelste index : ( 0 + 7 ) \ 2 = 3. 81 is de "pivot" waarde ( element op index 3 ), deze "pivot" waarde plaatsen we aan de kant ( bijvoorbeeld achteraan de tabel door 81 en 35 van positie te wisselen ) : indices : 0 1 2 3 4 5 6 7
waarden : 88 75 93 35 21 74 84 81
pivotWe zoeken startende bij het begin van de tabel naar een waarde die groter is dan ( of gelijk aan ) de "pivot" waarde : indices : 0 1 2 3 4 5 6 7
waarden : 88 75 93 35 21 74 84 81
groter pivotEn startende bij het einde van de tabel naar een waarde die kleiner is ( of gelijk aan ) de "pivot" waarde : indices : 0 1 2 3 4 5 6 7
waarden : 88 75 93 35 21 74 84 81
groter kleiner pivotDeze waarde wisselen we van positie ( pivoteren ) : indices : 0 1 2 3 4 5 6 7
waarden : 74 75 93 35 21 88 84 81
pivotStartende bij de uit vorige stap bereikte posities zoeken we verder naar een kleinere en grotere waarde dan de "pivot" : indices : 0 1 2 3 4 5 6 7
waarden : 74 75 93 35 21 88 84 81
groter kleiner pivotOpnieuw wisselen we de waarden van positie ( pivoteren ) : indices : 0 1 2 3 4 5 6 7
waarden : 74 75 21 35 93 88 84 81
* pivotBij het verder zoeken naar een grotere waarde dan de "pivot" komen we aan de positie waar het laatst een kleinere waarde dan de "pivot" werd gevonden ( index 4 ). Verder ( op hogere indices ) naar een grotere waarde dan de "pivot" zoeken heeft geen zin, gezien we daar enkel waarden gaan terugvinden die ten opzichte van de "pivot" reeds juist gepivoteerd zitten.
Met andere woorden : we weten dat voor index 4 elementen zitten die kleiner zijn of gelijk aan de "pivot" waarde en vanaf index 4 elementen zitten die groter zijn of gelijk aan de pivot waarde. De "pivot" kan nu terug op zijn juiste positie worden geplaatst ( index 4 ) : indices : 0 1 2 3 4 5 6 7
waarden : 74 75 21 35 81 88 84 93 81 zit juist dus hebben we nog 2 ongesorteerde delen : deel 1 : deel 2 :
indices : 0 1 2 3 5 6 7
waarden : 74 75 21 35 88 84 93 Om deze ongesorteerde delen verder te sorteren kunnen we dezelfde werkwijze gebruiken, of dit dus als een analoog kleiner deelprobleem beschouwen.
Als het ongesorteerde deel minder groot is dan 3 elementen ( 0, 1 of 2 elementen ) kan/hoeft dezelfde werkwijze niet worden toegepast, en bevinden we ons dus in triviale gevallen : Visual Basic Broncode Module QuickSort
Sub Main()
Dim numbers As Integer() = {88, 75, 93, 81, 21, 74, 84, 35}
PrintArray(numbers)
QuickSort(numbers, 0, 7)
PrintArray(numbers)
Console.ReadLine()
End Sub
Sub PrintArray(ByVal values As Integer())
For Each value As Integer In values
Console.Write(value & " ")
Next
Console.WriteLine()
End Sub
Sub QuickSort(ByVal array As Integer(), _
ByVal lowerbound As Integer, ByVal upperbound As Integer)
Dim count As Integer = upperbound - lowerbound + 1
If count = 2 Then
If array(lowerbound) > array(upperbound) Then
Dim backup As Integer = array(lowerbound)
array(lowerbound) = array(upperbound)
array(upperbound) = backup
End If
ElseIf count > 2 Then
Dim pivotIndex As Integer = (lowerbound + upperbound) \ 2
Dim pivot As Integer = array(pivotIndex)
array(pivotIndex) = array(upperbound)
array(upperbound) = pivot
Dim smallerIndex As Integer = lowerbound
Dim biggerIndex As Integer = upperbound
Do While smallerIndex <> biggerIndex
Do While array(smallerIndex) <= pivot AndAlso _
smallerIndex < biggerIndex
smallerIndex += 1
Loop
Do While array(biggerIndex) >= pivot AndAlso _
smallerIndex < biggerIndex
biggerIndex -= 1
Loop
If smallerIndex <> biggerIndex Then
Dim backup As Integer = array(smallerIndex)
array(smallerIndex) = array(biggerIndex)
array(biggerIndex) = backup
End If
Loop
array(upperbound) = array(biggerIndex)
array(biggerIndex) = pivot
QuickSort(array, lowerbound, biggerIndex - 1)
QuickSort(array, smallerIndex + 1, upperbound)
End If
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 88 75 93 81 21 74 84 35
21 35 74 75 81 84 88 93 Terug naar boven
8.14.6. BacktrackingOm sommige problemen op te lossen ( zoals het "N Dames Probleem" ) moet men tijdens het zoeken naar een oplossing terugkeren naar een vorige gevonden deeloplossing. Dit terugkeren wordt ook wel "backtracking" genoemd. Visual Basic Broncode Module NQueensProblem
Const N As Integer = 8
Dim chessBoard(N - 1, N - 1) As Boolean
Sub Main()
If CanSolve(N) Then
Console.WriteLine("A solution is found :")
DrawChessBoard()
Else
Console.WriteLine("No solution is found.")
End If
Console.ReadLine()
End Sub
Sub DrawChessBoard()
Console.Write("+")
For col As Integer = 0 To N - 1
Console.Write("---+")
Next
Console.WriteLine()
For row As Integer = 0 To N - 1
Console.Write("|")
For col As Integer = 0 To N - 1
If HasQueen(row, col) Then
Console.Write(" Q |")
Else
Console.Write(" |")
End If
Next
Console.WriteLine()
Console.Write("+")
For col As Integer = 0 To N - 1
Console.Write("---+")
Next
Console.WriteLine()
Next
Console.WriteLine()
End Sub
Function CanSolve(ByVal queens As Integer) As Boolean
If queens = 0 Then
CanSolve = True
Else
Dim col As Integer = N - queens
Dim rowToTry As Integer = 0
Do
If IsUnderAttack(rowToTry, col) Then
rowToTry += 1
Else
PlaceQueen(rowToTry, col)
Console.WriteLine("Trying :")
DrawChessBoard()
CanSolve = CanSolve(queens - 1)
If Not CanSolve Then
RemoveQueen(rowToTry, col)
Console.WriteLine("Backtracking to :")
DrawChessBoard()
rowToTry += 1
End If
End If
Loop Until CanSolve OrElse Not IsLegalPosition(rowToTry, col)
End If
End Function
Function IsUnderAttack(ByVal row As Integer, ByVal col As Integer) As Boolean
IsUnderAttack = IsUnderAttack(row, col, -1, -1) OrElse _
IsUnderAttack(row, col, +1, -1) OrElse _
IsUnderAttack(row, col, 0, -1)
End Function
Function IsUnderAttack(ByVal row As Integer, ByVal col As Integer, _
ByVal rowOffSet As Integer, ByVal colOffSet As Integer) As Boolean
Do
row += rowOffSet
col += colOffSet
Loop While IsLegalPosition(row, col) AndAlso Not HasQueen(row, col)
IsUnderAttack = HasQueen(row, col)
End Function
Function HasQueen(ByVal row As Integer, ByVal col As Integer) As Boolean
HasQueen = IsLegalPosition(row, col) AndAlso chessBoard(row, col)
End Function
Function IsLegalPosition(ByVal row As Integer, ByVal col As Integer) As Boolean
IsLegalPosition = row >= 0 AndAlso row <= N - 1 AndAlso col >= 0 AndAlso col <= N - 1
End Function
Sub PlaceQueen(ByVal row As Integer, ByVal col As Integer)
chessBoard(row, col) = True
End Sub
Sub RemoveQueen(ByVal row As Integer, ByVal col As Integer)
chessBoard(row, col) = False
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Voor N = 3 : Visual Basic Output Trying :
+---+---+---+
| Q | | |
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
Trying :
+---+---+---+
| Q | | |
+---+---+---+
| | | |
+---+---+---+
| | Q | |
+---+---+---+
Backtracking to :
+---+---+---+
| Q | | |
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
Backtracking to :
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
Trying :
+---+---+---+
| | | |
+---+---+---+
| Q | | |
+---+---+---+
| | | |
+---+---+---+
Backtracking to :
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
Trying :
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
| Q | | |
+---+---+---+
Trying :
+---+---+---+
| | Q | |
+---+---+---+
| | | |
+---+---+---+
| Q | | |
+---+---+---+
Backtracking to :
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
| Q | | |
+---+---+---+
Backtracking to :
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
No solution is found. Voor N = 4 : Visual Basic Output Trying :
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Trying :
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | Q | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Backtracking to :
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Trying :
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | Q | | |
+---+---+---+---+
Trying :
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | Q | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | Q | | |
+---+---+---+---+
Backtracking to :
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | Q | | |
+---+---+---+---+
Backtracking to :
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Backtracking to :
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Trying :
+---+---+---+---+
| | | | |
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Trying :
+---+---+---+---+
| | | | |
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | Q | | |
+---+---+---+---+
Trying :
+---+---+---+---+
| | | Q | |
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | Q | | |
+---+---+---+---+
Trying :
+---+---+---+---+
| | | Q | |
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | Q |
+---+---+---+---+
| | Q | | |
+---+---+---+---+
A solution is found :
+---+---+---+---+
| | | Q | |
+---+---+---+---+
| Q | | | |
+---+---+---+---+
| | | | Q |
+---+---+---+---+
| | Q | | |
+---+---+---+---+ Terug naar boven
8.14.7. OefeningenOpgave :
Breid onderstaande programmacode uit met de recursieve functie GetRowToZero. Visual Basic Broncode Module Exercise1Task
Sub Main()
Console.ReadLine()
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 5 4 3 2 1 0
-3 -2 -1 0
0 Oplossing : Visual Basic Broncode Module Exercise1Solution
Sub Main()
Console.WriteLine(GetRowToZero(5))
Console.WriteLine(GetRowToZero(-3))
Console.WriteLine(GetRowToZero(0))
Console.ReadLine()
End Sub
Function GetRowToZero(ByVal value As Integer) As String
If value = 0 Then
GetRowToZero = 0
ElseIf value < 0 Then
GetRowToZero = value & " " & GetRowToZero(value + 1)
Else
GetRowToZero = value & " " & GetRowToZero(value - 1)
End If
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Opgave : Breid onderstaande programmacode uit met de recursieve functie GetRow. Visual Basic Broncode Module Exercise2Task
Sub Main()
Console.ReadLine()
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output -2 -1 0 1
1 Oplossing : Visual Basic Broncode Module Exercise2Solution
Sub Main()
Console.WriteLine(GetRow(2, -3))
Console.WriteLine(GetRow(0, 2))
Console.WriteLine(GetRow(-3, -4))
Console.ReadLine()
End Sub
Function GetRow(ByVal value1 As Integer, _
ByVal value2 As Integer) As String
If value1 > value2 Then
GetRow = GetRow(value2, value1)
ElseIf value2 - value1 < 2 Then
GetRow = ""
Else
GetRow = (value1 + 1) & " " & GetRow(value1 + 1, value2)
End If
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Opgave : Breid onderstaande programmacode uit met de recursieve procedure PlaceSteps. Visual Basic Broncode Module Exercise3Task
Sub Main()
Console.WriteLine()
Console.WriteLine()
Console.ReadLine()
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 1
1
3
3
3
1
3
3
3
1
1 Oplossing : Visual Basic Broncode Module Exercise3Solution
Sub Main()
PlaceSteps(2)
Console.WriteLine()
PlaceSteps(10)
Console.WriteLine()
PlaceSteps(11)
Console.ReadLine()
End Sub
Sub PlaceSteps(ByVal distance As Integer)
Dim stepDistance As Integer
If distance = 1 Then
stepDistance = 1
Console.WriteLine(stepDistance)
Else
If distance >= 3 Then
stepDistance = 3
ElseIf distance >= 1 Then
stepDistance = 1
End If
Console.WriteLine(stepDistance)
PlaceSteps(distance - stepDistance)
End If
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Opgave : Breid onderstaande programmacode uit met de recursieve functie BinarySearch. Die via de "Binary Search" methode op zoek gaat naar een bepaald getal in een gesorteerde tabel. Visual Basic Broncode Module Exercise4Task
Sub Main()
Dim numbers As Integer() = {1, 3, 4, 7, 9, 10, 11, 15, 18, 20}
Dim number, lowerbound, upperbound As Integer
Dim found As Boolean
number = 15
lowerbound = 0
upperbound = 9
Console.WriteLine(found)
number = 18
lowerbound = 0
upperbound = 7
Console.WriteLine(found)
Console.ReadLine()
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output True
False Oplossing : Visual Basic Broncode Module Exercise4Solution
Sub Main()
Dim numbers As Integer() = {1, 3, 4, 7, 9, 10, 11, 15, 18, 20}
Dim number, lowerbound, upperbound As Integer
Dim found As Boolean
number = 15
lowerbound = 0
upperbound = 9
found = BinarySearch(number, numbers, lowerbound, upperbound)
Console.WriteLine(found)
number = 18
lowerbound = 0
upperbound = 7
found = BinarySearch(number, numbers, lowerbound, upperbound)
Console.WriteLine(found)
Console.ReadLine()
End Sub
Function BinarySearch(ByVal number As Integer, _
ByVal array As Integer(), _
ByVal lowerbound As Integer, _
ByVal upperbound As Integer) As Boolean
Dim middle As Integer = (lowerbound + upperbound) \ 2
If (number = array(middle)) Then
BinarySearch = True
Else
If (upperbound <= lowerbound) Then
BinarySearch = False
Else
If number > array(middle) Then
lowerbound = middle + 1
Else
upperbound = middle - 1
End If
BinarySearch = BinarySearch(number, array, lowerbound, upperbound)
End If
End If
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Opgave : Breid onderstaande programmacode uit met de recursieve procedure TowersOfHanoi.
De procedure zou moeten weergeven welke stappen moeten ondernomen worden om het "Torens van Hanoi"-probleem om te lossen.
In dit probleem moet een bepaald aan schijven - van verschillende grote - verplaatst worden. Dit vertrekkende van een bepaalde bronstaaf, via een bepaalde hulpstaaf, naar een bepaald doelstaaf. De beperkingen zijn hierbij dat je slechts 1 schijf per keer mag verplaatsen en dat je nooit een grotere schijf op een kleinere mag plaatsen.
Bij het probleem "Torens van Hanoi" is het de bedoeling op zoek te gaan naar het minimum aantal verplaatsingen.
Zorg ervoor dat de procedure afdrukt welke verplaatsingen moeten gebeuren. Visual Basic Broncode Module Exercise5Task
Sub Main()
Dim diskCount As Integer = 5
Dim source As Integer = 1
Dim help As Integer = 2
Dim destination As Integer = 3
Console.ReadLine()
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output from 1 to 3
from 1 to 2
from 3 to 2
from 1 to 3
from 2 to 1
from 2 to 3
from 1 to 3
from 1 to 2
from 3 to 2
from 3 to 1
from 2 to 1
from 3 to 2
from 1 to 3
from 1 to 2
from 3 to 2
from 1 to 3
from 2 to 1
from 2 to 3
from 1 to 3
from 2 to 1
from 3 to 2
from 3 to 1
from 2 to 1
from 2 to 3
from 1 to 3
from 1 to 2
from 3 to 2
from 1 to 3
from 2 to 1
from 2 to 3
from 1 to 3 Oplossing : Visual Basic Broncode Module Exercise5Solution
Sub Main()
Dim diskCount As Integer = 5
Dim source As Integer = 1
Dim help As Integer = 2
Dim destination As Integer = 3
TowersOfHanoi(diskCount, source, destination, help)
Console.ReadLine()
End Sub
Sub TowersOfHanoi(ByVal diskCount As Integer, _
ByVal source As Integer, ByVal destination As Integer, _
ByVal help As Integer)
If diskCount = 1 Then
Console.WriteLine("from " & source & " to " & destination)
Else
TowersOfHanoi(diskCount - 1, source, help, destination)
Console.WriteLine("from " & source & " to " & destination)
TowersOfHanoi(diskCount - 1, help, destination, source)
End If
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Opgave : Breid onderstaande programmacode uit met de recursieve functie GetFiboNumbers. Visual Basic Broncode Module Exercise6Task
Sub Main()
Dim fiboNumbers As Integer()
For Each fiboNumber As Integer In fiboNumbers
Console.Write(fiboNumber & " ")
Next
Console.ReadLine()
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output 1 1 2 3 5 8 13 21 34 55 Oplossing : Visual Basic Broncode Module Exercise6Solution
Sub Main()
Dim fiboNumbers As Integer()
fiboNumbers = GetFiboNumbers(10)
For Each fiboNumber As Integer In fiboNumbers
Console.Write(fiboNumber & " ")
Next
Console.ReadLine()
End Sub
Function GetFiboNumbers(ByVal ordinal As Integer) As Integer()
Dim fiboNumbers As Integer()
If ordinal = 1 Then
fiboNumbers = New Integer() {1}
ElseIf ordinal = 2 Then
fiboNumbers = New Integer() {1, 1}
ElseIf ordinal > 2 Then
fiboNumbers = GetFiboNumbers(ordinal - 1)
ReDim Preserve fiboNumbers(ordinal - 1)
fiboNumbers(ordinal - 1) = fiboNumbers(ordinal - 2) + _
fiboNumbers(ordinal - 3)
End If
GetFiboNumbers = fiboNumbers
End Function
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Dit artikel is gepubliceerd op woensdag 28 april 2010 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
Visual Basic 2008 & 2010 Boeken
Berichten
|