Pascalsches Dreieck im Programm ausgeben
-
Hallo,
ich versuche eine Aufgabe zu lösen, und brauche dabei eure Hilfe. Wir programmieren in C.
Die Aufgabe lautet:Schreiben Sie ein Programm, welches die Werte im Paschalschen Dreieck ausrechnet und in der angegebenen Form ausdruckt. Die Höhe des Dreiecks sollte man eingeben können.
Benutzen Sie bei der Lösung noch keine Arrays und keine Rekursion, sondern nur geschachtelte Schleifen. Wr werden später sehen, dass man mit Hilfe von Arrays diese Aufgabe leichter lösen kann.Die Binomialkoeffizienten, mit denen das Paschalsche Dreieck gefüllt werden soll, sollen mit der Formel n! / (k!*(n-k)!) berechnet werden.
Also ich habe mich erstmal um die äußere Form gekümmert, wie ich diese Dreiecksausgabe hinrkiege. Und habe erstmal zur Vereinfachung gesagt, er soll in dem Dreieck nur 5 ausgeben(und noch nciht die Binomialkoeffizienten).
Aber ich kriege noch nciht ganz das Dreieck hin.Ich habe mir auf einen Zettel ein Koordinatensystem aufgestellt, diese Form eingezeichnet(jeweils auf der x-undx-Achse immer von 0 bis z, je nachdem was eingegeben wird), und habe versucht, rauszukriegen, wann ich in dem Dreieck bin(da soll ja immer was ausgegeben werden) und wann ich außerhalb des Dreiecks bin(da sollen Leerzeichen ausgegeben werden, soll also frei sein, ist außerhalb des Dreiecks). Denn das muss ich ja wissen, um die Bedingung für die IF-Schleife festlegen zu können. Nach langem Übrlegen rechnen und probieren bin ich schließlich nur soweit gekommen: k/2)(2n)<=z
Aber so habe ich noch keinen Dreieck, wie muss ich das jetzt verändern, damit es das Dreieck ausgibt?? Also nach welcher Formel, kann ich festlegen, wann ich in dem Dreick und wann außerhalb des Dreiecks bin???
Ich hoffe ihr könnt mir da weiterhelfen...Das ist mein Code:
#include <stdio.h> #include <math.h> int main (void) { int n; int k; int z; int ze=1; printf("Geben Sie die gewünschte Höhe des Pascalschen Dreicks an:"); scanf("%i", &z); for(n=0; n<=z; n++) { for(k=0; k<=z; k++) { if((k/2)*(2*n)<=z) { printf("5"); } else { printf("*"); } printf(" "); } printf("\n"); } return 0; }
-
for(n=0; n<=z; n++) { for(k=0; k<=z-n; k++) { printf("*"); } printf("\n"); }
-
Ich glaube, du bist da auf keinem guten Pfad. Orientier dich eher an dem Pascalschen Dreieck: In der ersten Zeile hast du n=0 über k mit k von 0 bis n=0. In der zweiten Zeile hast du n=1 über k mit k von 0 bis n=1. In der dritten Zeile hast du n=2 über k von 0 bis n=2.
Das kannst du einfach als zwei verschachtelte Schleifen schreiben.
Dann verbleibt nur noch die Frage, wieviele Leerstellen du jeweils am Anfang einer Zeile einzeichnen musst. In der letzten Zeile hast du n Werte und musst keine Leerstelle einfügen. In der vorletzten Zeile hast du n-1 Werte und musst daher 1/2 Leerstellen einfügen. In der vorvorletzten Zeile hast du n-2 Werte und musst daher 2/2 Leerstellen einfügen. In der ersten Zeile hast du n-(n-1) Werte und musst daher (n-1)/2 Leerstellen einfügen.
Die Größe einer Leerstelle ist dabei die Größe einer Zahl plus der Abstand bis zur nächsten Zahl.
-
DirkB schrieb:
for(n=0; n<=z; n++) { for(k=0; k<=z-n; k++) { printf("*"); } printf("\n"); }Das wird bei mir auch kein Dreieck
-
SeppJ schrieb:
Orientier dich eher an dem Pascalschen Dreieck: In der ersten Zeile hast du n=0 über k mit k von 0 bis n=0. In der zweiten Zeile hast du n=1 über k mit k von 0 bis n=1. In der dritten Zeile hast du n=2 über k von 0 bis n=2.
Das kannst du einfach als zwei verschachtelte Schleifen schreiben.
.ich probiere jetzt seit einer halben Stunde, aber schaffe es mit den 2 verschachtelten Schleifen einfach nicht
Sind meine 2 Schleifen nicht richtig? n und k laufen doch jeweils bis z, k bis 2*z oder nicht?
Was in dem ersten Absatz steht, habe ich verstanden, aber es nur mit 2 Schleifen ausgeben kann ich damit nicht
-
xx_20 schrieb:
Das wird bei mir auch kein Dreieck
Bei mir schon:http://codepad.org/ZNaR44Eu
Ich hatte das Dreieck von Blaise Pascal in Erinnerung: http://de.wikipedia.org/wiki/Pascalsches_Dreieck#Anwendung
-
Achso, ja, aber es soll bei uns mit der Spitze nach oben zeigen, das ist in der Aufgabenstellung auch so abgebildet, und so soll leider auch genau so ausgegeben werden. Alsi die Spitze nach oben und in der Mitte. Trotzdem vielen Dank!!
-
xx_20 schrieb:
Sind meine 2 Schleifen nicht richtig? n und k laufen doch jeweils bis z, k bis 2*z oder nicht?
Nein. Denk noch einmal nach, welche Werte k für gegebenes n haben kann. Dann verstehst du auch den zweiten Absatz mit der Erklärung, wie du das Dreieck grafisch schön hinbekommst.
-
Ich komme einfach nicht drauf :S
Probiere alles mögliche aber es funktioniert nicht. Mein "Dreieck" sieht jedesmal nur noch schlimmer aus, wie logisch mir meine Schleifen auch zu sein scheinen
-
xx_20 schrieb:
Ich komme einfach nicht drauf :S
Probiere alles mögliche aber es funktioniert nicht. Mein "Dreieck" sieht jedesmal nur noch schlimmer aus, wie logisch mir meine Schleifen auch zu sein scheinenOch, mit so viel Hilfe immer noch nichts
.Na, bevor du Pipi in die Augen bekommst:
#include <stdio.h> #include <stdlib.h> unsigned long long fak(unsigned n) { unsigned long long result = 1; unsigned i = 1; for (; i <=n; ++i) result *= i; return result; } unsigned binomial(unsigned n, unsigned k) { return fak(n)/(fak(k)*fak(n-k)); } int main () { unsigned max_n; puts("Maximales n (0-20)? "); if (scanf("%ud", &max_n) == 1) { unsigned zeichenbreite=7; // "Empirisch" bestimmte Werte if (max_n > 20) // Zahlen werden zu groß exit(1); else if (max_n > 19) zeichenbreite = 7; else if (max_n > 16) zeichenbreite = 6; else if (max_n > 13) zeichenbreite = 5; else if (max_n > 9) zeichenbreite = 4; else if (max_n > 5) zeichenbreite = 3; else zeichenbreite = 2; char formatstring[6]; sprintf(formatstring, "%%%uu ", zeichenbreite - 1); unsigned n, k; for(n = 0; n <= max_n; ++n) { // Whitespace vorne int num_whitespace = ((max_n)/2. - n/2.)*zeichenbreite; int i; for(i = 0; i < num_whitespace; ++i) putchar(' '); // Eigentliche Werte for(k = 0; k <= n; ++k) { printf(formatstring, binomial(n,k)); } putchar('\n'); } } return 0; }Sieht nun wirklich sehr schön aus:
Maximales n (0-20)? 20 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 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1 1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1 1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1Es ist zwar alles recht grundlegend, es könnte jedoch sein, dass dir niemand glaubt, dass du das alleine hinbekommen hast, weil eben sehr viele Grundlagen clever kombiniert werden, während du noch nicht einmal Schleifen mit Hilfe richtig hinbekommst.
edit: Da war noch ein Fehler für n=20. Ausgebessert.
-
Vielen Dank!
Das würde ich mir auch nicht glauben.
Aber ich habe erst seit einem Monat programmierung und finde diese Aufgabe schon viel zu krass für unseren "Wissensstand".Zum Beispiel steht bei dir sprintf, das sehe ich zum ersten mal. Kenne nur printf und scanf. Und dass du oben scanf gleich mit in der if-Bedingung hast, kann ich auch nicht verstehen, sowas sehe ich auch das erste mal und ich habe versucht das so auseinanderzunehmen:
scanf("%ud", &max_n);
if(max_n == 1)aber das wird dann falsch......ich komme irgendwie überhaupt nicht klar mit diesem Programm, verstehe zum Beispiel auch überhaupt nicht was die Zahlen für die "Zeichenbreite" sein sollen.
Und das Schlimme ist, das ich mit diesem "Zwischenergebnis" bei meinem Tutor war, bevor ich es hier reingepostet habe, und er mir gesagt hat, dass die Schleifen so richtig sind, und ich mir da als BEdingung nur noch was anderes überlegen muss, damit ich das Dreieck hinbekomme. Und für den Fall, dass ich das richtig hinbekomme hatte ich schon den Inhalt des Dreieck "programmiert", wo er auch meinte es sei richtig und wenn ich diese BEdingung richtig bestimme wäre mein Programm fertig
deshalb war ich echt verzweifelt und wusste nicht an wen ich mich wenden soll, zu ihm sollte ich glaube ich nicht mehr gehen.
Vielleicht sollte ich Nachhilfe nehmen
-
Du kannst den Kladderadatsch mit der Zeichenbreite auch weglassen:
#include <stdio.h> #include <stdlib.h> unsigned long long fak(unsigned n) { unsigned long long result = 1; unsigned i = 1; for (; i <=n; ++i) result *= i; return result; } unsigned binomial(unsigned n, unsigned k) { return fak(n)/(fak(k)*fak(n-k)); } int main () { unsigned max_n; puts("Maximales n (0-20)? "); if (scanf("%ud", &max_n) == 1) { if (max_n > 20) // Zahlen werden zu groß exit(1); const int zeichenbreite = 7; // Maximale Breite einer Zahl bei n=20 unsigned n, k; for(n = 0; n <= max_n; ++n) { // Whitespace vorne int num_whitespace = ((max_n)/2. - n/2.)*zeichenbreite; int i; for(i = 0; i < num_whitespace; ++i) putchar(' '); // Eigentliche Werte for(k = 0; k <= n; ++k) { printf("%7u ", binomial(n,k)); } putchar('\n'); } } return 0; }Dann sieht es bei 4 eben nicht mehr so:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1sondern so aus:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1Nun verständlicher?
Im Programm oben waren übrigens noch ein paar Schönheitsfehler drin, an den Grenzen hätte es >= statt >= heißen müssen:
if (max_n > 20) // Zahlen werden zu groß exit(1); else if (max_n == 20) zeichenbreite = 7; else if (max_n >= 16) zeichenbreite = 6; else if (max_n >= 13) zeichenbreite = 5; else if (max_n >= 9) zeichenbreite = 4; else if (max_n >= 5) zeichenbreite = 3; else zeichenbreite = 2;
-
Hmmm mit überlegen verstehe ich einiges vielleicht doch. ZUm Beispiel kannte ich auch result = i noch nicht bin jetzt aber drauf gekommen, das das result= resulti heißen muss.
Und Zeichenbreite ich glaube ich die Anzahl der Spalten, die freigehalten werdens ollen für die Zahlen im DReieck, da die Zahlen größer werden, je größer max_n ist, muss die Zeichenbreite größer werden damit es noch ein Dreieck bleibt...oder?
Ich verstehe dann aber diese Zeile überhaupt nichtchar formatstring[6];
sprintf(formatstring, "%%%uu ", zeichenbreite - 1);Ich glaube jetzt verstehe ich fast alles bis auf diese 2 Zeilen....und die Zeile wo im printf befehl nochmal formatstring vorne steht, aber das müsste auch an disen zwei zeilen liegen, was heißt denn hier formatstring[6]
wäre echt seeeeehr nett wenn du mir diese zwei zeilen noch erklären könntest.
Und nochmal tauuuusend DaNK!
-
scanf() gibt die Anzahl der gelesenen Werte zurück.
Man kann mit scanf auch mehrere verschiedene Daten einlesen.Nachzulesen z.B hier: http://www.cplusplus.com/reference/clibrary/cstdio/scanf/
Die Seite kannst du dir gleich merken, da dort auch die anderen Funktionen der C-Standardlibrary erklärt werden.
Das ist eigentlich für C++, die Besonderheiten bei C werden aber erklärt.
-
Ach du hattest in zwischen schon geantwortet,
DANKESEHR!!!
-
xx_20 schrieb:
. Und dass du oben scanf gleich mit in der if-Bedingung hast, kann ich auch nicht verstehen, sowas sehe ich auch das erste mal und ich habe versucht das so auseinanderzunehmen:
scanf("%ud", &max_n);
if(max_n == 1)Das hast du auch völlig falsch interpretiert. Guck dir scanf an:
http://www.cplusplus.com/reference/clibrary/cstdio/scanf/Return Value
On success, the function returns the number of items successfully read. This count can match the expected number of readings or fewer, even zero, if a matching failure happens.
In the case of an input failure before any data could be successfully read, EOF is returned.Es wird also geprüft, ob der eingegebene Wert überhaupt eine Zahl war. Nix mit dem Wert von max_n. Warum sollte ich den Wert von max_n überhaupt auf Gleichheit mit 1 prüfen?
ich komme irgendwie überhaupt nicht klar mit diesem Programm, verstehe zum Beispiel auch überhaupt nicht was die Zahlen für die "Zeichenbreite" sein sollen.
Bei größeren max_n werden die Zahlen unten im Dreieck immer länger. Damit das Dreieck noch Dreieckig bleibt, muss man entsprechend mehr Füllzeichen einfügen. Die Grenzen 5,9,13,16,19 habe ich durch ausprobieren bestimmt. Vergleiche die Ausgaben meiner vereinfachten Version und der Version mit der variablen Zeichenbreite. Sieht doch viel besser aus mit variabler Zeichenbreite.
Und das Schlimme ist, das ich mit diesem "Zwischenergebnis" bei meinem Tutor war, bevor ich es hier reingepostet habe, und er mir gesagt hat, dass die Schleifen so richtig sind, und ich mir da als BEdingung nur noch was anderes überlegen muss, damit ich das Dreieck hinbekomme. Und für den Fall, dass ich das richtig hinbekomme hatte ich schon den Inhalt des Dreieck "programmiert", wo er auch meinte es sei richtig und wenn ich diese BEdingung richtig bestimme wäre mein Programm fertig
Nun, kommt erst einmal drauf an, ob dein Tutor überhaupt Ahnung hat. Wie genau hast du deine Schleifen denn gemacht? Es sollte auf jeden Fall der "Trick" auftauchen, k von 0 bis n laufen zu lassen. Sonst hast du keine Chance, auf das Dreieck zu kommen. Oder du bekommst ein Dreieck dieser Form:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1Das geht auch mit vereinfachter Bedingung:
#include <stdio.h> #include <stdlib.h> unsigned long long fak(unsigned n) { unsigned long long result = 1; unsigned i = 1; for (; i <=n; ++i) result *= i; return result; } unsigned binomial(unsigned n, unsigned k) { if (k>n) return 0; // ACHTUNG: Hier auch geändert! return fak(n)/(fak(k)*fak(n-k)); } int main () { unsigned max_n; puts("Maximales n (0-20)? "); if (scanf("%ud", &max_n) == 1) { if (max_n > 20) // Zahlen werden zu groß exit(1); unsigned n, k; for(n = 0; n <= max_n; ++n) { for(k = 0; k <= max_n; ++k) // Dann muss man hier nicht denken { unsigned wert = binomial(n,k); if (wert > 0) printf("%7u ", wert); } putchar('\n'); } } return 0; }Wenn es ein schönes Dreieck werden soll, dann findest du die Erklärung in meinem Beitrag ganz oben und die konkrete Umsetzung als Code dieser Bedingungen hast du auch gezeigt bekommen.
-
sprintf(formatstring, "%%%uu ", zeichenbreite - 1);Da steht erstmal %% . Das schreibt ein % in den Formatstring.
Das %u danach schreibt den entsprechenden Paramter als vorzeichenlose Dezimalzahl in den Formatstring. Ist zeichenbreit z.B. 4 dann wird in formatstring eine 3 geschrieben.
Das u und das Leerzeichen werden übernommen.
Also steht in Formatstring ein "%3u ".
Damit wird dann das printf "gefüttert".Für solche Fälle gibt es aber den * im Formatstring.
printf("%*u ", zeichenbreite - 1, binomial(n,k));
-
xx_20 schrieb:
Ich verstehe dann aber diese Zeile überhaupt nicht
char formatstring[6];
sprintf(formatstring, "%%%uu ", zeichenbreite - 1);Ich glaube jetzt verstehe ich fast alles bis auf diese 2 Zeilen....und die Zeile wo im printf befehl nochmal formatstring vorne steht,
Dann schauen wir nochmal in das vereinfachte Beispiel:
printf("%7u ", binomial(n,k));Da gibt die 7 (wie du in einer printf-Referenz nachlesen kannst) die Zahl der Zeichen an, auf die die Ausgabe aufgefüllt werden soll. Das mache ich, wie du richtig erkannt hast, weil die Zahlen unten breiter werden, die Ausgabe der Zahlen oben aber genau so breit sein muss wie unten, damit das Dreieck schön wird.
So, nun ist diese breite aber eine Variable. ich will also bei max_n = 20 da
"%7u " stehen haben und bei max_n=4 will ich "%2u " als Formatstring. Ich kann aber natürlich nichtprintf("%"zeichenbreite"u ", binomial(n,k));schreiben. Das ist Unsinn, so funktioniert das nicht. Also muss ich mir einen Formatstring basteln. Der Formatstring von printf muss nicht etwas sein, dass man beim Programmieren fest einbaut, das kann irgendeine Zeichenkette (d.h. in C ein Array von chars) sein, zum Beispiel mein char formatstring[6]. Den muss ich nun noch mit dem passenden Inhalt füllen. sprintf ist wie printf, aber anstatt auf die Standardausgabe schreibt es in eine Zeichenkette, hier den Formatstring. Ansonsten ist alles genau gleich wie bei printf. Nun will ich also die oben genannten Zeichenketten in den Formatstring schreiben. Doch Ohweh! Wie gibt man mit printf ein Prozentzeichen aus? Wieder in die Referenz geguckt: Ach, mit %%. Somit können wir den Befehl auseinandernehmen:
sprintf(formatstring, "%%%uu ", zeichenbreite - 1);Da steht:
Schreibe an die Stelle von formatstring folgedes: Ein Prozenzeichen, dann eine vorzeichenlose Zahl, dann ein Leerzeichen. Und dann noch die Angabe, dass die vorzeichenlose Zahl den Wert zeichenbreite-1 haben soll. Und somit hat formatstring hinterher den Inhalt den ich möchte und ich kann dies als Formatstring für das printf benutzen.
-
DirkB schrieb:
Für solche Fälle gibt es aber den * im Formatstring.
printf("%*u ", zeichenbreite - 1, binomial(n,k));:p Ich sollte mir meinen Rat zu Herzen nehmen und selber öfters in die Referenz gucken. Das ist so natürlich viel einfacher. Hatte mich schon gewundert, dass dies so kompliziert sein sollte in C.
-
Im K&R gabs das auch noch nicht
@xx_20
K&R bezeichnet das Ur-C, das in dem Buch "The C Programming Language" (deutsch: Programmieren in C) von Kernighan und Ritchie beschrieben wird.
