Problem bei C-Programm

[Furgy]

Hallo liebe Luxxer,

Ich hoffe ihr könnt mir helfen bei meinen Hausaufgaben.
Unser Lehrer hat uns einen Code mitgegeben um zu sehen, ob wir die "rekursiven Funktionen" verstanden haben...

Also die Aufgabe wirkt sehr Simpel:
Die Aufgabe lautet: Wieviele * werden ausgegeben?

Und der Code dazu:

[FONT="Courier New"][B]#include <stdio.h>

void Ast (int x)
{
 printf("***");
 if (x > 1)
 {
  Ast (x-1);
  Ast (x-2);
  Ast (x-1);
 }
}

int main ()
{
 Ast(47);
 return 0;
 system("Pause");
}[/B][/FONT]

Ich hoffe ihr könnt mir helfen

 

[Jean Pernod]

Ich würde mal tippen 48*3 = 144 Sternchen.

 

[André [HWLUXX]]

 

[Furgy]

@ Jean Pernod: Bisschen wenig

@ André [HWLUXX]: Danke

 

[Jean Pernod]

Ach so, scheisse hast recht.
Neuer Tipp: 48*47*48*3

 

[burni87]

schreib doch nach der printf zeile noch irgndwas in der art " sum = sum + 3;" ... dann weist es wieviel es sind ^^

 

[Furgy]

Also: Die Funktion wird mit 47 gestartet -> 3 Sterne
Dann ruft sie sich selber auf mit 46 -> 3 Sterne
...

So hab ich das verstanden...

//Edit: also wären es dann 47^46*3 Sterne ~ 2.5x10^77?

 

[burni87]

machs so wie ichs sage und führ das ganze aus und gibt dann das ergebniss aus, fertig ^^

oder musst dus so berechnen ?

 

[phubong]

Es ist fast unendlich!

mit 10 ist es schon 5044 "***", mit 20 ist es 33929305 "***", mit 47 ... ich weiße nicht, ich will mein CPU nicht braten!

 

[burni87]

Es ist fast unendlich!

mit 10 ist es schon 5044 "***", mit 20 ist es 33929305 "***", mit 47 ... ich weiße nicht, ich will mein CPU nicht braten!

ich schon, ich schreibs heute abend mal schnell in java und dann schau ich mal was da rauskommt ^^

 

[phubong]

mit 10 war es millisekunde, mit 20 so um 2 Sekunde, mit 30 dauert es 5 Minuten und noch nicht zu enden, ich habe es dann abgebrochen!

 

[tbird]

in meinen augen ist das durch "laufen lassen" nicht zu lösen ... hier muss ne formel her ...

 

[phubong]

Interessant! P4 2,8GHz

2: 6
3: 13
4: 29
5: 66
6: 154
7: 365
8: 873
9: 2098
10: 5054
11: 12189
12: 29413
13: 70994
14: 171378
15: 413725
16: 998801 - 15 milliseconds
17: 2411298 - 16
18: 5821366 - 31
19: 14053997 - 78
20: 33929325 - 219
21: 81912610 - 500
22: 197754506 - 1187
23: 477421581 - 2875
24: 1152597625 - 7031

 

[tbird]

ich lass grad mal mit 47 durchlaufen ... glaube aber nicht dass das in absehbarer zeit was wird, weil schon mit 30 hat das extrem lange gedauert...

 

[phubong]

Korrektur!

2: 4
3: 10
4: 25
5: 61
6: 148
7: 358
8: 865
9: 2084
10: 5044
11: 12178
12: 29401
13: 70981
14: 171364
15: 413710
16: 998785 - 15 milliseconds
17: 2411281 - 16
18: 5821348 - 31
19: 14053978 - 78
20: 33929305 - 219
21: 81912589 - 500
22: 197754484 - 1187
23: 477421558 - 2875
24: 1152597601 - 7031

 

[MacT2001]

sieht irgendwie so aus, als ob man die anzahl der Sterne ungefähr mit der formel:
sterne = sterne(n-2) + sterne(n-1)*2
rausbekommen kann.
Zumindest, wenn ich nach den Werten von phubong geh.

 

[burni87]

Korrektur!

2: 4
3: 10
4: 25
5: 61
6: 148
7: 358
8: 865
9: 2084
10: 5044
11: 12178
12: 29401
13: 70981
14: 171364
15: 413710
16: 998785 - 15 milliseconds
17: 2411281 - 16
18: 5821348 - 31
19: 14053978 - 78
20: 33929305 - 219
21: 81912589 - 500
22: 197754484 - 1187
23: 477421558 - 2875
24: 1152597601 - 7031

es werden immer 3 sterne pro aufruf gespeichert, dh du musst dein ergebniss noch mit 3 multipliziern
Hinzugefügter Post:
btw: lass grad mit 47 laufen ... der eine core läuft auf vollast und wird verdammt heiss

 

[phubong]

Klar! da sind nicht die Anzahlen der Sterne sondern die Anzahlen der Aufrufen.

 

[burni87]

ok

 

[DFC-Neo]

sieht so aus als ob keiner hier rekursive aufrufe verstanden hat ;-)
Im Hauptprogramm wird die Funktion Ast aufgerufen, x hat den Wert 47.
Dann werden 3 * ausgegeben. Dann ruft sich Ast selber auf mit x= 47-1 => 3*, dann wieder selber aufgerufen mit x=46-1... solange bis x=1 ist. Dann wird die IF-Schleife nicht durchlaufen nachdem die 3* ausgegeben wurden.
Das heißt der letzte Aufruf von Ast wird fertig durchgeführt und im das Programm springt zurück in den vorletzten Aufruf der Funktion. Dann kommt als nächstes der Aufruf mit x-2, auch hier wird die IF-Schleife nicht durchlaufen. als nächstes der dritte Aufruf, ebenfalls ohne IF-Schleife. dann gehts im 3.-letzten Aufruf weiter mit dem Aufruf x-2. der dürfte dann auch noch ohne if-schleife durchlaufen werden, währende der 3. aufruf einmal durch geht.
Und dann geht das ganze so wieder hoch bis zum hauptprogramm. Gibt also jede Menge Sternchen


01. Aufruf x=47 1x3*
02. Aufruf x=46 2x3=6*
03. Aufruf x=45 3x3=9*
04. Aufruf x=44 4x3=12*
usw bis x=2
46. Aufruf x=2 46x3 = 138*
47. Aufruf x=1 47x3 = 141* IF-Schleife wird nicht durchlaufen, Rücksprung zum 46. Aufruf, hier wird jetzt das 2. Mal Ast aufgerufen, mit x-2=0
48. Aufruf x=0 48x3=144* IF-Schleife wird nicht durchlaufen, Rücksprung zum 46. Aufruf, hier wird jetzt das 3. Mal Ast aufgerufen, mit x-1=1
49. Aufruf x=1 49x3=147* IF-Schleife wird nicht durchlaufen, Rücksprung zum 46. Aufruf. Wird beendet, Rücksprung zum 45. mit x-2=1
50. Aufruf x=1 50x3=150* IF-Schleife wird nicht durchlaufen, Rücksprung zum 45. Aufruf, hier wird jetzt das 3. Mal Ast aufgerufen, mit x-1=2
51. Aufruf x=2 51x3=153* Jetzt wird die IF-Schleife durchlaufen
52. Aufruf x=1 52x3=156* IF-Schleife wird nicht durchlaufen, Rücksprung zum 51. Aufruf, hier wird jetzt das 2. Mal Ast aufgerufen, mit x-2=0

und so weiter und so fort. (siehe 47. Aufruf)
Die Formel darfst du dir jetzt selber daraus zusammenbasteln, SO langweilig ist mir dann doch noch nicht
Alle Angaben ohne Gewähr!

 

[phubong]

@DFC-Neo: das was Du erklärt ist so alt wie die Programmierung selbst. Es ist einfach wenn es nur den ersten Aufruf, Ast(x -1), gibt. Der Knackpunkt ist daß nach der Rücksprung weiteren Aufrufen folgen und ich glaube Du verstehst hier auch nicht richtig. Du darfst selber testen und wirst überrascht sein!

 

[Gelöschtes Mitglied 45455]

O(3^n) ?

 

[Furgy]

Und für was steht O?

 

[Gelöschtes Mitglied 45455]

Das steht für "wächst höchstens so schnell wie".
Landau Symbole

Das würde ja einen Baum von Knoten mit jeweils drei Kindern geben und die Tiefe des Baumes ist ja etwa n. Denke das passt dann so.

 

[DFC-Neo]

@DFC-Neo: das was Du erklärt ist so alt wie die Programmierung selbst. Es ist einfach wenn es nur den ersten Aufruf, Ast(x -1), gibt. Der Knackpunkt ist daß nach der Rücksprung weiteren Aufrufen folgen und ich glaube Du verstehst hier auch nicht richtig. Du darfst selber testen und wirst überrascht sein!

Genau das habe ich doch geschrieben, dass nach dem Rücksprung der nächste Aufruf kommt also der mit x-2 usw.

 

[tbird]

So...die Laufzeit beträg jetzt schon fast 21 Stunden, und es ist noch kein Ende in Sicht

Mal schaun wann das Programm eine Ausgabe auf den Schirm zaubert (ich glaube das dauert aber noch ne weile ^^)

//edit: kommilitone kam grad, und wir haben die komplexität des programms mit O(3^n) bestimmt. das würde bedeuten, dass das dingens bei n=47 einige TAUSEND jahre laufen würde ...

 

[Gelöschtes Mitglied 45455]

Hab mal so rumgerechnet, der Supercomputer in Jülich mit 50Teraflop bräuchte dann mindestens 18 Jahre für die Berechnung und das ist noch optimistisch gerechnet.

 

[tbird]

tja, was uns bei der lösung des problems, wie oft das dingens durchrennt, ned weiterhilft.

eine formel muss irgendwie her.

 

[Furgy]

Hallo,

Ich hab das mal mit einem Mitarbeiter angeschaut, der eigentlich c++ programmiert, aber c ist ja c++ ohne die guten Funktionen

Folgendes kam raus:

folgender lösungsansatz: ast(1) = 1 ausdruck

1 ausdruck = 3 sternchen

ast(2) = 4 ausdruck

ast(3) = 10 ausdruck

ast(x) = 2*ast(x-1) + ast(x -2) + 1 ausdruck

also z.b. ast(3) = ast(2) * 2 + ast(1) + 1 = 4*2 + 1 + 1 = 10

lässt man das programm in diesem muster von unten nach oben
und nicht von oben nach unten mit ewiger rekursion
rechnen erhält man schneller das ergebnis.

mein programm zur berechnung der ausgedruckten sterne:

int sternchen (int aststart)
{
  int x1 = 1;		'Wert für ast(1) schon ausgerechnet
  int x2 = 4;		'Wert für ast(2) schon ausgerechnet
  int speicher = 0;
  int count = 2;	'da wir ast(1) und ast(2) 
chon haben starten wir bei 2
  while(count != aststart)
  {
    count++;
    speicher = x2;
    x2 = x2·2 + x1 + 1;	'folgt der Formel: ast(x)=ast(x-1)*2+ast(x-2)+1
    x1 = speicher;	'setze x1 auf altes x2
  }
  return(x2);
}

sternchen(47) =733699924308655918
und weil immer 3 sterne gedruckt werden werden insgesamt 733699924308655918 * 3
= 2201099772925967754 sterne gedruckt