Εισαγωγή
Με τον καιρό να είναι υπέροχος, δεν ανυπομονείς να περάσεις μια ώρα μέσα σε μια τάξη.
Ενοχλημένος, μπαίνεις στην τάξη, όπου παρατηρείς ένα παράξενα ικανοποιητικό τριγωνικό σχήμα στον ασπροπίνακα.
Όσο περιμένεις να φτάσει ο καθηγητής μαθηματικών, δε μπορείς παρά να παρατηρήσεις κάποια μοτίβα στο τρίγωνο: οι ακραίες τιμές είναι όλες άσσοι, κάθε επόμενη σειρά έχει μία τιμή παραπάνω από την προηγούμενη και το τρίγωνο είναι συμμετρικό.
Περίεργο!
Λίγο αφότου κάθεσαι, ο καθηγητής μπαίνει στην αίθουσα και εξηγεί ότι αυτό το τρίγωνο είναι το περίφημο τρίγωνο του Πασκάλ.
Την επόμενη ώρα, ο καθηγητής σου αποκαλύπτει μερικά καταπληκτικά πράγματα που κρύβονται σε αυτό το τρίγωνο:
- Μπορεί να χρησιμοποιηθεί για να υπολογίσεις με πόσους τρόπους μπορείς να διαλέξεις 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:
