Hofstadters Folgen in C

[Bert (Gast)]

Hallo,

ich möchte Hofstadters Q-Folge als Funktion sowohl iterativ als auch 
rekursiv programmieren. Dabei möchte ich die n-te Zahl berechnen, die 
main-Funktion stellt sicher, dass die Zahl n>0 ist.

http://de.wikipedia.org/wiki/Hofstadter-Folge
In dem Link etwa in der Mitte ist sie beschrieben.


Iterativ habe ich das ganze geschafft, der Code sieht so aus:

int Iterativ( int n ) 
{
  int i=0;
  int *ptr;
  ptr = (int *) malloc( n * sizeof(int));

  ptr[0]=ptr[1]=1;

  for(i=2;i<=n;++i){
    ptr[i]=ptr[i-ptr[i-1]] + ptr[i-ptr[i-2]] }

  return ptr[n-1]; /* Feld beginnt bei 0 */

Rekursiv bekomme ich das ganze einfach nicht hin, wäre super, wenn mir 
dabei jemand helfen könnte, ich bin fast am Verzweifeln.


MfG
Bert

[Karl H. (kbuchegg)]

Bert schrieb:

>   int *ptr;
>   ptr = (int *) malloc( n * sizeof(int));
>
>   ptr[0]=ptr[1]=1;
>
>   for(i=2;i<=n;++i){

Hier hast du einen Fehler.
Du hast im malloc 1 Element zu wenig allokiert.

Faustregel: Wann immer du es mit Arrays zu tun hast und die 
for-Schleife, die über die Array-Elemente iteriert, ein <= anstelle 
eines < enthält, ist extreme Vorsicht angebracht.

Ausserdem hast du den allokierten Speicher nicht wieder freigegeben.

> Rekursiv bekomme ich das ganze einfach nicht hin, wäre super, wenn mir
> dabei jemand helfen könnte, ich bin fast am Verzweifeln.

Wo liegt das Problem?
Rekursiv programmiert sich das fast von alleine mit der Definition der 
Folge

Def:
   Q(1) = 1
   Q(2) = 1
   Q(n) = Q( n - Q(n-1)) + Q( n - Q(n-2) )

int Q( int n )
{
  if( n == 1 )
    return 1;

  if( n == 2 )
    return 1;

  return Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) );
}

[yalu (Gast)]

Karl heinz Buchegger schrieb:
>>   for(i=2;i<=n;++i){
>
> Hier hast du einen Fehler.
> Du hast im malloc 1 Element zu wenig allokiert.

...bzw. einen Schleifendurchlauf zu viel programmiert, der für das
Ergebnis gar nicht benötigt wird. i<n als Abbruchbedingung reicht, dann
stimmt's auch mit dem malloc.

[Bert (Gast)]

Hallo,


vielen Dank euch beiden!!

>Wo liegt das Problem?

Die beiden oberen Zeilen sind klar, mein Problem ist einfach, dass ich 
mir nicht vorstellen kann, dass diese Zeile

 return Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) );

die Q-Folge ergibt. Da tu ich mich ja schon beim Nachvollziehen mit 
einem Beispiel, wenn ich nun etwa n= 5 im Kopf einsetze, extrem schwer.
Dass man das Ganze quasi aus der Definition "entnehmen" kann, wusste ich 
nicht, ich werd mir das Schema dann mal einprägen. Danke nochmals!


MfG
Bert

[Karl H. (kbuchegg)]

Hmm.
Laut Wikipedia:
<quote>
Es ist insbesondere unbekannt, ob die Folge für alle n wohldefiniert 
ist, das heißt, ob die Folge irgendwo abbricht, weil ihre 
Produktionsregel versucht, sich auf Elemente zu beziehen, die sich 
konzeptuell links vom ersten Element Q(1) befinden müssten.
</quote>

Also besser:

int Q( int n )
{
  if( n < 1 ) {
    printf( "ungültiges n: %d\n", n );
    return 1;   // man könnte hier auch einen exit() machen
                // aber dagegen habe ich eine Abneigung :-)
  }

  if( n == 1 )
    return 1;

  if( n == 2 )
    return 1;

  return Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) );
}

[Karl H. (kbuchegg)]

Bert schrieb:

> Die beiden oberen Zeilen sind klar, mein Problem ist einfach, dass ich
> mir nicht vorstellen kann, dass diese Zeile
>

>  return Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) );

>
> die Q-Folge ergibt. Da tu ich mich ja schon beim Nachvollziehen mit
> einem Beispiel, wenn ich nun etwa n= 5 im Kopf einsetze, extrem schwer.

Das wirst du auch im Kopf so nicht schaffen.
Aber mit Papier und Bleistift gehts. Und dann hast du natürlich auch 
noch dein Programm. Niemand hindert dich daran, im Programm ein paar 
printf einzubauen, so dass das Programm mitprotokolliert, wie das 
berechnet wird :-)

[Karl H. (kbuchegg)]

So könnte zb eine mit Ausgaben versehene Funktion Q aussehen, die 
mitprotokolliert, was sie tut. Der zusätzliche Parameter 'Level' ist 
einfach nur die Rekusrionstiefe und wird dazu misbraucht die einzelnen 
Ausgaben entsprechend der Rekursionstiefe einzurücken.

#include <stdio.h>

void Indent( int Level )
{
  int i;
  for( i = 0; i < Level; ++i )
    printf( " " );
}

int Q( int n, int Level )
{
  int Sum1, Sum2;

  Indent( Level );
  printf( "Berechne Q(%d)\n", n );

  Level++;

  if( n == 1 ) {
    Indent( Level );
    printf( "trivial, das ist 1\n" );
    return 1;
  }

  if( n == 2 ) {
    Indent( Level );
    printf( "trivial, das ist 1\n" );
    return 1;
  }

  Indent( Level );
  printf( "Gesucht Q( %d - Q( %d ) )\n", n, n - 1 );
  Sum1 = Q( n - Q( n - 1, Level ), Level );

  Indent( Level );
  printf( "Gesucht Q( %d - Q( %d ) )\n", n, n - 2 );
  Sum2 = Q( n - Q( n - 2, Level ), Level );

  Indent( Level );
  printf( "Q(%d) = %d + %d = %d\n", n, Sum1, Sum2, Sum1 + Sum2 );

  return Sum1 + Sum2;
}

int main()
{
  printf( "-> ergebnis %d\n", Q( 6, 0 ) );
}

[Bert (Gast)]

Wow, da hast du dir aber viel Mühe gemacht, da kann ich mich nur erneut 
bedanken und dir ein dickes Lob aussprechen! Toll, wie du dich hier 
engagierst! Ich werd den Code jetzt gleich mal durchdenken :-)


MfG
Bert

[Karl H. (kbuchegg)]

Bert schrieb:
> Wow, da hast du dir aber viel Mühe gemacht, da kann ich mich nur erneut
> bedanken und dir ein dickes Lob aussprechen! Toll, wie du dich hier
> engagierst! Ich werd den Code jetzt gleich mal durchdenken :-)

Da brauchst du nicht viel durchdenken.
Ist der gleiche Code wie vorher, nur ein paar printf sind mehr drinnen 
und die Monsterberechnung

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

habe ich in 2 Teile aufgespalten

  S1 = Q( n - Q(n-1) )
  S2 = Q( n - Q(n-2) )

  Q(n) = S1 + S2

damit ich mittendrinn, während der Berechnung, noch Gelegenheit für ein 
paar printf habe.
Eigentlich sollte man das noch ein wenig mehr mit Zwischenvariablen und 
printf aufdröseln. Aber das kannst ja dann du machen :-)

[Michael H. (overthere)]

Oh da hat jemand mit dem Programmierpraktikum an der TU Munich Probleme. 
Ich dachte dazu gibts Tutoren =)

Jetzt mal ein Tipp fürs rekursive: Ersetz einfach jede eckige Klammer 
des Feldes durch einen rekursiven Funktionsaufruf.
ptr[i-ptr[i-1]] + ptr[i-ptr[i-2]]
also so:
rekursiv(i-rekursiv(i-1) + rekursiv(i-rekursiv(i-2))

[Karl H. (kbuchegg)]

So ist die Berechnung (die immer noch dieselbe ist) noch ein wenig mehr 
aufgedröselt und das Protokoll noch leichter zu lesen

#include <stdio.h>

void Indent( int Level )
{
  int i;
  for( i = 0; i < 2*Level; ++i )
    printf( " " );
}

int Q( int n, int Level )
{
  int Sum1, Sum2, Tmp;

  Indent( Level );
  printf( "Berechne Q(%d)\n", n );

  Level++;

  if( n == 1 ) {
    Indent( Level );
  printf( "trivial, das ist 1\n" );
    return 1;
  }

  if( n == 2 ) {
    Indent( Level );
  printf( "trivial, das ist 1\n" );
    return 1;
  }

  Indent( Level );
  printf( "Zu berechnen ist Q( %d - Q( %d ) ) + Q( %d - Q( %d ) )\n", n, n-1, n, n - 2 );
  printf( "\n" );
  Indent( Level );
  printf( "Gesucht Q( %d - Q( %d ) )\n", n, n - 1 );
  Indent( Level );
  printf( "Dazu brauche ich Q(%d)\n", n - 1 );
  Tmp = Q( n - 1, Level + 1 );
  Indent( Level );
  printf( "Q(%d) ergibt also %d\n", n - 1, Tmp );
  Indent( Level );
  printf( "Und jetzt Q( %d - %d ) = Q(%d)\n", n, Tmp, n - Tmp );
  Sum1 = Q( n - Tmp, Level );
  Indent( Level );
  printf( "Q( %d - Q( %d ) ) ergibt also %d\n", n, n - 1, Sum1 );

  printf( "\n" );
  Indent( Level );
  printf( "Gesucht Q( %d - Q( %d ) )\n", n, n - 2 );
  Indent( Level );
  printf( "Dazu brauche ich Q(%d)\n", n - 2 );
  Tmp = Q( n - 2, Level + 1 );
  Indent( Level );
  printf( "Q(%d) ergibt also %d\n", n - 2, Tmp );
  Indent( Level );
  printf( "Und jetzt Q( %d - %d ) = Q(%d)\n", n, Tmp, n - Tmp );
  Sum2 = Q( n - Tmp, Level );
  Indent( Level );
  printf( "Q( %d - Q( %d ) ) ergibt also %d\n", n, n - 2, Sum2 );

  Indent( Level );
  printf( "Q(%d) = %d + %d = %d\n", n, Sum1, Sum2, Sum1 + Sum2 );

  return Sum1 + Sum2;
}

int main()
{
  printf( "-> ergebnis %d\n", Q( 4, 0 ) );
}

Für Q(4) sieht das Protokoll so aus

Berechne Q(4)
  Zu berechnen ist Q( 4 - Q( 3 ) ) + Q( 4 - Q( 2 ) )

  Gesucht Q( 4 - Q( 3 ) )
  Dazu brauche ich Q(3)
    Berechne Q(3)
      Zu berechnen ist Q( 3 - Q( 2 ) ) + Q( 3 - Q( 1 ) )

      Gesucht Q( 3 - Q( 2 ) )
      Dazu brauche ich Q(2)
        Berechne Q(2)
          trivial, das ist 1
      Q(2) ergibt also 1
      Und jetzt Q( 3 - 1 ) = Q(2)
      Berechne Q(2)
        trivial, das ist 1
      Q( 3 - Q( 2 ) ) ergibt also 1

      Gesucht Q( 3 - Q( 1 ) )
      Dazu brauche ich Q(1)
        Berechne Q(1)
          trivial, das ist 1
      Q(1) ergibt also 1
      Und jetzt Q( 3 - 1 ) = Q(2)
      Berechne Q(2)
        trivial, das ist 1
      Q( 3 - Q( 1 ) ) ergibt also 1
      Q(3) = 1 + 1 = 2
  Q(3) ergibt also 2
  Und jetzt Q( 4 - 2 ) = Q(2)
  Berechne Q(2)
    trivial, das ist 1
  Q( 4 - Q( 3 ) ) ergibt also 1

  Gesucht Q( 4 - Q( 2 ) )
  Dazu brauche ich Q(2)
    Berechne Q(2)
      trivial, das ist 1
  Q(2) ergibt also 1
  Und jetzt Q( 4 - 1 ) = Q(3)
  Berechne Q(3)
    Zu berechnen ist Q( 3 - Q( 2 ) ) + Q( 3 - Q( 1 ) )

    Gesucht Q( 3 - Q( 2 ) )
    Dazu brauche ich Q(2)
      Berechne Q(2)
        trivial, das ist 1
    Q(2) ergibt also 1
    Und jetzt Q( 3 - 1 ) = Q(2)
    Berechne Q(2)
      trivial, das ist 1
    Q( 3 - Q( 2 ) ) ergibt also 1

    Gesucht Q( 3 - Q( 1 ) )
    Dazu brauche ich Q(1)
      Berechne Q(1)
        trivial, das ist 1
    Q(1) ergibt also 1
    Und jetzt Q( 3 - 1 ) = Q(2)
    Berechne Q(2)
      trivial, das ist 1
    Q( 3 - Q( 1 ) ) ergibt also 1
    Q(3) = 1 + 1 = 2
  Q( 4 - Q( 2 ) ) ergibt also 2
  Q(4) = 1 + 2 = 3
-> ergebnis 3

man erkennt auch den Nachteil der (simplen) rekursiven Lösung.
Das Programm ist strohdumm. Einzelne Werte werden wieder und immer 
wieder berechnet. Das Programm weiß nicht, dass es (in diesem Fall) Q(3) 
schon des öfteren berechnet hat.

[yalu (Gast)]

Karl heinz Buchegger schrieb:
> ...

Hab' mir auch gerade ein paar Gedanken dazu gemacht. Ganz so einfach
ist es tatsächlich nicht ;-)

Aber die Folge hat einen interessanten Verlauf (s. Anhang).

[D. I. (Gast)]

Ich behaupte wenn dus simpel rekursiv berechnest wird ohne dynamische 
Programmierung irgendwo bei n = 50 Schluss sein :>

[Karl H. (kbuchegg)]

Christopher D. schrieb:
> Ich behaupte wenn dus simpel rekursiv berechnest wird ohne dynamische
> Programmierung irgendwo bei n = 50 Schluss sein :>

Alles eine Frage der Geduld.
Die Stackbelastung ist ja nicht sehr hoch.
D.h.: Solange man das Ergebnis erwarten kann, ist man im Rennen.

[D. I. (Gast)]

Karl heinz Buchegger schrieb:
> Christopher D. schrieb:
>> Ich behaupte wenn dus simpel rekursiv berechnest wird ohne dynamische
>> Programmierung irgendwo bei n = 50 Schluss sein :>
>
> Alles eine Frage der Geduld.
> Die Stackbelastung ist ja nicht sehr hoch.
> D.h.: Solange man das Ergebnis erwarten kann, ist man im Rennen.

Hehe, ja da kann man sich zeitlich irgendwo zwischen einem Kaffee holen 
und 5 Häuser bauen einreihen :D

[Karl H. (kbuchegg)]

Christopher D. schrieb:

> Hehe, ja da kann man sich zeitlich irgendwo zwischen einem Kaffee holen
> und 5 Häuser bauen einreihen :D

:-)

Habs gerade probiert.
10 geht sofort
20 ebenfalls
30 dauert schon ein paar Sekunden
40 noch keien Zigarettenlänge
50 hab ich grade gestartet

[D. I. (Gast)]

Karl heinz Buchegger schrieb:
> Christopher D. schrieb:
>
>> Hehe, ja da kann man sich zeitlich irgendwo zwischen einem Kaffee holen
>> und 5 Häuser bauen einreihen :D
>
> :-)
>
> 50 hab ich grade gestartet

Werde dann heut nach unserem Johann König - DVD Abend wieder reinsehen 
und das Ergebnis abwarten :D
Morgen gebe ich dann auch mal eine schicke Folge (im Sinne wenn man sie 
sich als Plot ansieht) zum Besten

[Karl H. (kbuchegg)]

10 Minuten sind durch
Und er rechnet und rechnet und rechnet ....

[D. I. (Gast)]

Karl heinz Buchegger schrieb:
> 10 Minuten sind durch
> Und er rechnet und rechnet und rechnet ....

ich würde bei n=50 auf eine 2stellige stundenzahl < 1 Tag tippen

[Karl H. (kbuchegg)]

Christopher D. schrieb:
> Karl heinz Buchegger schrieb:
>> 10 Minuten sind durch
>> Und er rechnet und rechnet und rechnet ....
>
> ich würde bei n=50 auf eine 2stellige stundenzahl < 1 Tag tippen

20 sind durch.

:-)
Allerdings will ich um 8 ins Kino und ich hab keine Messfunktion ins 
Programm eingebaut. Also hopp, hopp. In einer halben Stunde muss ein 
Ergebnis her :-)
Ich kann natürlich auch durchlaufen lassen. Dann hab ich wenigstens eine 
obere Schranke wenn er in der Zwischenzeit fertig werden sollte.

[D. I. (Gast)]

Karl heinz Buchegger schrieb:
> Christopher D. schrieb:
>> Karl heinz Buchegger schrieb:
>>> 10 Minuten sind durch
>>> Und er rechnet und rechnet und rechnet ....
>>
>> ich würde bei n=50 auf eine 2stellige stundenzahl < 1 Tag tippen
>
> 20 sind durch.
>
> :-)
> Allerdings will ich um 8 ins Kino und ich hab keine Messfunktion ins
> Programm eingebaut. Also hopp, hopp. In einer halben Stunde muss ein
> Ergebnis her :-)
> Ich kann natürlich auch durchlaufen lassen. Dann hab ich wenigstens eine
> obere Schranke wenn er in der Zwischenzeit fertig werden sollte.

ich wette dass er nicht vor morgen früh fertig ist :) wer steigt ein? :D

[Karl H. (kbuchegg)]

Christopher D. schrieb:
> Karl heinz Buchegger schrieb:
>> Christopher D. schrieb:
>>> Karl heinz Buchegger schrieb:
>>>> 10 Minuten sind durch
>>>> Und er rechnet und rechnet und rechnet ....
>>>
>>> ich würde bei n=50 auf eine 2stellige stundenzahl < 1 Tag tippen
>>
>> 20 sind durch.
>>
>> :-)
>> Allerdings will ich um 8 ins Kino und ich hab keine Messfunktion ins
>> Programm eingebaut. Also hopp, hopp. In einer halben Stunde muss ein
>> Ergebnis her :-)
>> Ich kann natürlich auch durchlaufen lassen. Dann hab ich wenigstens eine
>> obere Schranke wenn er in der Zwischenzeit fertig werden sollte.
>
> ich wette dass er nicht vor morgen früh fertig ist :) wer steigt ein? :D


Ich!
Ich wette auf morgen mittag.

Ach ja. 40 Minuten sind durch :-)
(Ich hätte doch den Optimizer einschalten sollen :-)

[Klaus W. (mfgkw)]

ok, ihr rechnet offenbar ungeschickt....

in meiner ersten Variante habe ich ähnliche Laufzeiten:

klaus@a64a:~ > g++ -Wall -O3 hofstadter.cpp -o hofstadter  && ./hofstadter 
Q(1) ist 1 in 0 msec
Q(2) ist 1 in 0 msec
Q(3) ist 2 in 0 msec
Q(4) ist 3 in 0 msec
Q(5) ist 3 in 0 msec
Q(6) ist 4 in 0 msec
Q(7) ist 5 in 0 msec
Q(8) ist 5 in 0 msec
Q(9) ist 6 in 0 msec
Q(10) ist 6 in 0 msec
Q(11) ist 6 in 0 msec
Q(12) ist 8 in 0 msec
Q(13) ist 8 in 0 msec
Q(14) ist 8 in 0 msec
Q(15) ist 10 in 0 msec
Q(16) ist 9 in 0 msec
Q(17) ist 10 in 0 msec
Q(18) ist 11 in 0 msec
Q(19) ist 11 in 0 msec
Q(20) ist 12 in 0 msec
Q(21) ist 12 in 0 msec
Q(22) ist 12 in 0 msec
Q(23) ist 12 in 0 msec
Q(24) ist 16 in 0 msec
Q(25) ist 14 in 10 msec
Q(26) ist 14 in 10 msec
Q(27) ist 16 in 20 msec
Q(28) ist 16 in 30 msec
Q(29) ist 16 in 50 msec
Q(30) ist 16 in 80 msec
Q(31) ist 20 in 130 msec
Q(32) ist 17 in 160 msec
Q(33) ist 17 in 270 msec
Q(34) ist 20 in 420 msec
Q(35) ist 21 in 700 msec
Q(36) ist 19 in 1120 msec
Q(37) ist 20 in 1810 msec
Q(38) ist 22 in 2930 msec
Q(39) ist 21 in 4760 msec

In der zweiten Version geht es dann etwas schneller:

klaus@a64a:~ > g++ -Wall -O3 hofstadter.cpp -o hofstadter  && ./hofstadter 
Q(1) ist 1 in 0 msec
Q(2) ist 1 in 0 msec
Q(3) ist 2 in 0 msec
Q(4) ist 3 in 0 msec
Q(5) ist 3 in 0 msec
Q(6) ist 4 in 0 msec
Q(7) ist 5 in 0 msec
Q(8) ist 5 in 0 msec
Q(9) ist 6 in 0 msec
Q(10) ist 6 in 0 msec
Q(11) ist 6 in 0 msec
Q(12) ist 8 in 0 msec
Q(13) ist 8 in 0 msec
Q(14) ist 8 in 0 msec
Q(15) ist 10 in 0 msec
Q(16) ist 9 in 0 msec
Q(17) ist 10 in 0 msec
Q(18) ist 11 in 0 msec
Q(19) ist 11 in 0 msec
...
Q(9993) ist 4887 in 0 msec
Q(9994) ist 5139 in 0 msec
Q(9995) ist 5087 in 0 msec
Q(9996) ist 4866 in 0 msec
Q(9997) ist 4709 in 0 msec
Q(9998) ist 5411 in 0 msec
Q(9999) ist 4726 in 0 msec

:-)

[D. I. (Gast)]

Dynamische Programmierung ftw. das ist ein alter Hut um den es aber 
gerade nicht geht :P

[Klaus W. (mfgkw)]

was ist jetzt dynamische Programmierung?

[Karl H. (kbuchegg)]

Klaus Wachtler schrieb:
> ok, ihr rechnet offenbar ungeschickt....

:-)
Da läuft bewusst die völlig unoptimierte naive rekursive Version :-)

Schon klar, dass man da viel drehen kann. Das prinzipielle Problem, 
warum da die Laufzeit explodiert, ist ja bekannt. Ich will gar nicht 
wissen, wieviele Milliarden mal das Programm mittlerweile Q(3) als 
Zwischenergebnis berechnet hat

Btw. die erste Stunde ist bald rum

[Klaus W. (mfgkw)]

ok, ich rechne auch rekursiv.
Allerdings merke ich mir bereits berechnete Werte und verwende
die dann wieder, anstatt sie mehrfach neu zu bestimmen.

[Klaus W. (mfgkw)]

Hier der Quelltext.
Der Einfachheit halber in C++.

// Time-stamp: "09.01.10 19:05 t.txt klaus?wachtler.de"

#include <stdexcept>
#include <iostream>
#include <time.h>
#include <vararr.h>



// Ausnahmen für Fehler:
#define DERIVEEXCEPTION( NAME, BASENAME, TEXT )                         \
  class NAME : public BASENAME                                          \
    {                                                                   \
    public:                                                             \
      NAME( const std::string &_what = #NAME )                          \
        : BASENAME( std::string( TEXT ) + std::string( "\n" ) + _what ) \
        {}                                                              \
    }

DERIVEEXCEPTION(ErrUnderflow,std::runtime_error,"underflow");

int Q( int x )
{
  static VarArr< int >   Q_alt;
  if( x<1 )
  {
    throw ErrUnderflow("x<1 in Q()");
  }
  else if( x<=2 )
  {
    Q_alt[x] = 1;
    return 1;
  }
  else if( x<=Q_alt.og() )
  {
    // schon einmal berechnet? Dann einfach nehmen:
    return Q_alt[x];
  }
  else
  {
    // Wert noch nicht vorhanden, also berechnen.

    // falls noch nicht alle darunter liegenden Werte berechnet
    // wurden, dann nachholen:
    for( int i=Q_alt.og()+1; i<x; ++i )
    {
      Q( i );
    }

    // aktuellen Wert berechnen und ggf. merken:
    return ( Q_alt[x] = Q( x - Q( x - 1 ) ) + Q( x - Q( x - 2 ) ) );
  }
}


int main( int nargs, char **args )
{
  try
  {
    clock_t   start, ende;

    for( size_t i=1; i<10000; ++i )
    {
      start = clock();
      int   q = Q(i);
      ende = clock();
      std::cout << "Q(" << i << ") ist " << q << " in "
                << ( (double)( ende - start )/CLOCKS_PER_SEC*1000.0 ) << " msec"
                << std::endl;
    }
  }
  catch( std::exception &Fehler )
  {
    std::cerr << "Fehler: <"
              << Fehler.what()
              << "> in "
              << __PRETTY_FUNCTION__
              << "\n";
  }
  catch( ... )
  {
    std::cerr << "unbekannter Fehler in "
              << __PRETTY_FUNCTION__
              << "\n";
  }
}

Nötig ist dann noch ein dynamisches Feld aus vararr.h; siehe Anhang.
Daraus wird eine Methode og() verwendet, welche die bisherige
Obergrenze (also höchsten benutzten Index) liefert.
Ansonsten wird einfach mit [] aus Feldelemente zugegriffen und im
Hintergrund passend Platz dafür beschafft.

[Karl H. (kbuchegg)]

Klaus Wachtler schrieb:

> Nötig ist dann noch ein dynamisches Feld aus vararr.h; siehe Anhang.

Damit erklärt sich dann auch, was gemeinhin unter 'dynamischer 
Programmierung' verstanden wird: Wenn im Programm Datenstrukturen 
vorkommen, die zur Laufzeit wachsen bzw. schrumpfen.

[Klaus W. (mfgkw)]

Das hast du mit dem Stack doch sowieso... :-)

[Karl H. (kbuchegg)]

Klaus Wachtler schrieb:
> Das hast du mit dem Stack doch sowieso... :-)

LOL
Welcher Stack?

(Hintergrund: Der C-Standard fordert keinen Stack. Unterprogramme müssen 
wieder zum Aufrufer zurückfinden. Aber es ist nirgends spezifiziert, wie 
dieser Mechanismus zu geschehen hat. Solange eine zuverlässige 
Kristallkugel vorhanden ist, wäre die auch zulässig :-)
Ich geh mal davon aus, dass in meiner CPU winzigkleine Japaner wohnen, 
die über ein Mords Gedächtnis verfügen :-)

[Karl H. (kbuchegg)]

1 Stunde 10.
Ich geh mal Schnee vom Auto schaufeln und dann ab ins Kino.
Avatar in 3D


Sieht so aus, als ob das wieder mal ein wunderschönes Beispiel ist für

* Time for Space
  Investier ein bischen Speicher um die Laufzeit drastisch
  zu drücken

* Beim Optimieren auf algorithmischer Ebene anfangen
  Subtraktionen zu optimiern, hätte nicht viel gebracht

[Klaus W. (mfgkw)]

@khb:
Jetzt wirst du aber ziemlich pingelig.
Ob du es Stack nennst oder nichts davon wissen willst:
Bei rekursiver Programmierung brauchst du irgendwas dynamisches.

Aber im Ernst: Im OP wird ja auch für alle Werte ab 1 ein Feld
allokiert (iterative Version). Nichts anderes mache ich auch.
Nur halt aus Bequemlichkeit automatisch, dahinter steckt nichts
anderes als ein Feld mit allen Werten ab 1.

Du hattest ja mit deiner Aussage weiter oben vollkommen recht, daß
das wiederholte Berechnen der Zwischenwerte tötlich ist.
Diese zu cachen ist doch nicht illegitim, sondern einfach
sinnvoll m.E..

Selbst wenn du jetzt die Zeit hast, auf Q(50) zu warten, wirst du
halt bei Q(60) oder Q(100) scheitern mit dem päpstlichen Weg.

[Karl H. (kbuchegg)]

Klaus Wachtler schrieb:
> @khb:
> Jetzt wirst du aber ziemlich pingelig.
> Ob du es Stack nennst oder nichts davon wissen willst:
> Bei rekursiver Programmierung brauchst du irgendwas dynamisches.

Schon klar.
Aber üblicherweise wird der Stack bei der Betrachtung von 'dynamischer 
Programmierung' ausgeklammert.
Das würde ja sonst den ganzen Begriff ad absurdum führen. Denn jedes 
Programm, welches über Funktionsaufrufe verfügt, hat so etwas.

> Du hattest ja mit deiner Aussage weiter oben vollkommen recht, daß
> das wiederholte Berechnen der Zwischenwerte tötlich ist.
> Diese zu cachen ist doch nicht illegitim, sondern einfach
> sinnvoll m.E..

:-)
behauptet ja auch keiner, dass das illegitim wäre. Kann es sein, dass du 
das in den falschen Hals gekriegt hast?

> Selbst wenn du jetzt die Zeit hast, auf Q(50) zu warten, wirst du
> halt bei Q(60) oder Q(100) scheitern mit dem päpstlichen Weg.

Völlig klar.
Wenn ich demnächst einmal Zeit habe, baue ich mir eine Graphik wie die 
Rechenzeit ansteigt. Das wird ein Graph werden!

Aber was solls.
Der Rechner läuft sowieso und fadisiert sich die halbe Zeit.

[yalu (Gast)]

@Karl heinz:

Läuft das bei dir auf einem C64, oder hast du vielleicht noch die
Debug-Printfs noch drin? ;-)

Bei mir dauert es mit deiner Routine vom 08.01.2010 18:50 für etwas
größere n ziemlich genau

$$c\cdot \left(\frac{1+\sqrt 5}2\right)^n$$

wobei c=32.5ns eine rechnerabhängige Konstante ist (Pentium 4 3,2GHz).

[Klaus W. (mfgkw)]

na, dann viel Spaß mit 3D!

[Bert (Gast)]

Dynamische Programmierung war die nächste Aufgabe :D

[Karl H. (kbuchegg)]

yalu schrieb:
> @Karl heinz:
>
> Läuft das bei dir auf einem C64, oder hast du vielleicht noch die
> Debug-Printfs noch drin? ;-)

printf sind raus.
Debug Version, gebaut mit VC++ 6.0

Vis Studio ist offen, der Browser ist offen und da läuft auch sonst noch 
was im Hintergrund :-)

[Klaus W. (mfgkw)]

du kommst noch zu spät ins Kino....
Mit deiner Version kannst du auch danach noch nachsehen, ob er
fertig ist :-))

[yalu (Gast)]

Ohne die Gültigkeitsabfrage (n<1), die beiden Initialisierungen
zusammengefasst, das Ganze mit unsigned und mit -O3 statt -O2 kompiliert
(auf dem GCC), aber immer noch rekursiv, dauert es für n=50 noch 5m51.

#include <stdio.h>

unsigned int Q(unsigned int n) {
  if(n <= 2)
    return 1;
  return Q(n - Q(n - 1)) + Q(n - Q(n - 2));
}

int main(void) {
  printf("%d\n", Q(50));
  return 0;
}

Ich muss jetzt nämlich ebenfalls die Biege machen ;-)

@Karl Heinz:
Hast gerade eben einen Lauf auf dem Forenrechner gestartet, oder warum
hat der für ein paar Minuten nicht mehr geantwortet?

[Klaus W. (mfgkw)]

Der scheint depressiv zu werden, wenn khb geht...

[D. I. (Gast)]

Dynamische Programmierung bedeutet dass man sich Zwischenergebnisse in 
einer Tabelle merkt und wieder verwendet ;)

EDIT: Um noch ein bisschen klug zu scheißern handelt es sich um Top-Down 
DP auch Memoization genannt, daneben gibt es noch iteratives bottom-up 
DP :) Habe ich vor 2 Wochen meiner Erstitutoriumsgruppe verklickert :)
So jetzt beginnt auch unser DVD abend.

[Klaus W. (mfgkw)]

Danke, den Begriff kannte ich so noch nicht.
Es gibt sogar einen knappen Wikipedia-Artikel dazu.

Schönen Abend!

[Gerry E. (micky01)]

Apfelmännchen im Seepferdchental der Mandelbrotmenge ist auch eine 
schöne Übung zum Zeitvertreib :-)

[Klaus W. (mfgkw)]

Aber erst, wenn das einer als Hausaufgabe machen muß und selber
keine Lust dazu hat :-)

[Karl H. (kbuchegg)]

Habs leider übersehen, wann der Rechner fertig wurde :-(
Auf jeden Fall kommt 25 raus :-)


>> Apfelmännchen im Seepferdchental der Mandelbrotmenge ist
>> auch eine schöne Übung zum Zeitvertreib
> Aber erst, wenn das einer als Hausaufgabe machen muß und
> selber keine Lust dazu hat :-)

:-)
Ich liebe solche Fingerübungen. Kleine Programme, mit denen man so 
herrlich spielen kann.
In meiner Anfangszeit hab ich mir den Spass gemacht, mit der Stoppuhr 
neben dem Rechner einen Bubblesort zu 'trainieren'. Den konnte ich zum 
Schluss morgens um halb 4 fehlerfrei im Schlaf runterrasseln.
(Ein bischen einen Vogel darf jeder haben :-)