BPS #8: Rekursiv zu Iterativ - Auswertung

Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Neue Antwort erstellen

Holzchopf

Meisterpacker

Betreff: BPS #8: Rekursiv zu Iterativ - Auswertung

 BeitragSo, Mai 29, 2011 10:46
Antworten mit Zitat
Benutzer-Profile anzeigen
Jetzt zeigt sich, wer in den Katakomben der Rekursion den Durchblick hatte!

Das war die Aufgabe

Postet hier eure Ergebnisse, Codes, Gedanken. Lernt von den anderen, seht euch deren Quelltext an und versucht euren eigenen zu verbessern.

Diskussion
Postet zu euren Codes stets eine kurze Erklärung mit euren Gedanken in denen ihr simpel gesagt die Frage "Wieso habe ich XY auf diese Art gelöst?" beantwortet. Beiträge, die nur den Code enthalten werden wir aus dem Thread entfernen.

Musterlösung:
BlitzMax: [AUSKLAPPEN] 
Local i:Int 

Print "Die beiden Funktionen der 1. Aufgabe werden mit Werten von 0 bis 15 gefüttert und das Ergebnis ausgegeben." 
For i = 0 To 15 
   Print i + " bsp_rekursiv: " + func1_rekursiv(i) + " bsp_iterativ: " + func1_iterativ(i) 
Next 

Print "Die beiden Funktionen der 2. Aufgabe werden mit Werten von 0 bis 15 gefüttert und das Ergebnis ausgegeben." 
For i = 0 To 15 
   Print i + " fib_rekursiv: " + fib_rekursiv(i) + " fib_iterativ: " + fib_iterativ(i) 
Next 


'Beispielfunktionen 
Function bsp_rekursiv(n:Int) 
   If n <= 0 Return 0 
   Return 1 + bsp_rekursiv(n - 1) 
End Function 

Function bsp_iterativ(n:Int) 
   Local a:Int 
   For Local i:Int = 1 To n 
      a:+1 
   Next 
   Return a 
End Function 

Function bsp_instant(n:Int) 
   Return Max(0, n) 
End Function 


'Funktionen der 1. Aufgabe 
Function func1_rekursiv(n:Int) 
   If n = 0 Return n 
   Return n + func1_rekursiv(n - 1) 
End Function 

Function func1_iterativ(n:Int) 
   Local a:Int 
   For Local i:Int = 1 To n 
      a:+i 
   Next 
   Return a 
End Function 

'Funktionen der 2. Aufgabe 
Function fib_rekursiv(x:Int) 
   If x = 0 Return 0 
   If x = 1 Return 1 
   Return fib_rekursiv(x - 1) + fib_rekursiv(x - 2) 
End Function 


Function fib_iterativ(n:Int) 
   Local a:Double = ((1 + Sqr(5)) / 2) ^ n 
   Local b:Double = ((1 - Sqr(5)) / 2) ^ n 
   Return (1 / Sqr(5)) * (a - b) 
End Function
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm
  • Zuletzt bearbeitet von Holzchopf am Di, Jun 14, 2011 19:53, insgesamt einmal bearbeitet

mpmxyz

 BeitragSo, Mai 29, 2011 11:37
Antworten mit Zitat
Benutzer-Profile anzeigen
BlitzMax: [AUSKLAPPEN] 
Function fib_iterativ(n:Int) 
   Local a:Double = ((1 + Sqr(5)) / 2) ^ n 
   Local b:Double = ((1 - Sqr(5)) / 2) ^ n 
   Return (1 / Sqr(5)) * (a - b) 
End Function

Ist das nicht eher "instant"?
Iterativ wäre das hier:
BlitzMax: [AUSKLAPPEN] 
Function fib_iterativ:Int(n:Int)
	If n = 0 Then Return 0 
	Local x0:Int=0
	Local x1:Int=1
	For Local i:Int=2 To n
		Local newX:Int=x0+x1
		x0=x1
		x1=newX
	Next
	Return x1
EndFunction

(Anmerkung durch Kommentarregel: Bei der Fibonacci-Folge werden zur Berechnung eines neuen Folgengliedes immer nur die beiden Vorgänger betrachtet. Also werden nur 2 Variablen + eine Tauschvariable gebraucht, um die Werte zu berechnen.)
Wenn ich gerade schon dabei bin:
BlitzMax: [AUSKLAPPEN] 
Function func1_iterativ(n:Int) 
   Local a:Int 
   For Local i:Int = 1 To n 
      a:+i 
   Next 
   Return a 
End Function

Dazu gibt es auch eine instant-Lösung.
BlitzMax: [AUSKLAPPEN] 
Function func1_instant:Int(n:Int)
	Return n*(n+1)/2
End Function

Meine Gedanken zu dem hier: "Der junge Gauß hatte einmal eine entsprechende Hausaufgabe elegant gelöst."
mfG
mpmxyz
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

BlitzMoritz

 BeitragSo, Mai 29, 2011 18:25
Antworten mit Zitat
Benutzer-Profile anzeigen
Zunächst die Lösung der beiden "Pflichtaufgaben", wobei mir angesichts ihrer Kürze und Einfachheit nicht mehr Erklärung notwendig erscheint als der Hinweis, dass man bei der iterativen Funktion jenen fortgeschrittenen Zustand, den man ansonsten als Argument der rekursiv aufgerufenen Funktion weitergeben würde, in einer separaten Variable speichert und ihn pro Schleifendurchgang aktualisiert. Bei den Fibonacci-Zahlen ist es ein Duo aus zwei solcher Variablen, die in einem "Ringtausch" weitergegeben werden.
Als jeweils dritte Funktion habe ich mir nicht nehmen lassen, weder Rekursionen noch Iterationen, sondern einfach die entsprechende Summenformel zu verwenden, von denen man die zur ersten Aufgabe leicht selbst herleiten kann und jene von Moivre-Binet im Wikipedia-Artikel über Fibonacci-Zahlen zu finden ist. Zuerst hatte ich bei der Formel von Moivre-Binet Bedenken, ob der (ungenaue) Floatwert für die Wurzel von Fünf Schwierigkeiten beim Ergebnis bereiten würde, welches ja aus einer natürlichen Integerzahl besteht, was sich allerdings überraschender Weise nicht herausstellte:
BlitzMax: [AUSKLAPPEN] 
'1.Aufgabe:

Function func1_rekursiv:Int(n:Int)
    If n = 0 Return n 
    Return n + func1_rekursiv(n - 1) 
End Function

Function func1_iterativ:Int(n:Int)
	Local sum:Int
    For Local i:Int = 1 To n
		sum:+i
	Next
	Return sum
End Function

Function func1_sumformula:Int(n:Int) 
    Return n*(n+1)/2
End Function

For Local i:Int = 0 To 15 
    Print "Summe natuerlicher Zahlen von 0 bis " + i + " Rekursiv/Iterativ/Summenformel: " + func1_rekursiv(i) + " = " + func1_iterativ(i) + " = " + func1_sumformula(i)
Next

'2.Aufgabe:

Function fib_rekursiv:Int(n:Int) 
    If n = 0 Return 0 
    If n = 1 Return 1 
    Return fib_rekursiv(n - 1) + fib_rekursiv(n - 2) 
End Function

Function fib_iterativ:Int(n:Int)
	If n = 0 Then Return 0
	Local duo:Int[] = [0,1]
	Local i:Int = 1
	While i < n
		Local new_second_duo_item:Int = duo[0] + duo[1]
		duo[0] = duo[1]
		duo[1] = new_second_duo_item
		i:+1
	Wend
	Return duo[1]
End Function

Function fib_MoivreBinetFormula:Int(n:Int) 
    Local SquareRoot5# = Sqr(5)
	Return ( ((1+SquareRoot5)/2.0)^n - ((1-SquareRoot5)/2.0)^n ) / SquareRoot5
End Function

For Local j:Int = 0 To 15 
    Print "Fibonacci-Zahl(" + j + ") Rekursiv/Iterativ/Formel von Moivre-Binet: " + fib_rekursiv(j) + " = " + fib_iterativ(j) + " = " + fib_MoivreBinetFormula(j)
Next

Nun zur selbst gestellten dritten Aufgabe, bei der ich mich dazu zwang, eine Rekursion, die sich nicht einmal, sondern zweimal selbst aufruft, ebenfalls durch eine iterative Funktion zu ersetzen.
Statt wie anfangs geschildert eine feste Anzahl von einer oder zwei Speichervariablen zu verwenden, verdoppelte sich hier die Anzahl der zu speichernden Informationen pro Iterationsschritt. Beim ersten Versuch sammelte ich sie in einer Liste, beim zweiten definierte ich ein Array, dessen Dimension ich pro Schleifendurchgang anpasste. Die Geschwindigkeitstests zeigen, dass die Listenvariante mehr als doppelt so langsam und die Array-Variante geringfügig langsamer ist als die ursprüngliche rekursive Funktion:
BlitzMax: [AUSKLAPPEN] 
SuperStrict

AppTitle = "Zur Fortsetzung eine Taste druecken:"
Graphics 800,600

Global MaxDepth% = 16 'Die Tiefe der Rekursion bzw. Iteration
'Hier nun die variierbaren Daten der beiden jeweils neuen Äste im Vergleich zum vorigen Ast:
Global DistanceFactor#[] = [0.7, 1.0] 'Abstand
Global LengthFactor#[] = [0.8, 0.7]	 'Länge
Global AngleAddition%[] = [-45, 30]	 'Winkeländerung

	'REKURSIV:

Function Bush_rekursiv(x%, y%, angle%, length%, Rekursion% = 0)
	SetColor Rand(0,192), Rand(64,255), 0
	DrawLine x, y, x + length * Cos(angle), y + length * Sin(angle)
	If Rekursion < MaxDepth Then
		Bush_rekursiv(x + DistanceFactor[0] * length * Cos(angle), y + DistanceFactor[0] * length * Sin(angle), angle + AngleAddition[0], length * LengthFactor[0], Rekursion + 1)
		Bush_rekursiv(x + DistanceFactor[1] * length * Cos(angle), y + DistanceFactor[1] * length * Sin(angle), angle + AngleAddition[1], length * LengthFactor[1], Rekursion + 1)
	End If		
End Function

Local time:Int = MilliSecs()
Bush_rekursiv(320, 550, 300, 160)
Print "Bush_rekursiv() brauchte " + (MilliSecs()-time) + " Millisekunden"
Flip
WaitKey()
Cls

	'ITERATIV inklusive LISTEN:

Function Bush_iterativ_list(x%, y%, angle%, length%)
	Local LineList:TList = CreateList()
	ListAddLast(LineList, [x, y, angle, length])
	For Local iteration% = 0 To MaxDepth
		Local NewLineList:TList = CreateList()
		For Local array%[] = EachIn LineList
			SetColor Rand(0,255), Rand(0,255), 0
			DrawLine array[0], array[1], array[0] + array[3] * Cos(array[2]), array[1] + array[3] * Sin(array[2])
			ListAddLast(NewLineList, [Int(array[0] + DistanceFactor[0] * array[3] * Cos(array[2])), Int(array[1] + DistanceFactor[0] * array[3] * Sin(array[2])), array[2] + AngleAddition[0], Int(array[3] * LengthFactor[0])])
			ListAddLast(NewLineList, [Int(array[0] + DistanceFactor[1] * array[3] * Cos(array[2])), Int(array[1] + DistanceFactor[1] * array[3] * Sin(array[2])), array[2] + AngleAddition[1], Int(array[3] * LengthFactor[1])])
		Next
		ClearList(LineList)
		LineList = NewLineList
	Next	
End Function

time = MilliSecs()
Bush_iterativ_list(320, 550, 300, 160)
Print "Bush_iterativ_list() brauchte " + (MilliSecs()-time) + " Millisekunden"
Flip
WaitKey()
Cls

	'ITERATIV inklusive ARRAYs:

Function Bush_iterativ_power(x%, y%, angle%, length%)
	Local data%[1, 4]
	data[0, 0] = x
	data[0, 1] = y
	data[0, 2] = angle
	data[0, 3] = length
	For Local iteration% = 0 Until MaxDepth
		Local power% = 2^iteration
		Local new_data%[power*2, 4]
		Local count%
		For Local d% = 0 Until power
			SetColor Rand(0,255), Rand(0,255), 0
			DrawLine data[d, 0], data[d, 1], data[d, 0] + data[d, 3] * Cos(data[d, 2]), data[d, 1] + data[d, 3] * Sin(data[d, 2])
			new_data[count, 0] = data[d, 0] + DistanceFactor[0] * data[d, 3] * Cos(data[d, 2])
			new_data[count, 1] = data[d, 1] + DistanceFactor[0] * data[d, 3] * Sin(data[d, 2])
			new_data[count, 2] = data[d, 2] + AngleAddition[0]
			new_data[count, 3] = data[d, 3] * LengthFactor[0]
			count:+1
			new_data[count, 0] = data[d, 0] + DistanceFactor[1] * data[d, 3] * Cos(data[d, 2])
			new_data[count, 1] = data[d, 1] + DistanceFactor[1] * data[d, 3] * Sin(data[d, 2])
			new_data[count, 2] = data[d, 2] + AngleAddition[1]
			new_data[count, 3] = data[d, 3] * LengthFactor[1]
			count:+1
		Next
		data = new_data
	Next
	'Die zuletzt gezeichneten Aeste muessen nicht mehr gespeichert werden,
	'daher kann dieser abgespeckte Auszug aus der vorigen Schleife extrahiert:
	For Local d% = 0 Until 2^MaxDepth
		SetColor Rand(0,255), Rand(0,255), 0
		DrawLine data[d, 0], data[d, 1], data[d, 0] + data[d, 3] * Cos(data[d, 2]), data[d, 1] + data[d, 3] * Sin(data[d, 2])
	Next
End Function

time = MilliSecs()
Bush_iterativ_power(320, 550, 300, 160)
Print "Bush_iterativ_power() brauchte " + (MilliSecs()-time) + " Millisekunden"
Flip
WaitKey()

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group