Entrekursivierung

[forsti222]

Hei, da melde ich mich wieder mal.
Habe gerade die Aufgabe 1 gelöst und musste da nen rekursiven Algorithmus für die Stirling zahl machen. Funktioniert auch soweit : (Verbesserungen immer gerne willkommen)

class Stirling {
	
	static int stirling(int n, int k) {
		int result = 0;
		//initStack();
		if(n==k) {
			result = 1;
		}
		else if(k==0 && (n>0 || n<k)) {
			result = 0;
		}
		else {
			int result1 = stirling(n-1,k-1);
			int result2 = k*stirling(n-1,k);
			result = result1+result2;
		}
		return result;
	}
 
	public static void main(String[] args) {
		System.out.print(stirling(4,2));
	}
    
         
}

Jetzt stellt sich für mich die Frage, wie kann ich diesen entrekursivieren. Ist nämlich aufgabe 2. Idee habe ich etzt nur dies über Schleifen zu lösen? Aber kann ich da irgendwie vorgehen. Wäre über Lösungsansätze sehr dankbar

lg forsti

 

[Technoblade]

Ich kann dir im Moment nur Tipps geben und kann nicht mal eben selber was programmieren, da ich gleich los muss, aber wenigstens ein bisschen. Du solltest auf jeden Fall mit einem Stack arbeiten. In dem kannst du dann die Ergenisse der einzelnen Rechnungen schreiben. Dazu würde ich dir eine while-Schleife verwenden mit der Abbruchbedingung, dass der Stack die Größe 1 hat, denn in diesem Fall enthält der Stack ja nur noch das Endergebnis. Wenn ich heute Abend nochmal Zeit/Lust habe programmiere ich auch nochmal was.

Ich hoffe das hilft dir schonmal ein wenig.


EDIT: Hab noch nen bisschen nachgedacht, in den Stack müssen die Zwischenwerte für n und k rein. Die Schleife sollte abbrechen wenn n und k die entsprechenden Werte erreichen. Nachher kannst du dann mit den Werten aus dem Stack das Ergebnis ausrechnen-

 

[forsti222]

Würde mich freuen falls du mir das am Abend ausprogrammieren könntest.. habe mit stacks noch nicht soviel Ahnung und bin mir ziemlich unsicher wie das gehen soll!

danke

 

[HonniCilest]

Es handelt sich hiebei um die zweite Art oder? Müsste es in der Zeile 9 nicht eher so heißen?:

else if((k==0 && n>0) || n<k) {

Denn laut Wikipedia....

rekursive Formel


mit den Anfangsbedingungen

Sn,n = 1 und
Sn,k = 0 für k = 0 < n oder n < k .

 

[forsti222]

Ja stimmt, mein Fehler... Hast du bezüglich des entrekursivieren auch einen vorschlag für mich?

 

[HonniCilest]

Ähm ich war nicht zwingend die Beste in Mathe, jedoch würde ich die explizite Formel von Wikipedia so interpretieren:

//fakul soll eine Funktion darstellen, die die Fakultät eines Ausdruckes berechnet...

public int stirling(int n, int k)
{
	int sum = 0;

	for(int j = 0; j <= k; j++)
	{
		int x1 = (int)Math.pow(-1, k - j);
		int x2 = fakul(k) / (fakul(j) * fakul(k - j));
		int x3 = (int)Math.pow(j, n);
		sum += x1 * x2 * x3;
	}

	return sum / fakul(k);
}

Wie gesagt, absolut ohne Gewähr!

 

[Technoblade]

Hmm, da wäre es jetzt interessant zu wissen wie exakt die Aufgabestellung lautet. Wenn es lediglich darum geht eine iterative Implementation der Methode anzugeben reicht der Quelltext von dir HonniCilest, aber wenn die rekursive Methode in eine iterative Umgewandelt werden soll reicht es nicht, da eine andere Formel als Grundlage verwendet wird.

Ich habe jetzt auf jeden Fall nochmal eine Methode welche die Rekursive Formel verwendet, aber selbst nicht rekursiv ist. Damit die funktioniert musst du am Anfang der Klasse java.util.Stack importieren.

public int stirlingIt(int n, int k) {
    //Stacks für die Werte von k, n und den Faktor der über die einzelnen Durchläufe entsteht
    Stack<Integer> nStack = new Stack<Integer>();
    Stack<Integer> kStack = new Stack<Integer>();
    Stack<Integer> fStack = new Stack<Integer>();
    int result = 0;
    
    //Befüllen der Stacks mit den Startwerten
    nStack.push(n);
    kStack.push(k);
    fStack.push(1);
    while(nStack.size() != 0 && kStack.size() != 0 && fStack.size() != 0) {
        n = nStack.pop();
        k = kStack.pop();
        int factor = fStack.pop();
        if(n == k) {
            result += factor;
        }
        else if(!((k==0 && n>0) || n<k)) {
            nStack.push(n - 1);
            kStack.push(k);
            fStack.push(factor * k);
            nStack.push(n - 1);
            kStack.push(k - 1);
            fStack.push(factor);
        }
    }
    return result;
}

Sollte sich herausstellen, dass diese Lösung gefragt war und nicht die HonniCilest mache ich mir (wenn erwünscht) auch gerne nochmal die Mühe und erkläre wieso das funktioniert.