Εισαγωγή
Με τον καιρό να είναι υπέροχος, δεν ανυπομονείς να περάσεις μια ώρα μέσα σε μια τάξη.
Ενοχλημένος, μπαίνεις στην τάξη, όπου παρατηρείς ένα παράξενα ικανοποιητικό τριγωνικό σχήμα στον ασπροπίνακα.
Όσο περιμένεις να φτάσει ο καθηγητής μαθηματικών, δε μπορείς παρά να παρατηρήσεις κάποια μοτίβα στο τρίγωνο: οι ακραίες τιμές είναι όλες άσσοι, κάθε επόμενη σειρά έχει μία τιμή παραπάνω από την προηγούμενη και το τρίγωνο είναι συμμετρικό.
Περίεργο!
Λίγο αφότου κάθεσαι, ο καθηγητής μπαίνει στην αίθουσα και εξηγεί ότι αυτό το τρίγωνο είναι το περίφημο τρίγωνο του Πασκάλ.
Την επόμενη ώρα, ο καθηγητής σου αποκαλύπτει μερικά καταπληκτικά πράγματα που κρύβονται σε αυτό το τρίγωνο:
- Μπορεί να χρησιμοποιηθεί για να υπολογίσεις με πόσους τρόπους μπορείς να διαλέξεις 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:
Πώς υλοποιείται αυτή η άσκηση στην Python: Αναδρομή
Αυτή η άσκηση είναι σχεδιασμένη να ολοκληρωθεί με τη χρήση recursion, αντί για βρόχους.
Μια αναδρομική συνάρτηση είναι μια συνάρτηση που καλεί τον εαυτό της, κάτι που είναι χρήσιμο όταν λύνεις προβλήματα που ορίζονται με βάση τον εαυτό τους.
Για να αποφύγεις την άπειρη αναδρομή (ή, πιο συγκεκριμένα, την υπερχείλιση της στοίβας), χρησιμοποιείται κάτι που ονομάζεται "βασική περίπτωση".
Όταν φτάσεις στη βασική περίπτωση, επιστρέφεται μια μη αναδρομική τιμή, η οποία επιτρέπει στην προηγούμενη κλήση της συνάρτησης να ολοκληρωθεί και να επιστρέψει την τιμή της, και ούτω καθεξής, με το αποτέλεσμα να διαδίδεται προς τα κάτω στη στοίβα μέχρι η πρώτη κλήση της συνάρτησης να επιστρέψει την απάντηση.
Θα μπορούσαμε να γράψουμε μια αναδρομική συνάρτηση για να βρούμε την απάντηση στο 5! (δηλαδή 5 * 4 * 3 * 2 * 1) ως εξής:
def factorial(number):
if number <= 1: # base case
return 1
return number * factorial(number - 1) # recursive case
print(factorial(5)) # returns 120
Τέλος, αξίζει να σημειωθεί ότι η Python περιορίζει τον αριθμό των αναδρομικών κλήσεων που μπορούν να γίνουν (1000 από προεπιλογή) και δεν βελτιστοποιεί την αναδρομή ουράς.
Μηνύματα εξαίρεσης
Μερικές φορές είναι απαραίτητο να πετάξεις μια εξαίρεση.
Όταν το κάνεις αυτό, θα πρέπει πάντα να συμπεριλαμβάνεις ένα κατανοητό μήνυμα σφάλματος που να δείχνει ποια είναι η πηγή του σφάλματος.
Αυτό κάνει τον κώδικά σου πιο ευανάγνωστο και βοηθάει σημαντικά στο debugging.
Σε περιπτώσεις όπου ξέρεις ότι η πηγή του σφάλματος θα είναι κάποιου συγκεκριμένου τύπου, μπορείς να επιλέξεις να πετάξεις έναν από τους ενσωματωμένους τύπους σφαλμάτων, αλλά και πάλι θα πρέπει να συμπεριλάβεις ένα κατανοητό μήνυμα.
Αυτή η συγκεκριμένη άσκηση απαιτεί να χρησιμοποιήσεις την εντολή raise για να "πετάξεις" πολλαπλά ValueErrors αν στη συνάρτηση rows() περαστεί αρνητικός αριθμός.
Τα τεστ θα περάσουν μόνο αν και κάνεις raise την exception και συμπεριλάβεις ένα μήνυμα μαζί της.
Για να πετάξεις ένα ValueError με μήνυμα, γράψε το μήνυμα ως όρισμα στον τύπο exception:
# if the rows function is passed a negative number.
raise ValueError("number of rows is negative")
