Ackermannsche Funktion

X

Xknight

Aktives Mitglied
Guten Tag, ich wollte die Ackermannsche Funktion implementieren und habe sie auch implementiert, nur weiß ich nicht ob sie richtig ist. Darum meine Frage, ob ihr mal über meinen Code drüberschauen könntet ob sie richtig ist oder nicht? Hier ist die Ackermannsche Funktion:
1604835027468.png

und hier ist der code dazu.
Java:
static int variable;
    public static int farmguy(int x, int y) {
        var stack = new ArrayDequeue<Integer>();
        
        while(stack.isEpmty) {
        
            if(x == 0) {
                y.stack.add(variable);
            }
            
            if(x < 0 && y == 0) {
                y = stack.removeLast(variable);
            }
            
            if(x > 0 && y > 0) {
                x = stack.removeLast(variable);
                y = stack.removeLast(variable);
            }
            
            
        }
        
        
        return stack;
 
L

LimDul

Top Contributor
Nein ist sie nicht. Zum einen kompiliert sie nicht. Zum anderen verstehe ich nicht, was deine Schleife mit der Ackermann Funktion zu tun hat. Die läuft solange der Stack leer ist. Das hört sich nicht sinnvoll an. Die Bedingung x < 0 ist mir auch schleierhaft. Variable wird nie initalisiert.

Tipp: Probier die Funktion mal aus, was passiert.
 
O

ocsme

Top Contributor
Hallo,
also ich würde an deiner Stelle den Stack so weg lassen und die Funktion rekursiv aufbauen.
Dazu glaube ich kaum das das hier Java Code ist oder? Zeit wann darf man den var Schreiben? Java14? K. A. =D
In Kotlin geht das glaube ich =D

Bei der Rekrusion gehst du folgendermaßen vor:
wenn x = 0 ist: gibt y + 1 zurück
anders wenn y = 0: Funktion(x - 1, 1)
und anders Funktion(x - 1, Funktion(x, y -1))

Durch die Rekursion hast du dein Stack :)
Viel Erfolg weiterhin :)
 
X

Xknight

Aktives Mitglied
Naja ich wollte die Ackermann Funktion mit dem import ArrayDequeue lösen und kann einer mir mal sagen was ich so ändern muss, damit der Code richtig wird.
 
X

Xknight

Aktives Mitglied
Neben der Funktion stehen halt die Bedingungen und bei dem ersten fall soll raus kommen, wenn x == 0 ist dann soll der code y+1 geben und da dachte ich mir das wird mit y.stack.add variable geschehen und beim zweiten fall , wenn x> 0 und y == 0 ist dann soll der code mir x-1,1 geben und da dachte ich mir das geht mit x = stack.removeLast gehen und beim letzten fall wenn x > o und y > 0 ist dann soll der code mir x-1, x,y-1 geben und da dachte ich mir dass geht mit x = stack.removeLast und y = stack.removeLast.
 
L

LimDul

Top Contributor
Hast du überhaupt eine Ahnung wie ein Stack funktioniert? Und wie Java funktioniert?
y ist ein int - da gibt es keine y.stack
Vraible ist eine int variable ohne Wert.

Und warum sollte removeLast gehen? Warum steht da an letzter Stelle im Stack das richtige drin? Der Code hat null komma nix mit der Ackermann Funktion zu tun und den dürfte man auch nicht so leicht dahin bekommen. Dir scheinen massiv Grundlagen zu fehlen.
 
X

Xknight

Aktives Mitglied
Darum habe ich euch doch gefragt, ob mein Code richtig ist oder nicht. Und wollte von euch Hilfe bekommen wenn mein Code falsch ist.
 
X

Xknight

Aktives Mitglied
Ausserdem hatte ich keine theoretische Informatik und wusste auch nicht was es mit dem Code zu tun hat.
 
L

LimDul

Top Contributor
Der Punkt ist - dein Code ist nicht nur falsch, er ist total unsinnig. Der ist so sinnvoll wie gar kein Code. Und hier hat eher selten jemand Lust die komplette Aufgabe zu lösen. @ocsme hat ja schon eine Lösung gescrieben. Ansonsten - beschreib mal exakt was du wie machen willst (nicht direkt java, sondern umgangssprachlich) wie es funktionieren soll. Mal dir ein paar Bilder wie sich dein Stack verhalten soll - wann kommt was rein, wann kommt was raus. Ich bin mir nicht mal sicher, ob ich die Ackermann Funktion überhaupt so einfach mit einem DeQueue Objekt lösen kann.
 
mihe7

mihe7

Top Contributor
Zwischen Code falsch und Code falsch gibt es einen himmelweiten Unterschied, ein Stack hat auch nichts mit theoretischer Informatik zu tun. Ein Stack ist ein Stapel, auf den kannst Du was legen und "von oben" wieder entfernen/abrufen - wie bei einem Stapel Papier.

Die Idee beim Stack wäre z. B. folgende: man legt die Parameter auf den Stack, die eigentliche Funktion holt sich die Parameter vom Stack und legt das Ergebnis auf den Stack.
 
L

LimDul

Top Contributor
Sinnvoll wäre erst mal Java zu lernen :) Zumindest anhand der Beispiele mangelt es daran bereits.
 
BestGoalkeeper

BestGoalkeeper

Top Contributor
Hm, fang damit an, die Rekursion in der dritten Zeile der rekursiven Definition aufzudröseln, so dass dort keine Rekursion mehr vorkommt ;)
 
BestGoalkeeper

BestGoalkeeper

Top Contributor
Hier mal der Wink mit dem Zaunpfahl (du brauchst zwei Stacks, wenn du oben angegebene Definition 1 zu 1 umsetzen möchtest):
Java:
import java.util.ArrayDeque;

public class Test {
    public static class Callee {
        long x, y, r;

        public Callee(long x, long y, long r) {
            this.x = x;
            this.y = y;
            this.r = r;
        }
    }

    public static long ackermann(int x, int y) {
        long r = 0;
        ArrayDeque<Callee> stack_a = new ArrayDeque<>();
        ArrayDeque<Callee> stack_b = new ArrayDeque<>();
        stack_a.add(new Callee(x, y, 0));
        while (!(stack_a.isEmpty() && stack_b.isEmpty())) {
            if (!stack_a.isEmpty()) {
                Callee c = stack_a.removeFirst();
                if (c.x == 0) {
                    r = c.y + 1;
                } else if (c.y == 0) {
                    stack_a.addFirst(new Callee(c.x - 1, 1, 0));
                } else {
                    stack_a.addFirst(new Callee(c.x, c.y - 1, 0));
                    stack_b.addFirst(new Callee(c.x - 1, 0, 0));
                }
            } else {
                Callee c = stack_b.removeFirst();
                c.y = r;
                stack_a.add(c);
            }
        }
        return r;
    }

    public static void main(String[] args) {
        for (int x = 0; x < 4; x++) {
            for (int y = 0; y < 5; y++) {
                System.out.printf("f(%d, %d) = %d%n", x, y, ackermann(x, y));
            }
        }
    }
}
 
BestGoalkeeper

BestGoalkeeper

Top Contributor
Ähnliches bei mir, obwohl als Wert ja eigentlich nur 65533 herauskommen sollte... aber ich bin trotzdem etwas schneller fertig als die Kurbelmaschine :)
 
BestGoalkeeper

BestGoalkeeper

Top Contributor
Ich würde sagen, mein Gerät ist um 666 % schneller als deins ;) (Also etwa 6,5mal so schnell) Aber in der Steinzeit war ja auch nicht alles schlecht ;)
 
BestGoalkeeper

BestGoalkeeper

Top Contributor
Btw, Was mir schon die ganze Zeit in den Augen brennt... Der Spaß heißt Ackermann-Funktion und nicht Ackermannsche Funktion.
Das "-sche" ist nur wenigen als feststehender Begriff im deutschen Sprachgebrauch vorbehalten. Beispiele: die schillerschen oder Schiller'schen Balladen, Glocke o. Ä.
 
MoxxiManagarm

MoxxiManagarm

Top Contributor
Eigentlich steht die Lösung bei diesen Definitionen doch immer schon da. Du musst sie nur nochmal 1:1 in Programmcode niederschreiben.

1604909447738.png


Java:
public int f(int x, int y) {
  if (x == 0) return y + 1;
  if (x > 0 && y == 0) return f(x-1, 1);
  // Du weißt selbst wie die letzte Zeile aussehen muss ;-)
  // (und ggf. Error-Handling für negative Werte)
}
 
Zuletzt bearbeitet:
BestGoalkeeper

BestGoalkeeper

Top Contributor
Ja aber er möchte ja eine nicht-rekursive Version haben...
Bei der Version mit den zwei Stacks macht es btw noch einen Unterschied, ob vorne oder hinten angehängt wird, wegen der Fehlerbehandlung:
Java:
import java.util.ArrayDeque;

public class Test {
    public static class Callee {
        long x, y;

        public Callee(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    public static long ackermann(int x, int y) {
        long r = 0;
        ArrayDeque<Callee> stack_a = new ArrayDeque<>();
        ArrayDeque<Callee> stack_b = new ArrayDeque<>();
        stack_a.addFirst(new Callee(x, y));
        while (!(stack_a.isEmpty() && stack_b.isEmpty())) {
            if (!stack_a.isEmpty()) {
                Callee c = stack_a.removeFirst();
                if (c.x == 0) {
                    r = c.y + 1;
                } else if (c.y == 0) {
                    stack_a.addFirst(new Callee(c.x - 1, 1));
                } else {
                    stack_a.addFirst(new Callee(c.x, c.y - 1));
                    stack_b.addFirst(new Callee(c.x - 1, 0));
                }
            } else {
                Callee c = stack_b.removeFirst();
                c.y = r;
                stack_a.add(c);
            }
        }
        return r;
    }

    public static long ackermann2(int x, int y) {
        long r = 0;
        ArrayDeque<Callee> stack_a = new ArrayDeque<>();
        ArrayDeque<Callee> stack_b = new ArrayDeque<>();
        stack_a.addLast(new Callee(x, y));
        while (!(stack_a.isEmpty() && stack_b.isEmpty())) {
            if (!stack_a.isEmpty()) {
                Callee c = stack_a.pollLast();
                if (c.x == 0) {
                    r = c.y + 1;
                } else if (c.y == 0) {
                    stack_a.addLast(new Callee(c.x - 1, 1));
                } else {
                    stack_a.addLast(new Callee(c.x, c.y - 1));
                    stack_b.addLast(new Callee(c.x - 1, 0));
                }
            } else {
                Callee c = stack_b.pollLast();
                c.y = r;
                stack_a.addLast(c);
            }
        }
        return r;
    }

    public static void main(String[] args) {
        long t0 = System.currentTimeMillis();
        System.out.println(ackermann(4, 1));
        long t1 = System.currentTimeMillis();
        System.out.println(ackermann2(4, 1));
        long t2 = System.currentTimeMillis();
        System.out.println((t1 - t0) + " " + (t2 - t1));
    }
}
Ca. 1,5 Sekunden Unterschied:
Code:
65533
65533
51137 49584
Etwas höheres als (4, 1) ist damit so oder so nicht berechenbar ;)
 
kneitzel

kneitzel

Top Contributor
Wozu zwei Stacks? Ein Stack reicht voll und ganz aus:
Man legt die zwei Parameter auf den Stack. So lange der Stack mindestens zwei Parameter enthält, werden die zwei Parameter entnommen und ähnlich wie bei der rekursiven Arbeitsweise dann der Stack befüllt:
Bei x==0 kommt das Ergebnis auf den Stack
bei x >0 und y ==0 kommen die Werte: x-1 und 1 auf den Stack (Was dem Aufruf f(x-1, 1) entspricht.
Und sonst kommen x-1, x, y-1 auf den Stack. Denn er nimmt ja die letzten 2 Elemente und berechnet diese, das Ergebnis kommt dann am Ende da auf den Stack, so dass x-1, f(x, y-1) auf dem Stack liegen, was dann ja dem f(x-1, f(x, y-1)) entspricht.

Sobald auf dem Stack nur nur eine Zahl liegt, ist die das Ergebnis.

Der Code würde also z.B. so aussehen können:
Java:
import java.util.ArrayDeque;
import java.util.Deque;

public class Test {

    public static int ackermannRekursiv(final int x, final int y) {
        if (x == 0) return y + 1;
        if (x > 0 && y == 0) return ackermannRekursiv(x-1, 1);
        return ackermannRekursiv(x-1, ackermannRekursiv(x, y-1));
    }

    public static int ackermannIterativ(final int x, final int y) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(x);
        stack.push(y);

        while (stack.size() >= 2) {
            int yValue = stack.pop();
            int xValue = stack.pop();

            if (xValue == 0) {
                stack.push(yValue + 1);
            } else if (xValue > 0 && yValue == 0) {
                stack.push(xValue - 1);
                stack.push(1);
            } else {
                stack.push(xValue - 1);
                stack.push(xValue);
                stack.push(yValue - 1);
            }
        }

        return stack.pop();
    }

    public static void testAckerman(final int x, final int y) {
        System.out.print("Ackermann(" + x + "," + y + ") = ");
        int resultRekursiv = ackermannRekursiv(x, y);
        System.out.print("Rekursiv: " + resultRekursiv);
        int resultIterativ = ackermannIterativ(x, y);
        System.out.println(" Iterativ: " + resultIterativ);

        if (resultIterativ != resultRekursiv) {
            System.err.println("Unterschiedliche Ergebnisse!");
        }
    }

    public static void main(String[] args) {
        testAckerman(0,1);
        testAckerman(1,1);
        testAckerman(2,2);
    }
}
 
BestGoalkeeper

BestGoalkeeper

Top Contributor
Ich meine, die Ackermann-Funktion wird oft auch im Compilerbau verwendet, um zu testen, ob die Rekursion funktioniert - weil es davon eben so viele unterschiedliche "Schreibweisen" gibt. ;)

Darüber hinaus ist so eine sehr schnell wachsende Funktion in der theoretischen Informatik natürlich unheimlich interessant, um die "Grenzen" der "Berechenbarkeit" zu zeigen.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Tino1993 Ellipse über draw Funktion ohne spur wandern lassen Java Basics - Anfänger-Themen 6
F Arrays: Mathematische Funktion Java Basics - Anfänger-Themen 19
P Dezimal zu Hexadezimalzahl Funktion Java Basics - Anfänger-Themen 5
S Verwenden von throw Exception an der Funktion Java Basics - Anfänger-Themen 2
M Arrays in Funktion Kopieren und Bearbeiten Java Basics - Anfänger-Themen 4
B Funktion mit mehreren Rückgabewerten aka Prozeduren? Java Basics - Anfänger-Themen 12
J Dynamisches Array durch split()-Funktion? Java Basics - Anfänger-Themen 3
D Funktion nur 1 Rueckgabewert Java Basics - Anfänger-Themen 9
M Wie lang eine Funktion/Methode? Java Basics - Anfänger-Themen 51
N den inhalt eines array per funktion ausgeben Java Basics - Anfänger-Themen 8
R Ackermann Funktion Java Basics - Anfänger-Themen 2
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
D Funktion zwei Arraylisten zu verleichen ob gleich funktioniert nicht Java Basics - Anfänger-Themen 26
N Abfragen eines Textes aus einem JTextField in Java, Funktion, CardLayout, Java Basics - Anfänger-Themen 2
T Rekursion Warum bricht meine Funktion nicht ab Java Basics - Anfänger-Themen 4
N Funktion funktioniert nicht immer Java Basics - Anfänger-Themen 6
E Contain-funktion überlisten Java Basics - Anfänger-Themen 4
J Division ohne Arithmetische Funktion Java Basics - Anfänger-Themen 2
S Funktion in Klasse auslagern Java Basics - Anfänger-Themen 4
J Problem mit Boolean bei Funktion! Java Basics - Anfänger-Themen 5
S Gibt es eine Funktion, die gewissermaßen eine Reihe von instanceOf() vereinheitlicht? Java Basics - Anfänger-Themen 19
D Nullstellen einer Funktion 3. Grades mit Horner Schema Java Basics - Anfänger-Themen 6
Aprendiendo Gibt es in der JAVA-API eine Funktion, die eine Dezimalzahl in eine binäre Zahl umwandelt? Java Basics - Anfänger-Themen 8
D Funktion gibt Dimension zurück Java Basics - Anfänger-Themen 11
A Rekursion Funktion in eine Iterativ Funktion umwandeln Java Basics - Anfänger-Themen 8
T static String Variable wird nur beim ersten aufruf durch eine Funktion geändert. Java Basics - Anfänger-Themen 16
B Zugriffe in einer Klasse / Funktion Java Basics - Anfänger-Themen 9
T Koordinatensystem zeichnen - Variablen merken? Quadratische Funktion zeichnen? Java Basics - Anfänger-Themen 5
J Array innerhalb einer Funktion mehrfach iniatilisieren Java Basics - Anfänger-Themen 4
T Lambda-Funktion bei Binärbäumen Java Basics - Anfänger-Themen 13
J Wie lässt sich der Konstruktor einer Klasse einer Funktion einer Klasse nutzen. Java Basics - Anfänger-Themen 4
M Thread.sleep() Funktion Java Basics - Anfänger-Themen 1
B OOP Wie benutze ich die Main Funktion richtig? Java Basics - Anfänger-Themen 10
H Nicht Static Funktion ohne Objekt aufrufen? Java Basics - Anfänger-Themen 6
K Methoden mit den Namen accept. Welche Funktion haben diese? Java Basics - Anfänger-Themen 2
E Compare-Funktion bei eigener Klasse Java Basics - Anfänger-Themen 4
S Threads run - Funktion wird nur einmal ausgeführt. Java Basics - Anfänger-Themen 8
B Anwender soll mathematische Funktion eingeben können, Einfachster Fnktionsplotter Java Basics - Anfänger-Themen 4
R If Funktion funktioniert nicht :P Java Basics - Anfänger-Themen 3
H Funktion in Hintergrund und Vordergrund ausführen Java Basics - Anfänger-Themen 11
S Funktion die mir fuer einen String eine Zahl zwischen 0.0 und 1.0 zurueckliefert..? Java Basics - Anfänger-Themen 9
S Funktion eines Stacks Java Basics - Anfänger-Themen 4
T Integer-Objekt über Hash-Funktion in Array ablegen Java Basics - Anfänger-Themen 1
S Separate Funktion für JUnit-Test Java Basics - Anfänger-Themen 3
D Keine Funktion bei "else" Java Basics - Anfänger-Themen 5
S timer funktion mit javax panel Java Basics - Anfänger-Themen 3
T Klassen Funktion in einem Funktionsaufruf definieren Java Basics - Anfänger-Themen 3
F Funktion eines JButton in einen Vektor verlagern Java Basics - Anfänger-Themen 4
X Eval-Funktion mit Variable Java Basics - Anfänger-Themen 2
T Screenreader Funktion Java Basics - Anfänger-Themen 2
S Wertetabelle einer Funktion f : R -> R Java Basics - Anfänger-Themen 1
P Methoden suche funktion die char wert ausgibt wenn man numerischen wert und radix angibt Java Basics - Anfänger-Themen 1
1 repaint() Funktion erzeugt Flackern Java Basics - Anfänger-Themen 33
J Taschenrechner Funktion Java Basics - Anfänger-Themen 18
R if funktion ohne else - Bedingung trifft nicht zu, ausgabe nicht nachvollziehbar Java Basics - Anfänger-Themen 7
shiroX OOP Java Funktion implementieren Java Basics - Anfänger-Themen 3
O Debug-Funktion mit Slick - Kleines Problem Java Basics - Anfänger-Themen 5
F Funktion immer zur vollen Stunde? Java Basics - Anfänger-Themen 3
S ResultSet close() in funktion nich möglich. Java Basics - Anfänger-Themen 8
C Meine erste Funktion Java Basics - Anfänger-Themen 12
J Funktion um JSON per Post senden/emfangen Java Basics - Anfänger-Themen 3
G OOP Aus Objekt auf Funktion der erzeuger Klasse zugreifen? Java Basics - Anfänger-Themen 11
D Binäre Suche für Integerarray in rekursiver Funktion Java Basics - Anfänger-Themen 5
M Interface als Konstruktorparameter nutzen, um Funktion zu plotten Java Basics - Anfänger-Themen 14
NR_EIGHT Benutzereingabe in Funktion verpacken Java Basics - Anfänger-Themen 4
J Funktion definieren und ausfuehren Java Basics - Anfänger-Themen 27
D Loop Funktion für Robot Klasse Java Basics - Anfänger-Themen 5
N mathematische Funktion Java Basics - Anfänger-Themen 29
R Programm verstehen, Funktion Java Basics - Anfänger-Themen 4
C Automatisches Ausfuehren einer Funktion beim Laden eines Jar files Java Basics - Anfänger-Themen 3
O Nicht Standard Form boolesche Funktion in Standard Form parsen Java Basics - Anfänger-Themen 3
F Sleep Funktion Java Basics - Anfänger-Themen 12
S Euklid Funktion Java Basics - Anfänger-Themen 8
H Funktion mit Argumenten Java Basics - Anfänger-Themen 5
Q Random Funktion JButtons Java Basics - Anfänger-Themen 6
O Probleme mit der repaint-Funktion Java Basics - Anfänger-Themen 6
F Eine Frage über paint() Funktion Java Basics - Anfänger-Themen 2
S Parameterübergabe - identische Funktionen, aber falsche Funktion Java Basics - Anfänger-Themen 5
C Probleme mit replaceAll Funktion Java Basics - Anfänger-Themen 9
S Vector mit beliebigen Klassen an Funktion übergeben Java Basics - Anfänger-Themen 20
C OOP Java JButton mit Funktion belegen Java Basics - Anfänger-Themen 3
A klasse[] funktion Java Basics - Anfänger-Themen 2
K Lampda funktion ? Java Basics - Anfänger-Themen 11
B Erste Schritte ergebnis der funktion in der main-methode ausgeben Java Basics - Anfänger-Themen 7
M Feldaustritt Funktion in java Java Basics - Anfänger-Themen 5
W Funktion zum Prüfen Java Basics - Anfänger-Themen 11
P int Array direkt einer Funktion übergeben Java Basics - Anfänger-Themen 3
M Funktion der Mutterklasse aus Kindklasse aufrufen?? Java Basics - Anfänger-Themen 19
Dit_ Funktion alle 24 Stunden ein mal aufrufen Java Basics - Anfänger-Themen 3
A Verstehe readLine()-Funktion nicht Java Basics - Anfänger-Themen 3
S Extremwerte einer Funktion Java Basics - Anfänger-Themen 11
I Befehl wird erst nach dem Ausführen einer Funktion ausgeführt Java Basics - Anfänger-Themen 4
I Funktion erst starten nachdem eine komplett fertig ist Java Basics - Anfänger-Themen 4
F Variablen brighter darker funktion Java Basics - Anfänger-Themen 5
F Methoden Fehler finden in Funktion Java Basics - Anfänger-Themen 3
W Funktion Matrizenmultiplikation Java Basics - Anfänger-Themen 15
P Funktion zeichnen Java Basics - Anfänger-Themen 6
Y add Funktion für GridBagLayout zeigt Button nicht an Java Basics - Anfänger-Themen 3
C funktion-ausgabe unklar Java Basics - Anfänger-Themen 10
D Klassen Funktion in Klasse einbauen Java Basics - Anfänger-Themen 5

Ähnliche Java Themen

Anzeige

Neue Themen


Oben