Tipps und eine Frage zu Rekursive-Art Aufgabe 4.4

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Tipps und eine Frage zu Rekursive-Art Aufgabe 4.4
[b][color=blue]hey,

hab heute schon mal nen Tutor gefragt wie er sich folgenden Side-Effekt (hab ich jetzt so definiert) vom Casten in Java erklärt… er hat leider auch keine Antwort gehabt…

Folgendes:

man kann die methode (eigentlich function oder routine) getNewY auf zwei unterschiedliche, aber richtige Arten (sofern man den Side-Effekt nicht kennt) coden:

(1) Programm funktioniert wie gewünscht:
[color=limegreen]


	public static int getNewY(int oldY, double len, double angle) {
		
		double new_y_wihtout_old=****code das mit dem DOUBLE angle und dem DOUBLE len und cosinus-sinus-fkt das neue y ausrechnet****	
		return (int)(new_y_wihtout_old+(double)oldY);
	}

[/color]

(2) Programm funktioniert nicht wegen Side-Effekt:
[color=red]


	public static int getNewY(int oldY, double len, double angle) {
		
		double new_y_wihtout_old=****code das mit dem DOUBLE angle und dem DOUBLE len und cosinus-sinus-fkt das neue y ausrechnet****	
		return (int)(new_y_wihtout_old)+oldY;//erst das neue y auf int casten und dann mit dem int oldY addieren-> sollte eigentlich das gleiche dabei herauskommen wie bei (1)
	}

[/color]

=> bei (2) Ausgabe von main von Class Art

checking getNewY with -4, 1.0, -0.9424777960769379, expected: -3, but was: -4 //Unterschied: -3 [-1] = -4
checking getNewY with -31, 1.5, -0.3141592653589793, expected: -29, but was: -30 //Unterschied: -29 [-1] = -30
checking getNewY with 4, 5.0, 4.084070449666731, expected: 1, but was: 2 //Unterschied: 1 [+1] = 2
recursiveArt incorrect

-1|-1|+1

Kann des sein, dass wenn man zu nem Double ein “ganzzahliges” anderes Double (lsg (1) oldY zu double gecastet) dazuaddiert,
dass sich das nach dem Komma verändert, was dann auch die Zahl vor dem Komma beeinflusst (weil beim anschließenden Cast zu int wird ja das nach dem komma einfach weggeworfen, so muss es schon vorher das vor dem komma geändert haben)

Und kann es sein, dass das vor dem Komma einmal kleiner und einmal größer wird, wegen -1|-1|+1 ?

Würde mich über ne Aufklärung des Side-Effekts freuen…

War übrigens sehr nervig, diesen Fehler zu finden, weil ich für getNewX auch erst mal analog zu (2) programmiert habe und da der Fehler nicht aufgetreten ist (wegen anderen Zahlen)
Sprich man fragt sich, wenn alles bei getnewX passt, wo dann der Fehler bei getnewY sein könnte, wenn es doch exakt so (analog zu (2)) gecoded ist (die Winkel halt etwas anders berechnet, aber vom Casten und so exakt gleich ist)?

Lg Knotenpunkt

[color=orange]PS:
Noch ein kleiner Tipp für die (Nicht-Tutoren,Dozenten )

bei canvas.drawLine(x, y, neuesX, neuesY, steps); darf beim letzten Rekursionsschritt der “steps” nicht 0 sein (sprich ihr müsst in euer if-else Konstrukt canvas.drawLine(…) geschickt einpflegen)
Die Aufgabe wäre an sich aber auch richtig, wenn steps=0 bei canvas.drawline(…) ist und das danach entsprechend implementiert ist
Problem ist nur, dass trotz der “Richtigkeit” dene ihr Test-Programm mal wieder viel zu unflexibel ist und die eben canvas.toString() nur für den Fall steps !=0 im letzten Rekursionsschritt abkontrollieren…
[/color]

[/color][/b]

3

meine augen bluten…

11 Likes
4

Nach dem Skript hat die Typumwandlung Vorrang gegenüber Multiplikation und Addition. Also wird zunächst der Intwert vom newYWithoutOld berechnet. Dieser Wert ist z. B. beim 1. Fall 0. Dann wird er zu yOld in int addiert. Es gehen somit einige Nachkommastellen verloren, wodurch Rundungsfehler entstehen.

(int) (0.5 + 0.7) = (int) 1.2 = 1
(int) 0.5 + (int) 0.7 = 0 + 0 = 0

5

So wird’s vielleicht besser.

Hier ist der eine Operand ja schon ein Int, daher sollte beim Abschneiden der Nachkommastellen immer das selbe rauskommen. Durch die Ungenauigkeit von [bei] Floats sind aber auch Ganzzahlen nicht exakt darstellbar, je nachdem was näher liegt ist das dann in etwa 0,9999 oder 1,0001 - beim Int-Cast wirkt sich das natürlich massiv aus.

5 Likes
6

Das erklärt das ganze zumindest teilweise

aber müsste,wenn 1 = 1,0001 ist nicht die zwei dann auch 2,0001 sein… oder warum kann es passieren, dass es dann 1,9999 ist… wegen -1|-1|+1 ?

achja arw: Farbe ist doch etwas schönes^^

7

Herrlich!

8

>>just like<<

noch eben die Farbe editiert, die vergessen wurde.

9

Klingt jetzt nicht allzu mysteriös:

double x = 1.999999999999999778;
System.out.println((int)(x+1) + " " + ((int)x+1));
10

Selten so einen Mist gelesen, ein double kann sogar mehr Ganzzahlen präzise darstellen als ein int :smiley: (natürlich weniger als ein long aber das ist hier nicht das Problem).

11

Ich sollte aufhören zu versuchen, Trollposts auf die schnelle ein wenig Sinn zu geben, wenn die Zeit zu spät für Sinnvolles ist… Ganzzahlen können in dem Bereich dargestellt werden, das war Müll (für sehr große Zahlen geht das irgendwann schief). Die fehlenden 0,00000xx ergeben sich wohl, da sich beim Addieren der (hier vermutlich größeren) Ganzzahl der Exponent ändert und dabei die letzten „Nachkommastellen“ der betragsmäßig kleineren Zahl verloren gehen (die werden ja dann für die Vorkommastellen gebraucht, bei IEEE Gleitkommaoperationen wird aber hinten nicht abgeschnitten, sondern gerundet). Und dann wäre man an dem Punkt, dass die durchs Runden verursachte Ungenauigkeit den Int-Cast verändert.

12

Da gibt es aber auch noch so etwas wie:

-4 + (int) 2.6 = -4 + 2 = -2 
(int) (-4 + 2.6) = (int) -1.4 = -1

Wird die Summe einer negativen Zahl und einer positiven Zahl gerechnet und kommt dabei etwas Negatives raus, dann wird durch das Casting der Wert vergrößert. Wird aber erst die positive Zahl gecastet, so wird sie verkleinert und dann wird sie zur negativen Zahl addiert, wodurch das Ergebnis um 1 kleiner als das andere ist. Analog ist das hier:

4 + (int) -2.6 = 2
(int) (4 + -2.6) = 1
13

Also vielleicht verstehe ich vor lauter „Farbe und bunt“ deinen Text falsch, aber:

  • Zitat Aufgabenstellung: „Der Parameter [m]steps[/m] gibt an, wieviele Ebenen noch zu zeichnen sind.“ → Quizfrage: wieviele Ebenen sind noch bei [m]steps=0[/m] zu zeichnen? Muss man also ueberhaupt noch [m]canvas.drawLine(…)[/m] aufrufen?
  • Die Aufgabe ist inkorrekt, wenn da das falsche passiert: deswegen schlaegt sowohl der gegebene oeffentliche Test absichtlich fehl (natuerlich auch die geheimen Testfaelle)
  • Das Ergebnis wird weder im ersten noch im letzten Rekursionsschritt getestet, sondern nach dem rekursiven Aufruf
14

dass das Ergebnis nach dem rekursiven Aufruf getestet wird, das ist schon klar

Aber hier ist ja schon etwas Objektorientierung dabei…

Die Zeichnung kann von den Strichenanzahl voll und ganz stimmen

Wird aber Canvas.drawline(…) mit steps=0; im letzten Schritt gezeichnet, dann hat das Objekt Canvas ein anderen Zustand… die Striche sind aber trotzdem alle korrekt gezeichnet (an der richtigen Stelle und die richtige Anzahl und der Baum sieht auch identisch aus)

Und der Testfall schlägt deswegen fehl, weil nacher der Objektzustand von Canvas kontrolliert wird und der eben intern anders ist wenn die letzten Striche mit steps=0 gezeichnet werden

15

Wenn du den richtigen Baum zeichnest, stimmt dir auch der Testfall zu. Wenn du aber mit [m]steps=0[/m] noch was zeichnest, machst du was falsch (falls das im letzten Post immer noch nicht offensichtlich genug war) und das bewertet der Testfall auch so.

16

Ich verstehe die Winkelberechnung einfach nicht bei dieses Aufgabe…
Man kriegt ja einen Winkel gegeben (0), damit zuerst eine gerade Linie nach oben gezeichnet wird. Nur wie wird dann der Winkel der “Äste”, die aus dem Stamm entstehen, berechnet?
Ich weiß Alpha gibt den Winkel zwischen dem linkem und rechtem an. Somit müsste(zu mindestens ohne den Randomfaktor) der Winkel von dem linkem Ast angle-openAngle/2 sein. Von dem nächstem Ast(also dem Ast der rechts davon liegt) müsste der Winkel, der Winkel vom linkem Ast sein + openAngle/(branches-1). Beim erneutem Aufruf müsste angle mit dem jeweils neuem Winkel(beim linkem z.B.“angle-openAngle/2”) übergeben werden und
mit dem jeweils neuem X,Y Wert und ohne dem Randomfaktor müsste die übergebene Länge ja einfach getNewLen(len) sein und steps um 1 verringert . Ist das richtig? Oder liegt bereits dort der Denkfehler?

Die Abbruchbedingung des rekursiven Aufrufs ist ja einfach dann, wenn Steps==1 ist und es wird dann einfach noch eine Reihe von Ästen gezeichnet werden und das war es dann…

Irgendwie kommt bei mir aber einfach nur was falsches raus… Bei mir werden anstatt 5 Äste nur 2 gezeichnet, obwohl ich die for-Schleife so definiert habe: int i=0; i<branches; i++. So müsste sie doch 5 mal durchlaufen und 5 mal recursiveArt 5 mal aufrufen, wenn branches=5 ist oder?

17

Klingt alles recht gut. Besuch am besten eine Rechneruebung und lass dir dort weiterhelfen.

18

Servus,

also wir kämpfen noch damit, das wir einen Strich zuviel einberechnen, aber egal an welcher dieser herauszurechnen ist, ist uns schleierhaft.

Der Normalfall läuft ohne Fehler und korrekt durch, sobald aber der Zufall mit ins Spiel kommt kriegen wir “recursiveArt incorrect” und einen zusätzlichen Strich (also statt wie in den Bildern 4 haben wir 5).

Mit was ist branches indiziert? Wenn ich branches oder steps irgendwo mit -1 angebe (ausser beim initialen rekursiven aufruf von recursiveArt) kommt irgendnen nonsense raus.

Vielleicht kann uns noch jemand einen Hinweis geben wos vielleicht hängen könnte.

19

Wenn ihr mit branch=0 anfangt und zum Vergleich die Variable branches benutzt, sollte es klappen.

20

was ja merkwürdig ist, ist, das wenn wir in den testfällen unten ind er main branch um eins reduzieren passt alles wunderbar…