Εισαγωγή
Με τον καιρό να είναι υπέροχος, δεν ανυπομονείς να περάσεις μια ώρα σε μια αίθουσα.
Νιώθοντας εκνευρισμό, μπαίνεις στην αίθουσα, όπου παρατηρείς ένα παράξενα ικανοποιητικό τριγωνικό σχήμα στον μαυροπίνακα.
Καθώς περιμένεις να φτάσει ο καθηγητής μαθηματικών σου, δεν μπορείς παρά να παρατηρήσεις μερικά μοτίβα στο τρίγωνο: οι εξωτερικές τιμές είναι όλες άσσοι, κάθε επόμενη σειρά έχει μία τιμή περισσότερη από την προηγούμενη και το τρίγωνο είναι συμμετρικό.
Περίεργο!
Λίγο αφού κάτσεις, ο καθηγητής σου μπαίνει στην αίθουσα και εξηγεί ότι αυτό το τρίγωνο είναι το διάσημο τρίγωνο του Πασκάλ.
Την επόμενη ώρα, ο καθηγητής σου αποκαλύπτει μερικά καταπληκτικά πράγματα κρυμμένα σε αυτό το τρίγωνο:
- Μπορεί να χρησιμοποιηθεί για να υπολογίσεις με πόσους τρόπους μπορείς να διαλέξεις K στοιχεία από N τιμές.
- Περιέχει την ακολουθία Φιμπονάτσι.
- Αν χρωματίσεις διαφορετικά τους μονούς και τους ζυγούς αριθμούς, παίρνεις ένα όμορφο μοτίβο που ονομάζεται τρίγωνο του Σιερπίνσκι.
Ο καθηγητής σου σε προτρέπει να ψάξεις μαζί με τους συμμαθητές σου για άλλες χρήσεις και σε διαβεβαιώνει ότι υπάρχουν κι άλλες πολλές!
Εκείνη τη στιγμή, χτυπάει το κουδούνι του σχολείου.
Συνειδητοποιείς ότι την τελευταία ώρα είχες απορροφηθεί εντελώς μαθαίνοντας για το τρίγωνο του Πασκάλ.
Αρπάζεις γρήγορα το λάπτοπ από την τσάντα σου και βγαίνεις έξω, για να απολαύσεις και τη λιακάδα και τα θαύματα του τριγώνου του Πασκάλ.
Οδηγίες
Η αποστολή σου είναι να παράγεις τις πρώτες N γραμμές του τριγώνου του Πασκάλ.
Το τρίγωνο του Πασκάλ είναι ένας τριγωνικός πίνακας θετικών ακεραίων.
Στο τρίγωνο του Πασκάλ, το πλήθος των τιμών σε μια γραμμή είναι ίσο με τον αριθμό της γραμμής (ο οποίος ξεκινά από το ένα).
Επομένως, η πρώτη γραμμή έχει μία τιμή, η δεύτερη γραμμή έχει δύο τιμές, και ούτω καθεξής.
Η πρώτη (πάνω) γραμμή έχει μία μόνο τιμή: 1.
Οι τιμές των επόμενων γραμμών υπολογίζονται προσθέτοντας τους αριθμούς ακριβώς στα δεξιά και στα αριστερά της τρέχουσας θέσης στην προηγούμενη γραμμή.
Αν η προηγούμενη γραμμή δεν έχει τιμή στα αριστερά ή στα δεξιά της τρέχουσας θέσης (κάτι που συμβαίνει μόνο στις πιο αριστερές και τις πιο δεξιές θέσεις), θεώρησε την τιμή αυτής της θέσης ως μηδέν (ουσιαστικά την "αγνοείς" στο άθροισμα).
Παράδειγμα
Ας δούμε τις πρώτες 5 γραμμές του τριγώνου του Πασκάλ:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Η πάνω γραμμή έχει μία τιμή, η οποία είναι 1.
Οι πιο αριστερές και οι πιο δεξιές τιμές έχουν μόνο μία προηγούμενη θέση να λάβουν υπόψη, δηλαδή τη θέση στα δεξιά τους ή στα αριστερά τους, αντίστοιχα.
Με την πάνω τιμή να είναι 1, έπεται ότι όλες οι πιο αριστερές και οι πιο δεξιές τιμές είναι επίσης 1.
Οι υπόλοιπες τιμές έχουν δύο θέσεις να λάβουν υπόψη.
Για παράδειγμα, η μεσαία τιμή της πέμπτης γραμμής (1 4 6 4 1) είναι 6, καθώς οι τιμές στα αριστερά και στα δεξιά της στην προηγούμενη γραμμή είναι 3 και 3:
