BlueJ Rekursionshausaufgabe

V

vblaze0994

Neues Mitglied
Ich komme bei einer Hausaufgabe nicht weiter!
Wie ihr am Titel schon gesehen habt, geht es um Rekursion.
Die Aufgabe lautet :
"Ein Paar aus jeweils n zueinander parallelen Geraden schneidet sich. Wieviele Schnittpunkte gibt es für n = 37, wenn für n = 36 die Anzahl A der Schnittpunkte A(36) = 1296 beträgt? Wie könnte man allgemein die Anzahl der Schnittpunkte von n Geradenpaaren aus der Anzahl für n - 1 bestimmen? Bestimmen Sie eine rekursive Definition der Funktion A(n). Geben Sie ebenso die Abbruchbedingung an."

Also ein Beispiel, um es zu verdeutlichen:

Wenn n = 3 ist, dann sind damit 6 Geraden gemeint, 3 waagrecht und 3 vertikal, also gibt es 3 * 3 = 9 Schnittpunkte! - > Also mit n sind die GeradenPAARE gemeint.

Ich habe zwar die Lösung schon, aber ich weiß nicht wie man auf die Lösung kommt! Bitte kann mir einer erklären, wie man bei Rekursion logisch an die richtige Lösung gelangt?

Die Lösung ist als Quelltext geschrieben:

Java: 
public long schnittpunkt(long n)
    {
        if  (n < 2) {return 1;}
        else    {return n + (n-1) + schnittpunkt(n-1);}
    }
 
S

SlaterB

Gast
die Lösung findet sich wie zumeist abseits des PCs, suche Zettel + Stift,
male das Bild für n = 3 und 4 auf, schaue wie das 3er-Bild im 4er liegt, was kommt dazu? ein Rand aus 4 und 3 Schnittpunkten
 
S

SlaterB

Gast
was hast du dann verstanden? ;)
4er = 3er + 4 + 3
ner = (n-1)er + lange Reihe + fast so lange Reihe
schnittpunkt(long n) = schnittpunkt(n-1) + n + (n-1)
 
A

Andi_CH

Top Contributor
Wenn du weisst was eine Rekursion im mathmatischen Sinn ist, hast du es schon verstanden.

Das Beispiel Fakultät:

Für die Fakultät gilt f(x) = 1 * 2 * ......... * x und f(1) = 1;

Die Fakultät f(1) ist 1
Die Fakultät f(2) ist 1 * 2
Die Fakultät f(3) ist 1 * 2 * 3 und das ist doch (1 * 2) * 3 und das ist f(2) * 3

Jetzt bemerkst du sicher auch dass f(2) = f(1) * 2 ist und f(1) ist definiert als 1

Also gilt:
Code: 
f(x) = x * f(x-1)
und
Code: 
f(1) = 1
und jetzt kannst du das rekursiv programmieren

und das sieht dann so aus

Java: 
public class Fakultaet {

	public static int f(int x) {
		if (x==1) {
			return 1;
		} else {
			return x * f(x-1);
		}
	}

	public static void main(String[] args) {
		System.out.println("f(10) = " + f(10));
	}
}
Das grösste Problem und der häufigste Fehler ist, dass eine Rekrusion nie abbricht!

Also bei der oben wird f(x) als x * f(x-1) ausgedrückt, also wird x bei jedem Aufruf kleiner und irgendwann ist es 1 und dann wird kein rekursiver Aufruf mehr gemacht - die Rekursion bricht ab.

Super! Aber wir haben etwas vergessen!
Überleg mal was mit f(0) oder f(-42) passiert? Was muss noch vorgekehrt werden?
(die Fakultät für negative Zahlen ist nicht definiert und für 0 IMO auch nicht)

So - jetzt zu deinem Problem:

Jetzt musst du hingehen und das oben beschriebene Problem als Formel auf ein Papier schreiben - ja, schalt den Computer aus, sonst kommst du nur in Versuchung gleich loszulegen - und dann die Formel so umzuformen, dass
Code: 
f(x) = x + (x-1) + f(x-1)
herauskommt und beweise dass
Code: 
f(2) = 1
ist. (Es ist ja um einige einfacher, da die Lösung schon vorliegt - du musst nur noch beweisen, dass sie stimmt und dabei lernst du ein erstes mal wie eine Rekursion aufgebaut ist.
 

Aktuelle Jobs

Neue Themen


Oben