Hofstadters Folgen in C

Bert Gast #1546817
Lesenswert?
• ▲
▼ 
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:

1
int Iterativ( int n ) 

2
{

3
  int i=0;

4
  int *ptr;

5
  ptr = (int *) malloc( n * sizeof(int));

6


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

8


9
  for(i=2;i<=n;++i){

10
    ptr[i]=ptr[i-ptr[i-1]] + ptr[i-ptr[i-2]] }

11


12
  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
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Karl H. #1546827
Lesenswert?
• ▲
▼ 
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) )


1
int Q( int n )

2
{

3
  if( n == 1 )

4
    return 1;

5


6
  if( n == 2 )

7
    return 1;

8


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

10
}
Antwort Zitieren Bearbeiten Löschen Beitrag melden
yalu Gast #1546832
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Bert Gast #1546892
Lesenswert?
• ▲
▼ 
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

1
 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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1546897
Lesenswert?
• ▲
▼ 
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:
1
int Q( int n )

2
{

3
  if( n < 1 ) {

4
    printf( "ungültiges n: %d\n", n );

5
    return 1;   // man könnte hier auch einen exit() machen

6
                // aber dagegen habe ich eine Abneigung :-)

7
  }

8


9
  if( n == 1 )

10
    return 1;

11


12
  if( n == 2 )

13
    return 1;

14


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

16
}
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1546903
Lesenswert?
• ▲
▼ 
Bert schrieb:

> Die beiden oberen Zeilen sind klar, mein Problem ist einfach, dass ich
> mir nicht vorstellen kann, dass diese Zeile
>
1
>  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 :-)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1546920
Lesenswert?
• ▲
▼ 
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.

1
#include <stdio.h>

2


3
void Indent( int Level )

4
{

5
  int i;

6
  for( i = 0; i < Level; ++i )

7
    printf( " " );

8
}

9


10
int Q( int n, int Level )

11
{

12
  int Sum1, Sum2;

13


14
  Indent( Level );

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

16


17
  Level++;

18


19
  if( n == 1 ) {

20
    Indent( Level );

21
    printf( "trivial, das ist 1\n" );

22
    return 1;

23
  }

24


25
  if( n == 2 ) {

26
    Indent( Level );

27
    printf( "trivial, das ist 1\n" );

28
    return 1;

29
  }

30


31
  Indent( Level );

32
  printf( "Gesucht Q( %d - Q( %d ) )\n", n, n - 1 );

33
  Sum1 = Q( n - Q( n - 1, Level ), Level );

34


35
  Indent( Level );

36
  printf( "Gesucht Q( %d - Q( %d ) )\n", n, n - 2 );

37
  Sum2 = Q( n - Q( n - 2, Level ), Level );

38


39
  Indent( Level );

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

41


42
  return Sum1 + Sum2;

43
}

44


45
int main()

46
{

47
  printf( "-> ergebnis %d\n", Q( 6, 0 ) );

48
}
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Bert Gast #1546937
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1546954
Lesenswert?
• ▲
▼ 
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 :-)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Michael H. #1546956
Lesenswert?
• ▲
▼ 
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))
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1546972
Lesenswert?
• ▲
▼ 
So ist die Berechnung (die immer noch dieselbe ist) noch ein wenig mehr 
aufgedröselt und das Protokoll noch leichter zu lesen

1
#include <stdio.h>

2


3
void Indent( int Level )

4
{

5
  int i;

6
  for( i = 0; i < 2*Level; ++i )

7
    printf( " " );

8
}

9


10
int Q( int n, int Level )

11
{

12
  int Sum1, Sum2, Tmp;

13


14
  Indent( Level );

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

16


17
  Level++;

18


19
  if( n == 1 ) {

20
    Indent( Level );

21
  printf( "trivial, das ist 1\n" );

22
    return 1;

23
  }

24


25
  if( n == 2 ) {

26
    Indent( Level );

27
  printf( "trivial, das ist 1\n" );

28
    return 1;

29
  }

30


31
  Indent( Level );

32
  printf( "Zu berechnen ist Q( %d - Q( %d ) ) + Q( %d - Q( %d ) )\n", n, n-1, n, n - 2 );

33
  printf( "\n" );

34
  Indent( Level );

35
  printf( "Gesucht Q( %d - Q( %d ) )\n", n, n - 1 );

36
  Indent( Level );

37
  printf( "Dazu brauche ich Q(%d)\n", n - 1 );

38
  Tmp = Q( n - 1, Level + 1 );

39
  Indent( Level );

40
  printf( "Q(%d) ergibt also %d\n", n - 1, Tmp );

41
  Indent( Level );

42
  printf( "Und jetzt Q( %d - %d ) = Q(%d)\n", n, Tmp, n - Tmp );

43
  Sum1 = Q( n - Tmp, Level );

44
  Indent( Level );

45
  printf( "Q( %d - Q( %d ) ) ergibt also %d\n", n, n - 1, Sum1 );

46


47
  printf( "\n" );

48
  Indent( Level );

49
  printf( "Gesucht Q( %d - Q( %d ) )\n", n, n - 2 );

50
  Indent( Level );

51
  printf( "Dazu brauche ich Q(%d)\n", n - 2 );

52
  Tmp = Q( n - 2, Level + 1 );

53
  Indent( Level );

54
  printf( "Q(%d) ergibt also %d\n", n - 2, Tmp );

55
  Indent( Level );

56
  printf( "Und jetzt Q( %d - %d ) = Q(%d)\n", n, Tmp, n - Tmp );

57
  Sum2 = Q( n - Tmp, Level );

58
  Indent( Level );

59
  printf( "Q( %d - Q( %d ) ) ergibt also %d\n", n, n - 2, Sum2 );

60


61
  Indent( Level );

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

63


64
  return Sum1 + Sum2;

65
}

66


67
int main()

68
{

69
  printf( "-> ergebnis %d\n", Q( 4, 0 ) );

70
}


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

1
Berechne Q(4)

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

3


4
  Gesucht Q( 4 - Q( 3 ) )

5
  Dazu brauche ich Q(3)

6
    Berechne Q(3)

7
      Zu berechnen ist Q( 3 - Q( 2 ) ) + Q( 3 - Q( 1 ) )

8


9
      Gesucht Q( 3 - Q( 2 ) )

10
      Dazu brauche ich Q(2)

11
        Berechne Q(2)

12
          trivial, das ist 1

13
      Q(2) ergibt also 1

14
      Und jetzt Q( 3 - 1 ) = Q(2)

15
      Berechne Q(2)

16
        trivial, das ist 1

17
      Q( 3 - Q( 2 ) ) ergibt also 1

18


19
      Gesucht Q( 3 - Q( 1 ) )

20
      Dazu brauche ich Q(1)

21
        Berechne Q(1)

22
          trivial, das ist 1

23
      Q(1) ergibt also 1

24
      Und jetzt Q( 3 - 1 ) = Q(2)

25
      Berechne Q(2)

26
        trivial, das ist 1

27
      Q( 3 - Q( 1 ) ) ergibt also 1

28
      Q(3) = 1 + 1 = 2

29
  Q(3) ergibt also 2

30
  Und jetzt Q( 4 - 2 ) = Q(2)

31
  Berechne Q(2)

32
    trivial, das ist 1

33
  Q( 4 - Q( 3 ) ) ergibt also 1

34


35
  Gesucht Q( 4 - Q( 2 ) )

36
  Dazu brauche ich Q(2)

37
    Berechne Q(2)

38
      trivial, das ist 1

39
  Q(2) ergibt also 1

40
  Und jetzt Q( 4 - 1 ) = Q(3)

41
  Berechne Q(3)

42
    Zu berechnen ist Q( 3 - Q( 2 ) ) + Q( 3 - Q( 1 ) )

43


44
    Gesucht Q( 3 - Q( 2 ) )

45
    Dazu brauche ich Q(2)

46
      Berechne Q(2)

47
        trivial, das ist 1

48
    Q(2) ergibt also 1

49
    Und jetzt Q( 3 - 1 ) = Q(2)

50
    Berechne Q(2)

51
      trivial, das ist 1

52
    Q( 3 - Q( 2 ) ) ergibt also 1

53


54
    Gesucht Q( 3 - Q( 1 ) )

55
    Dazu brauche ich Q(1)

56
      Berechne Q(1)

57
        trivial, das ist 1

58
    Q(1) ergibt also 1

59
    Und jetzt Q( 3 - 1 ) = Q(2)

60
    Berechne Q(2)

61
      trivial, das ist 1

62
    Q( 3 - Q( 1 ) ) ergibt also 1

63
    Q(3) = 1 + 1 = 2

64
  Q( 4 - Q( 2 ) ) ergibt also 2

65
  Q(4) = 1 + 2 = 3

66
-> 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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
yalu Gast #1547018
Lesenswert?
• ▲
▼ 
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).
Angehängte Dateien:
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1547904
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
D. I. Gast #1547906
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1547909
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
D. I. Gast #1547913
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1547939
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
D. I. Gast #1547948
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1547960
Lesenswert?
• ▲
▼ 
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 :-)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Klaus W. #1547966
Lesenswert?
• ▲
▼ 
ok, ihr rechnet offenbar ungeschickt....

in meiner ersten Variante habe ich ähnliche Laufzeiten:
1
klaus@a64a:~ > g++ -Wall -O3 hofstadter.cpp -o hofstadter  && ./hofstadter 

2
Q(1) ist 1 in 0 msec

3
Q(2) ist 1 in 0 msec

4
Q(3) ist 2 in 0 msec

5
Q(4) ist 3 in 0 msec

6
Q(5) ist 3 in 0 msec

7
Q(6) ist 4 in 0 msec

8
Q(7) ist 5 in 0 msec

9
Q(8) ist 5 in 0 msec

10
Q(9) ist 6 in 0 msec

11
Q(10) ist 6 in 0 msec

12
Q(11) ist 6 in 0 msec

13
Q(12) ist 8 in 0 msec

14
Q(13) ist 8 in 0 msec

15
Q(14) ist 8 in 0 msec

16
Q(15) ist 10 in 0 msec

17
Q(16) ist 9 in 0 msec

18
Q(17) ist 10 in 0 msec

19
Q(18) ist 11 in 0 msec

20
Q(19) ist 11 in 0 msec

21
Q(20) ist 12 in 0 msec

22
Q(21) ist 12 in 0 msec

23
Q(22) ist 12 in 0 msec

24
Q(23) ist 12 in 0 msec

25
Q(24) ist 16 in 0 msec

26
Q(25) ist 14 in 10 msec

27
Q(26) ist 14 in 10 msec

28
Q(27) ist 16 in 20 msec

29
Q(28) ist 16 in 30 msec

30
Q(29) ist 16 in 50 msec

31
Q(30) ist 16 in 80 msec

32
Q(31) ist 20 in 130 msec

33
Q(32) ist 17 in 160 msec

34
Q(33) ist 17 in 270 msec

35
Q(34) ist 20 in 420 msec

36
Q(35) ist 21 in 700 msec

37
Q(36) ist 19 in 1120 msec

38
Q(37) ist 20 in 1810 msec

39
Q(38) ist 22 in 2930 msec

40
Q(39) ist 21 in 4760 msec


In der zweiten Version geht es dann etwas schneller:
1
klaus@a64a:~ > g++ -Wall -O3 hofstadter.cpp -o hofstadter  && ./hofstadter 

2
Q(1) ist 1 in 0 msec

3
Q(2) ist 1 in 0 msec

4
Q(3) ist 2 in 0 msec

5
Q(4) ist 3 in 0 msec

6
Q(5) ist 3 in 0 msec

7
Q(6) ist 4 in 0 msec

8
Q(7) ist 5 in 0 msec

9
Q(8) ist 5 in 0 msec

10
Q(9) ist 6 in 0 msec

11
Q(10) ist 6 in 0 msec

12
Q(11) ist 6 in 0 msec

13
Q(12) ist 8 in 0 msec

14
Q(13) ist 8 in 0 msec

15
Q(14) ist 8 in 0 msec

16
Q(15) ist 10 in 0 msec

17
Q(16) ist 9 in 0 msec

18
Q(17) ist 10 in 0 msec

19
Q(18) ist 11 in 0 msec

20
Q(19) ist 11 in 0 msec

21
...

22
Q(9993) ist 4887 in 0 msec

23
Q(9994) ist 5139 in 0 msec

24
Q(9995) ist 5087 in 0 msec

25
Q(9996) ist 4866 in 0 msec

26
Q(9997) ist 4709 in 0 msec

27
Q(9998) ist 5411 in 0 msec

28
Q(9999) ist 4726 in 0 msec


:-)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1547987
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Klaus W. #1547992
Lesenswert?
• ▲
▼ 
Hier der Quelltext.
Der Einfachheit halber in C++.

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

2


3
#include <stdexcept>

4
#include <iostream>

5
#include <time.h>

6
#include <vararr.h>

7


8


9


10
// Ausnahmen für Fehler:

11
#define DERIVEEXCEPTION( NAME, BASENAME, TEXT )                         \

12
  class NAME : public BASENAME                                          \

13
    {                                                                   \

14
    public:                                                             \

15
      NAME( const std::string &_what = #NAME )                          \

16
        : BASENAME( std::string( TEXT ) + std::string( "\n" ) + _what ) \

17
        {}                                                              \

18
    }

19


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

21


22
int Q( int x )

23
{

24
  static VarArr< int >   Q_alt;

25
  if( x<1 )

26
  {

27
    throw ErrUnderflow("x<1 in Q()");

28
  }

29
  else if( x<=2 )

30
  {

31
    Q_alt[x] = 1;

32
    return 1;

33
  }

34
  else if( x<=Q_alt.og() )

35
  {

36
    // schon einmal berechnet? Dann einfach nehmen:

37
    return Q_alt[x];

38
  }

39
  else

40
  {

41
    // Wert noch nicht vorhanden, also berechnen.

42


43
    // falls noch nicht alle darunter liegenden Werte berechnet

44
    // wurden, dann nachholen:

45
    for( int i=Q_alt.og()+1; i<x; ++i )

46
    {

47
      Q( i );

48
    }

49


50
    // aktuellen Wert berechnen und ggf. merken:

51
    return ( Q_alt[x] = Q( x - Q( x - 1 ) ) + Q( x - Q( x - 2 ) ) );

52
  }

53
}

54


55


56
int main( int nargs, char **args )

57
{

58
  try

59
  {

60
    clock_t   start, ende;

61


62
    for( size_t i=1; i<10000; ++i )

63
    {

64
      start = clock();

65
      int   q = Q(i);

66
      ende = clock();

67
      std::cout << "Q(" << i << ") ist " << q << " in "

68
                << ( (double)( ende - start )/CLOCKS_PER_SEC*1000.0 ) << " msec"

69
                << std::endl;

70
    }

71
  }

72
  catch( std::exception &Fehler )

73
  {

74
    std::cerr << "Fehler: <"

75
              << Fehler.what()

76
              << "> in "

77
              << __PRETTY_FUNCTION__

78
              << "\n";

79
  }

80
  catch( ... )

81
  {

82
    std::cerr << "unbekannter Fehler in "

83
              << __PRETTY_FUNCTION__

84
              << "\n";

85
  }

86
}


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.
Angehängte Dateien:
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1547995
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1548006
Lesenswert?
• ▲
▼ 
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 :-)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1548010
Lesenswert?
• ▲
▼ 
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Klaus W. #1548011
Lesenswert?
• ▲
▼ 
@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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1548018
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
yalu Gast #1548023
Lesenswert?
• ▲
▼ 
@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


wobei c=32.5ns eine rechnerabhängige Konstante ist (Pentium 4 3,2GHz).
Angehängte Dateien:
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1548036
Lesenswert?
• ▲
▼ 
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 :-)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
yalu Gast #1548049
Lesenswert?
• ▲
▼ 
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.

1
#include <stdio.h>

2


3
unsigned int Q(unsigned int n) {

4
  if(n <= 2)

5
    return 1;

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

7
}

8


9
int main(void) {

10
  printf("%d\n", Q(50));

11
  return 0;

12
}


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?
Antwort Zitieren Bearbeiten Löschen Beitrag melden
D. I. Gast #1548065
Lesenswert?
• ▲
▼ 
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl H. #1548445
Lesenswert?
• ▲
▼ 
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 :-)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren