Ackermannsche Funktion

[Xknight]

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:

und hier ist der code dazu.

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;

 

[mihe7]

Darum meine Frage, ob ihr mal über meinen Code drüberschauen könntet ob sie richtig ist oder nicht?

Klar. Code ist falsch.

 

[LimDul]

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.

 

[ocsme]

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

 

[kneitzel]

Zeit wann darf man den var Schreiben? Java14? K. A. =D

Typinferenz ist mit Java 10 gekommen. Das nur als kleine Anmerkung.

 

[Xknight]

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.

 

[LimDul]

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.

Alles.

Beschreib mal, wie du das lösen willst. Wie soll sich deine ArrayDequeue verhalten?

 

[Xknight]

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.

 

[LimDul]

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.

 

[Xknight]

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

 

[Xknight]

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

 

[LimDul]

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]

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.

 

[Xknight]

Heißt das ich soll zuersst mal einen Stack programmieren?

 

[LimDul]

Sinnvoll wäre erst mal Java zu lernen Zumindest anhand der Beispiele mangelt es daran bereits.

 

[BestGoalkeeper]

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

 

[BestGoalkeeper]

Hier mal der Wink mit dem Zaunpfahl (du brauchst zwei Stacks, wenn du oben angegebene Definition 1 zu 1 umsetzen möchtest):

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));
            }
        }
    }
}

 

[mihe7]

du brauchst zwei Stacks, wenn du oben angegebene Definition 1 zu 1 umsetzen möchtest

Nein, einer reicht.

 

[BestGoalkeeper]

Nein, einer reicht.

Zeigen...

Edit, aber der Sche*** hält für f(4,1) bei mir fast nicht an.

 

[mihe7]

Zeigen...

Hier:

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.

 

[BestGoalkeeper]

Ok, will nix gesagt haben

 

[mihe7]

Edit, aber der Sche*** hält für f(4,1) bei mir fast nicht an.

LOL, die unoptimierte Variante läuft auf meiner alten Möhre 120 s, die etwas optimiertere 42 s.

 

[BestGoalkeeper]

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

 

[mihe7]

Mom, ich schick Dir den Code per PN.

EDIT:

aber ich bin trotzdem etwas schneller fertig als die Kurbelmaschine

Hey, nix gegen meinen Turion(tm) 64 X2 Mobile Technology TL-64

 

[BestGoalkeeper]

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

 

[mihe7]

Du kurbelst nur schneller.

 

[BestGoalkeeper]

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. Ä.

 

[fhoffmann]

Du kurbelst nur schneller.

Ich habe an meinem Computer (Baujahr 1980) noch eine "Turbo"-Taste. Aber wo kann ich die Kurbel ansetzen, um ihn noch mehr zu beschleunigen?

 

[mihe7]

Ich habe an meinem Computer (Baujahr 1980) noch eine "Turbo"-Taste. Aber wo kann ich die Kurbel ansetzen, um ihn noch mehr zu beschleunigen?

Der ist nicht XK-kompatibel.

 

[MoxxiManagarm]

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

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)
}

 

[BestGoalkeeper]

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:

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:

65533
65533
51137 49584

Etwas höheres als (4, 1) ist damit so oder so nicht berechenbar

 

[kneitzel]

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:

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]

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.