3. Eine rekursive Funktion

Eine rekursive Funktion

  • H

    Hallo!
    Wir hatten an der Uni Folgende Aufgabe(Den Wert habe ich zwar berechnet und die Antwort eingereicht aber ich habe gefühl das es zu komplizierter Weg war):

    Eine sehr interessante, aber äußerst undurchsichtige Folge natürlicher Zahlen wird durch die Hofstätter-Rekursion (um 1930) beschrieben:

    h(n) = h(n - h(n - 1) ) + h(n - h(n - 2) ) für n > 2

    mit h(1) = h(2) = 1

    Aufgabe:
    - Implementieren Sie die Hofstätter Rekursion als rekursive Funktion in C++.
    - Schreiben Sie Ihr Programm so, dass der Anwender zu Beginn nach dem Argument für die Funktion gefragt wird. Anschließend soll der Wert errechnet und ausgegeben werden.
    - Berechnen Sie mit dem von Ihnen erstellten Programm den Funktionswert für 20 und 100. Kreuzen Sie die beiden richtigen Ergebnisse unten an.

    Tipp:
    Die Berechnung kann für größere Argumente sehr lange dauern. Verwenden Sie zur Beschleunigung eine Tabelle zum nachschlagen bereits berechneter Funktionsergebnisse. Dies können Sie z.B. über ein globales integer-Array realisieren. In diesem Array werden zunächst die Lösungen für h(1) und h(2) eingetragen und alle übrigen Lösungen auf -1 gesetzt.

    Wird nun die Funktion h(n) aufgerufen, wird zunächst in dem Array nachgeschaut, ob der Wert vielleicht schon berechnet wurde (d.h. Wert > -1). Falls ja, kann der Wert gleich zurückgeliefert werden. Wenn nicht, muss der Wert mit obiger Formel errechnet werden, und kann dann zur späteren Verwendung in das Array geschrieben werden.

    Also erstens habe ich einen Code erstellt ohne Array:

    # include <iostream>

int hof (int);

int main()
{
	int hofzahl1=hof(20);
	int hofzahl2=hof(100);

	std::cout<<"Ergebnis fuer 20: "<<hofzahl1<<std::endl;
	std::cout<<"Ergebnis fuer 100: "<<hofzahl2<<std::endl;
	return 0;

}

int hof (register int n)
{
	if ( n < 3 ) return (1) ; 
		else 
 	return ( hof ( n - hof (n - 1) ) + hof (n - hof (n - 2) ) ) ; 

}

    Aber was es sich mit dieser diese Array auf sich hat verstehe ich nicht leider nicht ganz:(
    Mein Problem:
    1. So wie es ist braucht mein Rechner für den Wert 100 ein Paar Stunden, warum ist klar.
    2.Wie oben gesagt soll das Array den Ablauf beschleunigen,aber wie?
    Wann müssen Werte da reingeschrieben werden? Nach dem z.B Programm den Wert für 20 berechnet hat? oder was bringt es wenn ich das Program gleich für 100 aufrufe? also wird nach dem Ablauf den wert für 100 reingeschrieben oder wie?

    Wenn ich mein Problem unverständlich geäussert habe, sorry und bitte, dass jemand vielleicht diese Array in den Code einfügt.
    Danke im Voraus.

    0
  • S

    ich denke es ist folgendes gemeint:

    hof(1) liefert 1 zurück
    Also schreiben wir ins array an stelle 1 eine 1
    hof(2) liefert 1 zurück
    Also schreiben wir ins array an stelle 2 eine 1
    usw.

    hof(100) ruft ja intern hof(99), hof(98), hof(97) etc. auf.
    Aber hof(98) muss ja bereits berechnet sein (da hof(99) es ja schon berechnen hat lassen) - folglich ist es nicht mehr nötig es zu berechnen -> ein lookup im array ist wesentlich schneller.

    ich hoffe es ist klar geworden?

    btw: mach das register weg - das sieht ungut aus.

    0
  • B

    Genau. Das nennt sich übrigens Memoization.

    0
  • H

    Danke, so habe ich es jetzt verstanden, aber nur das Prinzip.
    Aber wie realisiere ich das?
    Wenn es dir nich aufwendig ist, könnest du es biite da einfügen?
    Mit dem "register", war so, dass ich gerade über die Speicherklassen gelesen habe und bissel was rumexperimentierte, dann ist es beim kopieren unbemerkt da gebliben. Aber warum sollte man es nicht benutzen?
    Ist das überflüssig? Im Buch stand nur Beschreibung von den Vorteilen oder Nachteilen nichts.
    danke

    0
  • B
     

    int hof_values[200];
void init_hof_values()
{
  hof_values[1] = hof_values[2] = 1;
  for (int i = 3; i < 200; ++i)
    hof_values[i] = -1;
}

int hof(int n)
{
    assert(n >= 1 && n < 200);
    if (hof_values[n] != -1)
      return hof_values[n];
    int result;
    if ( n < 3 ) 
      result = 1
    else
      result = ( hof ( n - hof (n - 1) ) + hof (n - hof (n - 2) ) ) ;
    hof_values[n] = result;
    return result;
}
    0
  • H

    Danke hat geklappt, aber verstehe

    assert(n >= 1 && n < 200);

    nicht ganz. Sonst ist es am Ende so was rausgekommen und funktioniert:

    # include <iostream>

int hof (int);
int arr[101]={1,1};

int main()
{

for(int c=2;c<101;c++)
{
	arr[c]= -1;
}

 int hof2=hof(100);
 std::cout<<"Hofstaetter Rekursion Ergebniss fuer Zahl 100: "<<hof2<<std::endl;

return 0;
}

int hof (int n)

	{ 
	if( arr[n]!=-1)
	return arr[n];
	int result;
	if(n<3)
		result=1; 
		else 
 		result=( hof ( n - hof (n - 1) ) + hof (n - hof (n - 2) ) ) ; 
		arr[n]=result;
		return result;
}
    0
  • W

    Diese assertation meldet dir zur Debug-Laufzeit Bereichsüber-/unterschreitungen.

    0
  • ?

    Bei miener Version kommt für 100 56 raus, stimmt das oder ist da was falsch?

    P.S. Bei mir gings selbst bei 899 (Ich hab das ganze ein wenig ausgeweitet) sehr schnell (1 sek.)

    mfg
    Glamdring

    0
  • H

    Ja bei mir auch 56.
    bei mir ging es aquch so schnell bis 1000.
    P.S. Was ist diese assert? Wozu gehört es? Ist es eine Funktion? Muss man etwas dafür includieren?
    Danke!

    0
  • T

    assert lässt dein Prgramm (in der Debugg-Version) abstürzen, wenn
    die übergebene Bedingung false wird - und meldet, in welcher Funktion
    es abgestürtzt ist. Ganz furchtbar praktsich zum Fehler finden.

    0
  • S

    Taurin schrieb:

    assert lässt dein Prgramm (in der Debugg-Version) abstürzen

    nein. es gibt eine 'Assertion' aus. Meistens ist das eine kleine Meldung wo die Zeile und Datei drinnen steht, in der die Assertion aufgedrehten ist. Meistens wird auch noch der Ausdruck angegeben, der den Fehler verursacht hat.

    Oft wird dann auch noch der Debugger aufgerufen, so dass man recht schnell feststellen kann, was da schief gelaufen ist.

    also absturz wuerde ich es nicht nennen...

    0
  • O

    herrlado schrieb:

    Ist es eine Funktion?

    Nein, ein Präprozessor-Makro. Deshalb befindet es sich auch nicht in std::.

    Muss man etwas dafür includieren?

    -> <cassert>

    0
  • H

    Alles klar, danke

    0
  • ?

    Wie wärs damit?

    #include <iostream>

template <unsigned long long n> struct hs {
  static const unsigned long long val = hs<n - hs<n-1>::val>::val + hs<n - hs<n-2>::val>::val;
};
struct hs<1> { static const unsigned long long val = 1; };
struct hs<2> { static const unsigned long long val = 1; };

template <int i> struct do_loop {
  static void run() {
    do_loop<i-1>::run();
    std::cout << i << '\t' << hs<i>::val << std::endl;
  }
};
struct do_loop<0> { static void run() { } };

int main() {
  do_loop<100>::run();
}
    0
Anmelden zum Antworten