Pascalsches Dreieck - rekursiv

bbskater

Hallo Leute. Ich habe folgendes Problem: rekursive Berechnung des Pascalschen Dreiecks.

Die iterative Berechnung ist kein Problem, die habe ich schon gemacht. Mir fehlt aber der Ansatz, wie das ganze rekursiv berechne.

Hier mein Code zur iterativen Berechnung des Dreiecks. Vielleicht kann mit jemand noch einen Tipp geben, wie ich die Ausgabe so formatiere, dass es auch in beliebiger Größe wie ein Dreieck aussieht. Vielen Dank.

void pasc_dreieck(int *ptr,int x)
{
	for (int i=0;i<x;i++)
	{
		for (int j=0;j<x;j++)
		{
			int a = i*x+j;
			int b = i*x+j-1;
			int c = (i-1)*x+j;
			if (i*j==0)
				ptr[a] = 1;
			else
				ptr[a] = ptr[b]+ptr[c];
		}
	}	
}

void main(void)
{
	int n = 0;
	int *pasc_array;

	printf("Dieses Programm berechnet das Pascalsche Dreieck bis zur eingegebenen Grenze.\n"
		"Bitte geben Sie eine Grenze ein: ");
	scanf("%i",&n);

	pasc_array = (int*)malloc(n*n*sizeof(int));

	pasc_dreieck(pasc_array,n);

	// Ausgabe des Pascalschen Dreiecks
	for (int i=0;i<n;i++)
	{
		for (int l=0;l<(n-i);l++)
		{
			printf(" ");
		}
		if (i*n == 0)
			printf("%i",pasc_array[0]);
		for (int j=i*n;j>0;j--)
		{
			printf("%i ",pasc_array[j]);
			j=j-n+2;
		}
		printf("\n");
	}
}

nwp2

pascal(int zeile, spalte){
    if (zeile==1 || zeie==spalte) return 1;
    else return pascal(zeile-1, spalte-1) + pascal(zeile-1, spalte)
}
int max = 10;
for (int i = 1; i < max; i++)
    for (int j = 1; j<i; j++)
        printf("%d ", pascal(i, j));

Grausam ineffizient, aber rekursiv ist es.

Hi,

bbskater schrieb:

Vielleicht kann mit jemand noch einen Tipp geben, wie ich die Ausgabe so formatiere, dass es auch in beliebiger Größe wie ein Dreieck aussieht.

Beliebig geht nicht, die Anzahl der Spalten einer Console ist begrenzt.
Jede Zeile in einen String mit der erforderlichen Anzal Leerzeichen verpacken.

bbskater

Okay, danke, dann bin ich ja schon auf dem richtigen Weg.

bbskater

nwp2 schrieb:

pascal(int zeile, spalte){
    if (zeile==1 || zeie==spalte) return 1;
    else return pascal(zeile-1, spalte-1) + pascal(zeile-1, spalte)
}
int max = 10;
for (int i = 1; i < max; i++)
    for (int j = 1; j<i; j++)
        printf("%d ", pascal(i, j));

Grausam ineffizient, aber rekursiv ist es.

Ganz so hats nicht funktioniert, habs aber hinbekommen.

int pascal(int zeile, int spalte)
{
    if (zeile*spalte == 0 || zeile==spalte) return 1;
    else return (pascal(zeile-1, spalte-1) + pascal(zeile-1, spalte));
}

void main(void)
{
	int max;
	printf("Dieses Programm berechnet das Pascalsche Dreieck bis zur eingegebenen Grenze.\n"
		"Bitte geben Sie eine Grenze ein: ");
	scanf("%i",&max);

	for (int i = 0; i < max; i++)
	{
		for (int l=0;l<(max-i);l++)
		{
			printf(" ");
		}
		for (int j = 0; j<=i; j++)
		{	
			printf("%i ", pascal(i, j));
		}
		printf("\n");
	}
}

Jetzt gilt es nur noch irgendwie die Formatierung hinzubekommen, denn sobald eine Zahl größer wird als 9, also größer als einstellig verschiebt sich das ja alles. Na ich werd mal noch weiterprobieren. Wenn jemand nen Tipp hat, nehme ich diesen auch dankend an.

Ansonsten vielen Dank für die Hilfe.

nwp2

bbskater schrieb:

nwp2 schrieb:
pascal(int zeile, spalte){
    if (zeile==1 || zeie==spalte) return 1;
    else return pascal(zeile-1, spalte-1) + pascal(zeile-1, spalte)
}
int max = 10;
for (int i = 1; i < max; i++)
    for (int j = 1; j<i; j++)
        printf("%d ", pascal(i, j));
Grausam ineffizient, aber rekursiv ist es.
Ganz so hats nicht funktioniert, habs aber hinbekommen.

Sollte ja auch nur das Prinzip verdeutlichen, will ja nicht deine Aufgaben machen

Nen Tipp hab ich vielleicht noch:

printf("%*d", n, z);

Das bedeutet soviel wie printe die Zahl z als int und mache sie mindestens n Zeichen lang. Für n, also die Zahlenbreite nimmst du

log10(pascal(zeile, zeile/2));

pascal(zeile, zeile/2) ist die größte Zahl im Dreieck, wobei zeile die Grenze ist die du vom Nutzer einließt. log10 berechnet die Länge davon.

Wahrscheinlich ist statt log10 ein

while(zeile/10)länge++;

sinnvoller, wobei länge die länge der längsten Zahl berechnet.

Funktioniert natürlich ganz so nicht, im Prinzip aber schon. Will dir ja nicht den Spaß nehmen.

bbskater

So, es ist geschafft:

int pascal(int zeile, int spalte)
{
    if (zeile*spalte == 0 || zeile==spalte)
	{
		return 1;
	}
    else
	{
		return (pascal(zeile-1, spalte-1) + pascal(zeile-1, spalte));
	}
}

void main(void)
{
	int max;
	printf("Dieses Programm berechnet das Pascalsche Dreieck bis zur eingegebenen Grenze.\n"
		"Bitte geben Sie eine Grenze ein: ");
	scanf("%i",&max);

	for (int i = 0; i < max; i++)
	{
		for (int l=0;l<2*(max-i);l++)
		{
			printf(" ");
		}
		for (int j = 0; j<=i; j++)
		{	
			printf("%*i", 5, pascal(i, j));
		}
		printf("\n");
	}
}

Ich danke euch für die Hilfe.

Dieses Programm berechnet das Pascalsche Dreieck bis zur eingegebenen Grenze.
Bitte geben Sie eine Grenze ein: 15
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
Drücken Sie eine beliebige Taste . . .

bbskater

Ups, er zeigt die Leerzeichen nicht an, na ja, also jedenfalls siehts wie ein Dreieck aus in der konsole