Frage von Yooooooshi, 35

H(n)=H(n-H(n-1)) + H(n-H(n-2) Wie löst man so eine Gleichung?

Hallöchen! Habe eine Aufgabe in Informatik vorgelegt bekommen und diese nun gelöst. mein Problem war eine darin vorkommende Gleichung, deren Lösungsweg ich nicht versteh.

H(n)=H(n-H(n-1)) + H(n-H(n-2)

Als Ergebnis bekommt man eine bestimmte Zahlenfolge. Nur interessiert mich jetzt der Zusammenhang zwischen Formel und Lösung. Danke im Voraus :)

Expertenantwort
von hypergerd, Community-Experte für Mathematik, 9

Es fehlen leider die Startbedingungen (Initialisierung), die bei rekursiven Algorithmen nötig sind!

Der Iterationsrechner kann das online leicht vorrechnen.

http://www.lamprechts.de/gerd/Roemisch_JAVA.htm##@NaB=Array(0,0);aC=Array(0,1);a...]=i-aD[i-1];@Ci]=i-aD[i-2];aD[i]=aD[@Bi]]+aD[@Ci]];@Ni%3E33@N0@N0@N#

{ LINK endet mit N# und beinhaltet den kompletten Code siehe Bild}

Arrays drückt man besser mit eckigen Klammern aus, um zu erkennen, dass ein ganzzahliger Index {also das wievielte Glied} angesprochen werden soll.

Dein H ist dort aD {letzte rechte Spalte der Wertetabelle }

Dein n ist dort i { Index ist gleichzeitig Zeilennummer}

Da Du statt einer einfachen Abhängigkeit wie bei den Fibonacci-Zahlen:

a[i]=a[i-1]+a[i-2] {Nachfolger ist Summe aus den beiden Vorgängern}

eine doppelte Abhängigkeit eingebaut hast

aD[i]=aD[i-aD[i-1]]+aD[i-aD[i-2]]

habe ich zur Übersichtlichkeit 2 Hilfs-Arrays aB und aC eingebaut, die die Zwischenergebnisse der anzusprechenden Summanden anzeigen:

aB[i]=i-aD[i-1]   und aC[i]=i-aD[i-2] 

Das Endergebnis wird somit zu:

aD[i]=aD[aB[i]]+aD[aC[i]];

Da auch Vor-Vorgänger angesprochen werden, müssen 2 Feldvariablen (also die ersten beiden Glieder der Folge) per Startbedingung vordefiniert sein und der Index der Berechnung darf erst bei i=2 beginnen.

Es gibt nur sehr wenige Vorbedingungen, die zu einer machbaren Lösung führen, da der Hilfsindex aB und aC nie größer werden darf als der von aD, der zuvor jemals berechnet wurde ( das sonst auf undefinierte Feldvariablen zugegriffen wird!).

Oder hast Du Dich einfach nur verschrieben, denn doppelt verschachtelte rekursive Algorithmen sind schon sehr selten!

Kommentar von hypergerd ,

Interessant: die Folge wird mit wachsenden Index immer komplizierter:

 i  aB  aC  aD

87 40 42 47
88 41 41 46
89 43 42 48
90 42 44 48
91 43 43 48
92 44 44 48
93 45 45 48
94 46 46 48
95 47 47 64
96 32 48 41
Antwort
von densch92,

Hm, so direkt nicht lösbar.

Fehlt die Startbedingung wie schon erwähnt (da n-1 und n-2 vorkommen, brauchen wir sogar die ersten 2 Zahlen als Startbedingung)

Wie man da auf eine lösung kommt, weiß ich nicht.

Ausser durch sehr geschicktes Raten...

Die Tatsache dass der Index auch noch eine Rolle spielt, macht es auch nicht viel leichter :-/

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten