Ackermannfunktion < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:25 Do 29.03.2012 | | Autor: | bandchef |
| Aufgabe | | Ich soll die rekursive Ackermannfunktion in einer iterativen nachbilden... |
Wie die Ackermannfunktion definiert ist, kann man ja auf wiki nachlesen. Mir gehts jetzt eher darum wie ich das Teil jetzt nachbilde. Eine while-Schleife sollte genügen hat man mir gesagt. Wie schafft man das? Kann mir jemand helfen?
Mein bisheriger Versuch:
| 1: |
| | 2: | unsigned int ackIt(unsigned int m, unsigned int n)
| | 3: | {
| | 4: | stack myStack(100);
| | 5: |
| | 6: | while((!myStack.isEmpty() == true) || (n > 0)) //so lange auf'm Stack was drauf is oder n größer 0, macht die Schleife weiter
| | 7: | {
| | 8: | if(n == 0)
| | 9: | {
| | 10: |
| | 11: | }
| | 12: | else if((m == 0) && (n >= 1))
| | 13: | {
| | 14: |
| | 15: | }
| | 16: | else
| | 17: | {
| | 18: |
| | 19: | }
| | 20: | }
| | 21: | }
|
|
|
| |
|
Hi!
Die Grundidee zur Lösung ist die dynamnische Programmierung. Dabei versucht du eine rekusrive Formel für ein Problem zu finden (hast Du ja schon gegeben) und diese dann effizient mit Hilfe eines (eventuell mehrdimensionalen) Arrays zu berechnen. Das heißt Du fängst sozusagen "unten" bei der Abbruchbedingung (n = 0 / m = 0) an und berechnest dann Stück für Stück die Werte für höhere n/m.
Das Gute dabei ist, dass du schon berechnete Werte zwischenspeicherst, sodass dynamische Programmierung sehr effizient ist.
Ich habe jetzt die Formel von Peter für die Ackermannfunktion als Grundlage genommen (siehe Wikipedia):
| 1: |
| | 2: | unsigned int ackIt(unsigned int n, unsigned int m) {
| | 3: | unsigned int ar[n][m];
| | 4: | unsigned int i_n = 0;
| | 5: | unsigned int i_m = 0;
| | 6: |
| | 7: | while(i_m < m) {
| | 8: | ar[0][i_m] = m+1;
| | 9: | ++i_m;
| | 10: | }
| | 11: |
| | 12: | while(i_n < n)
| | 13: | a[i_n][0] = a[i_n-1][1];
| | 14: | ++i_n;
| | 15: | }
| | 16: |
| | 17: | i_n = 1;
| | 18: | while(i_n < n) {
| | 19: | i_m = 1;
| | 20: | while(i_m < n) {
| | 21: | a[i_n][i_m] = a[i_n-1][a[i_n][i_m-1]];
| | 22: | ++i_m;
| | 23: | }
| | 24: | ++i_n;
| | 25: | }
| | 26: | return a[n-1][m-1];
| | 27: | } |
Das Ganze ist ungetestet und ich habe das gerade "mal eben" programmiert. Also kann das auch durchaus sehr falsch sein. Der Einfachheit halber habe ich es nicht in einer while-Schleife verpackt, wobei das natürlich auch möglich wäre ;)
Ich hoffe, das hilft Dir.
Gruß Pille
|
|
|
|
