ich habe hier eine rekursive Java-Methode, zu einer Aufgabe. Ich glaube, hier findet sich bestimmt jemand der das überprüfen kann.
Aufgabe)
Sei f: IN->IN eine Funktion, die folgendermaßen rekursiv definiert ist:
f(1)=1;f(2)=2 sowie
f(n)=4⋅f(n−1)−f(n−2), falls n>2.
Schreiben Sie eine rekursive Java-Methode, die zu einer gegebenen natürlichen Zahl den Funktionswert f(n) berechnen. eine main-Methode soll nicht beschreiben werden.
Antwort)
public class f{
public static int f(int n){
if (n==1)
return 1;
else if (n==2)
return 2;
else
return 4⋅f(n−1)−f(n−2);
}
}
Wäre super wenn mir jemand sagen würde ob ich alles richtig gemacht habe.
In Java gibt es keinen Operator mit dem Bild/Zeichen '⋅', somit kompiliert der Code nicht. Du meinst ja sicher den Multiplikationsoperator '*'. Ansonsten ist es richtig.
@httpdigest die lösung ist von der Laufzeit ja nicht so schön. Wie wäre dein Ansatz dafür ?
Wir sind ja hier in einer exponentiell Lösung, könnte man das auch Linear hinbekommen ?
Hmm, wie gehst du denn genau vor? Du musst meiner Meinung nach lernen, da Handlungswege für Dich zu finden und es Dir bewusst zu machen, was du machst .,.
Hier bedeutet das, dass du dir die Serie aufschreibst:
1: 1
2: 2
3: 4*2 - 1 = 7
4: 4*7 - 2 = 26
5: 4*26 - 7 = 97
...
So kann man das berechnen von Hand ... Zeile für Zeile...
Kannst du die Vorgehensweise nachvollziehen?
was brauchst du für eine Zeile? Das was du brauchst, sind dann die Parameter ...
Was habe ich für die Zeile 5:.... gebraucht?
@kneitzel Bist du dir sicher, dass du linear nicht mit iterativ verwechselst? Ich glaube du willst auf einen iterativen Ansatz hinaus, gesucht ist jedoch linear. Ich wäre echt überrascht wenn du hier eine lineare Formel siehst. Ich tue es nicht
Was ich nur grundsätzlich sagen kann: Die Formel erinnert leicht an Fibonacci und auch hier ist die Herleitung der linearen Formel nicht ganz trivial. https://de.wikipedia.org/wiki/Fibonacci-Folge
Es geht beides. Iterativ linear sowie rekursiv linear. Man braucht aber eine "Hilfsmethode" (bei rekursiven Funktionen ja nicht unüblich), die nicht die geforderte Signatur int(int) hat, sondern weitere Parameter braucht. Die eigene Funktion int(int) ruft dann nur die eigentliche Hilfsmethode auf.
Öhm, was verstehst ihr unter linearem Algorithmus?
Nach Wikipedia ist dies ein Algorithmus, der in O(n) läuft. Und das tut mein Algorithmus. Unabhängig davon, ob man ihn iterativ oder rekursiv berechnet.
Und ich bin auf Rekursion gegangen vom Wording her(==> Parameter), da ja das etwas gefragt war: "hab jetzt aber keine Ahnung wie die Rekursionsform dazu aussehen würde."
Generell erkennt man aber, dass man nur die zwei vorherigen Werte braucht, um den nächsten Wert zu berechnen. Das hatten wir prinzipiell vor kurzem erst im Tribonacci Thread mit iterativer, rekursiver und Stream Lösung ... und dann sogar einmal Objektorientiert aufgebaut ...
@kneitzel das mit dem auf schreiben und der Nummerierung hat mir sehr geholfen. Der Satz "Generell erkennt man aber, dass man nur die zwei vorherigen Werte braucht", da hat es "Bing" gemacht bei mir. Vielen Dank nochmal 👍
Ein Linearer Algorithmus hat nichts mit iterativ zu tun. Daher mein Link zu Wikipedia:
Ein linearer Algorithmus ist ein Algorithmus dessen Laufzeit linear in der Größe der Eingabe ist. Dies bedeutet, dass der Algorithmus für eine doppelt so große Eingabe in etwa doppelt so lange braucht. Man sagt auch: "Der Algorithmus ist in O(n)".
