Ackermann iterativ in K&R C: falsche Werte

[EinNutzer0]

Hallo, ich möchte die Ackermann-Funktion iterativ umsetzen.
Code:

#include <stdio.h>
#include <stdlib.h>

struct ByteContent
{
    char *content;
    int len;
};

struct Node
{
    struct Node *next;
    struct ByteContent *byte_content;
};

struct Node *root = 0;
int len = 0;

struct Node *get_node(int n)
{
    struct Node *tn = root;
    int i = 0;
    if (n < 0)
    {
        return 0;
    }
    for (; i < len && i < n; i++)
    {
        tn = tn->next;
    }
    return tn;
}

struct ByteContent *get_byte_content(int n)
{
    if (n < 0 || n >= len)
    {
        return 0;
    }
    return get_node(n)->byte_content;
}

void insert(int n, struct ByteContent *bc)
{
    struct Node *tn0 = get_node(n - 1);
    struct Node *tn1 = get_node(n);
    struct Node *tn2 = 0;
    if (n < 0 || n > len || bc == 0)
    {
        return;
    }
    tn2 = (struct Node *)malloc(sizeof(struct Node *));
    tn2->byte_content = bc;
    tn2->next = tn1;
    if (tn0 == 0)
    {
        root = tn2;
    }
    else
    {
        tn0->next = tn2;
    }
    len++;
}

struct ByteContent *delete (int n)
{
    struct Node *tn0 = 0;
    struct Node *tn1 = 0;
    struct ByteContent *temp = 0;
    if (n < 0 || n >= len)
    {
        return 0;
    }
    tn0 = get_node(n - 1);
    tn1 = get_node(n);
    temp = tn1->byte_content;
    if (tn0 == 0)
    {
        root = root->next;
    }
    else
    {
        tn0->next = tn1->next;
    }
    free(tn1);
    len--;
    return temp;
}

unsigned long int ackermann(unsigned long int x, unsigned long int y)
{
    struct ByteContent *a = 0, *b = 0;
    unsigned long int *e = 0, *f = 0;
    unsigned long int r = 0;
    a = malloc(sizeof(struct ByteContent *));
    e = malloc(sizeof(unsigned long int *) * 3);
    a->content = (char *)e;
    e[0] = x;
    e[1] = y;
    e[2] = 0;
    insert(0, a);
    while (len > 0)
    {
        a = delete (0);
        e = (unsigned long int *)a->content;
        r = e[2];
        if (e[0] == 0)
        {
            if (len == 0)
            {
                r = e[1] + 1;
            }
            else
            {
                f = (unsigned long int *)get_byte_content(0);
                f[2] = e[1] + 1;
            }
        }
        else if (e[1] == 0)
        {
            b = malloc(sizeof(struct ByteContent *));
            f = malloc(sizeof(unsigned long int *) * 3);
            b->content = (char *)f;
            f[0] = e[0] - 1;
            f[1] = 1;
            f[2] = 0;
            insert(0, b);
        }
        else
        {
            /* Im else-Teil stimmt etwas nicht... */
            b = malloc(sizeof(struct ByteContent *));
            f = malloc(sizeof(unsigned long int *) * 3);
            b->content = (char *)f;
            f[0] = e[0] - 1;
            f[1] = e[2];
            f[2] = 0;
            insert(0, b);

            b = malloc(sizeof(struct ByteContent *));
            f = malloc(sizeof(unsigned long int *) * 3);
            b->content = (char *)f;
            f[0] = e[0];
            f[1] = e[1] - 1;
            f[2] = 0;
            insert(0, b);
        }
        free(e);
        free(a);
    }
    return r;
}

int main(int argc, char **argv)
{
    printf("f(%d, %d) = %lu\n", 0, 0, ackermann(0, 0));
    printf("f(%d, %d) = %lu\n", 0, 1, ackermann(0, 1));
    printf("f(%d, %d) = %lu\n", 0, 2, ackermann(0, 2));
    printf("f(%d, %d) = %lu\n", 0, 3, ackermann(0, 3));
    printf("f(%d, %d) = %lu\n", 0, 4, ackermann(0, 4));
    printf("f(%d, %d) = %lu\n", 1, 0, ackermann(1, 0));
    printf("f(%d, %d) = %lu\n", 1, 1, ackermann(1, 1));
    printf("f(%d, %d) = %lu\n", 1, 2, ackermann(1, 2));
    printf("f(%d, %d) = %lu\n", 1, 3, ackermann(1, 3));
    printf("f(%d, %d) = %lu\n", 1, 4, ackermann(1, 4));
    return 0;
}

Die Ausgabe ist aber:

f(0, 0) = 1
f(0, 1) = 2
f(0, 2) = 3
f(0, 3) = 4
f(0, 4) = 5
f(1, 0) = 2
f(1, 1) = 1
f(1, 2) = 1
f(1, 3) = 1
f(1, 4) = 1

eigentlich sollte die Ausgabe aber sein:

f(0, 0) = 1
f(0, 1) = 2
f(0, 2) = 3
f(0, 3) = 4
f(0, 4) = 5
f(1, 0) = 2
f(1, 1) = 3
f(1, 2) = 4
f(1, 3) = 5
f(1, 4) = 6

Was hab ich falsch gemacht? Ich vermute, dass im else-Teil etwas nicht stimmt, also wenn x und y beide größer 0 sind...

[Ein ehemaliger Benutzer]

Wo ist da K&R C?

[EinNutzer0]

@manni66 sagte in Ackermann iterativ in K&R C: falsche Werte:

Wo ist da K&R C?

Meine natürlich ANSI C

[Swordfish]

@EinNutzer0 sagte in Ackermann iterativ in K&R C: falsche Werte:

ANSI C

Wann kapierst Du endlich daß es nicht nur eine ANSI Norm für C gibt???

[EinNutzer0]

Jetzt erhalte ich folgende Ausgabe:

f(0, 0) = 1
f(0, 1) = 2
f(0, 2) = 3
f(0, 3) = 4
f(0, 4) = 5
f(1, 0) = 2
f(1, 1) = 3
f(1, 2) = 4
f(1, 3) = 5
f(1, 4) = 6
f(2, 0) = 3
f(2, 1) = 5
f(2, 2) = 7
f(2, 3) = 9
f(2, 4) = 11
f(3, 0) = 5
f(3, 1) = 8
f(3, 2) = 11
f(3, 3) = 14
f(3, 4) = 17

Das ist bis f(3, 0) richtig und danach falsch...

unsigned long int ackermann(unsigned long int x, unsigned long int y)
{
    struct ByteContent *a = 0, *b = 0;
    unsigned long int *e = 0, *f = 0;
    unsigned long int r = 0;
    a = malloc(sizeof(struct ByteContent *));
    e = malloc(sizeof(unsigned long int *) * 3);
    a->content = (char *)e;
    e[0] = x;
    e[1] = y;
    e[2] = 0;
    insert(0, a);
    while (len > 0)
    {
        a = delete (0);
        e = (unsigned long int *)a->content;
        r += e[2];
        if (len > 0)
        {
            f = (unsigned long int *)get_byte_content(0);
            f[2] = r;
        }
        if (e[0] == 0)
        {

            if (len == 0)
            {
                r += e[1] + 1;
            }
            else
            {
                f = (unsigned long int *)get_byte_content(0);
                f[2] = e[1] + 1;
                r += e[1] + 1;
            }
        }
        else if (e[1] == 0)
        {
            b = malloc(sizeof(struct ByteContent *));
            f = malloc(sizeof(unsigned long int *) * 3);
            b->content = (char *)f;
            f[0] = e[0] - 1;
            f[1] = 1;
            f[2] = 0;
            insert(0, b);
        }
        else
        {
            /* Im else-Teil stimmt etwas nicht... */
            b = malloc(sizeof(struct ByteContent *));
            f = malloc(sizeof(unsigned long int *) * 3);
            b->content = (char *)f;
            f[0] = e[0] - 1;
            f[1] = e[2];
            f[2] = 0;
            insert(0, b);

            b = malloc(sizeof(struct ByteContent *));
            f = malloc(sizeof(unsigned long int *) * 3);
            b->content = (char *)f;
            f[0] = e[0];
            f[1] = e[1] - 1;
            f[2] = 0;
            insert(0, b);
        }
        free(e);
        free(a);
    }
    return r;
}

int main(int argc, char **argv)
{
    int x = 0, y = 0;
    for (x = 0; x < 4; x++)
    {
        for (y = 0; y < 5; y++)
        {
            printf("f(%d, %d) = %lu\n", x, y, ackermann(x, y));
        }
    }
    return 0;
}

Wenn man sich die rekursive Definition anschaut: https://www.geeksforgeeks.org/ackermann-function/
was geschieht dann im ersten und im dritten Fall?

[*john 0]

@Swordfish sagte in Ackermann iterativ in K&R C: falsche Werte:

Wann kapierst Du endlich daß es nicht nur eine ANSI Norm für C gibt???

Das stimmt nicht. Es gab nämlich nur eine ANSI Norm die von 1989, diese wurde 1990 zur ISO Norm. Danach gab es nur noch ISO Normen, die von ANSI als nationale Normen übernommen wurden.

[Swordfish]

@john-0 sagte in Ackermann iterativ in K&R C: falsche Werte:

die von ANSI als nationale Normen übernommen wurden.

boah ey. wodurch sie zu ANSI Normen wurden. Dasselbe für die ÖNORM die regelmäßig DIN übernimmt.

[*john 0]

@Swordfish sagte in Ackermann iterativ in K&R C: falsche Werte:

boah ey. wodurch sie zu ANSI Normen wurden.

Nein, nicht mehr – es sind INCITS/ISO/IEC Normen bzw. nur noch ISO/IEC Normen.

[EinNutzer0]

Wollt ihr mir helfen oder lieber eine Runde schnacken?

[Ein ehemaliger Benutzer]

@EinNutzer0 sagte in Ackermann iterativ in K&R C: falsche Werte:

Wollt ihr mir helfen oder lieber eine Runde schnacken?

Hier eine Impl. in Java, nichrekursiv.
Ist leicht in C umzubauen.
Musst nur einen Stack programmieren (kleines Array und ein Pointer).

    public static int itFunc (int m, int n)
    {
        Stack<Integer> s = new Stack<Integer>();
        s.add(m);
        while(!s.isEmpty())
        {
            m=s.pop();
            if(m==0||n==0)
                n+=m+1;
            else{
                s.add(--m);
                s.add(++m);
                n--;
            }
        }
        return n;
    }

[EinNutzer0]

@A-Grau Vielen Dank

in Java brauchte ich dafür zwei Stacks:

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

Dass es auch einfacher geht, hast du ja schon gezeigt.

[Ein ehemaliger Benutzer]

@EinNutzer0 sagte in Ackermann iterativ in K&R C: falsche Werte:

in Java brauchte ich dafür zwei Stacks:

Das finde ich übertrieben. Hier eine Java-Version ganz ohne Stack (und mit Test):
gibt das aus, was du erwartest.

public class TestAck
{
    public static void main(String[] args)
    {
        System.out.println(itFunc(0,4));
        System.out.println(itFunc(1,0));
        System.out.println(itFunc(1,1));
        System.out.println(itFunc(1,2));
        System.out.println(itFunc(1,3));
        System.out.println(itFunc(1,4));
    }

    public static int itFunc (int m, int n)
    {
        int[] arr = new int[1000];
        int p = 0;
        arr[p++] = m;
        while(p!=0)
        {
            m = arr[--p];
            if(m==0||n==0)
                n+=m+1;
            else
                {
                arr[p++] = --m;
                arr[p++] = ++m;
                n--;
            }
        }
        return n;
    }
}

Musst du nur noch C daraus machen. Ist aber jetzt besonders leicht.

[Wutz]

@EinNutzer0
Was genau soll der Verkettete-Liste-Unsinn hier?