Übung zur Rekursion

[JavaScala-An]

Hallo,

hab eine frage bezüglich einer Übungsaufgabe (Rekursion)
a)Schreiben Sie eine Funktion invHarm(rouble):Int, um das kleinste n zu finden so dass
(1+1/2+...+1/n) >= r ist.

ich hab zwar schon die funktion zur berechnung für die summe n aber wie soll ich das machen
das er das kleinste n nimmt, das größer oder gleich r ist?

def invHarmHelp(n:Int):Int ={
if (n==0) 1
else invHarmHelp(n-1) + (1/(n+1))
}

danke

 

[Gucky]

Du bist im Hausaufgabenforum.
Benutze bitte nächstes mal das richtige Unterforum zu den JVM Aliens und schreibe dazu, dass es sich um Scala handelt.

Zudem verstehe ich deine Frage nicht. Bitte erkläre sie noch mal.

 

[JavaScala-An]

ok sry,
die aufgabe ist ja, dass ich ein r: Double eingebe und er den kleinsten n wert wo die folge (1+1/2+1/3+...+1/n) >=r ist, ausgibt.
also muss das programm irgendwie den n wert selber bestimmen
z.B. r= 1.8
1+1/2= 1.5
1+1/2+1/3 =1.833
jetzt soll er den Int wert 3 rausgeben, da 1.8333 > 1.8

 

[Flown]

Schon wieder eine Rekursion. :noe:

Ist doch ganz einfach. Ich baue sie mit dir jetzt gemeinsam:

Man benötigt keine Helper Methode für diese Aufgabe.

Also ich baue mir immer eine Fassadenmethode, die nur die erforderlichen Eingaben benötigt und zwar r. (Ich machs jetzt mal in Java, da ich Scala nicht installiert habe).

Dann sieht das schon mal so aus:

public static int invHarm(double r) {
  return invHarm(...);
}

Dann überlegen wir mal was wir für die Initialisierung, Überprüfung und Rechenschritte benötigen.

Da haben wir mal, dass die Reihe mit f(1) = 1/1 = 1 beginnt (Initialisierung)
Dann benötigen wir das r, dass die Beendigung der Rekursion zeigt (Überprüfung)
Dann zu guter letzt noch das n, dass den Rechenschritt anzeigt

Dann wird aus dem oberen Code:

public static int invHarm(double r) {
  return invHarm(r, 1, 1);
}

Jetzt können wir uns der privaten Methode widmen:

private static int invHarm(double r, double fn, int n) {
  if(/* Abbruchbedingung aus deiner Spezifikation gegeben */) {
    return n;
  }
  return invHarm(r, /* Neuberechnung deines fn <=> fn = 1 + ... + 1/n */, /* Nächster n Schritt */);
}

 

[JavaScala-An]

public static int invHarm(double r) {
  return invHarm(...);
}

Dann überlegen wir mal was wir für die Initialisierung, Überprüfung und Rechenschritte benötigen.

Da haben wir mal, dass die Reihe mit f(1) = 1/1 = 1 beginnt (Initialisierung)
Dann benötigen wir das r, dass die Beendigung der Rekursion zeigt (Überprüfung)
Dann zu guter letzt noch das n, dass den Rechenschritt anzeigt

Dann wird aus dem oberen Code:

public static int invHarm(double r) {
  return invHarm(r, 1, 1);
}

Jetzt können wir uns der privaten Methode widmen:

private static int invHarm(double r, double fn, int n) {
  if(n==0) return 1 else invHarm((n-1)+(1.0/(n+1)) {
    return n;
  }
  return invHarm(r, /* Neuberechnung deines fn <=> fn = 1 + ... + 1/n */,/* Nächster n Schritt */);
}

also ich versteh jetzt noch nicht wie ich das mit fn machen soll, fn ist meine funktion, die die summe 1+1/n+... ausrechnet. Aber wie baue ich das fn ein? nächster n Schritt wäre doch dann einfach n+1?
bei der if zeile, schreib ich da return 1 oder return fn?

 

[Flown]

Rekapiturlieren wir nocheinmal das ganze.

Die Beendigung deiner Rekursion soll doch dein gewünschtes und minimales "n" zurückliefern. Dies representiert deine Iterationsschritte.

Die Lösung ist also:

private static int invHarm(double r, double fn, int n) {
  if (fn >= r) {
    return n;
  }
  return invHarm(r, /*Neuberechnung fn */, /*Nächster Iterationsschritt */);
}

Nocheinmal wie wird fn berechnet?

Schreibtischtest:
n = 1: fn = 1
n = 2: fn = 1 + 1/2
n = 3: fn = 1 + 1/2 + 1/3
...

Also rufst du jeweils deine private Methode mit dem neuen fn und n auf, dass sich sowas ergibt:

Schreibtischtest(sowas ist ja unheimlich praktisch, nicht?):
n = 1; invHarm(r, 1, 1);
n = 2; invHarm(r, 1 + 1/2, 2);
n = 3; invHarm(r, 1 + 1/2 + 1/3, 3);

um jetzt die nächste Iteration immer aufzurufen brauchst du dann was?