Σήμερα λύσαμε ακόμη μερικά προβλήματα, αναφερθήκαμε σε αναδρομικές συναρτήσεις και αρχίσαμε να συζητάμε για το πώς διαβάζουμε και γράφουμε αρχεία.
Κάποιοι φυσικοί αριθμοί \(n\) μπορούν να γραφούν ως άθροισμα δύο τετραγώνων. Π.χ. \(5=1^2+2^2\) ενώ κάποιοι άλλοι δε γίνεται να γραφούν έτσι, π.χ. ο αριθμός 7. Στο παρακάτω κελλί έχουμε γράψει μια συνάρτηση sumofsqaures που δοθέντος ενός φυσικού αριθμού \(n\) βρίσκει αν γράφεται ως άθροισμα δύο τετραγώνων \(n = x^2+y^2\) και μας επιστρέφει τα \(x, y\) (μπορεί να υπάρχουν πολλοί τρόποι να γραφεί το \(n\) ως τέτοιο άθροισμα, αλλά δεν τους βρίσκουμε όλους). Αν ο αριθμός δε γράφεται ως άθροισμα δύο τετραγώνων τότε η συνάρτησή μας επιστρέφει 0,0.
Κάνουμε κατ'αρχήν την παραδοχή ότι αν \(n=x^2+y^2\) τότε θα ονομάζουμε πάντα \(x\) το μικρότερο από τα δύο κι έτσι θα ισχύει πάντα \(0 \le x \le y \le \sqrt{n}\). Έτσι αφήνουμε το \(y\) να πάρει όλες τις τιμές από 0 έως και τον επόμενο ακέραιο του \(\sqrt{n}\) και για κάθε τιμή του \(y\) αφήνουμε το \(x\) να πάρει όλες τις τιμές από 0 έως και \(y\).
Η μεταβλητή sn υπολογίζεται παίρνοντας την τετραγωνική ρίζα του \(n\), στρογγυλεύοντάς την προς τα πάνω με την math.ceil και μετατρέποντας το αποτέλεσμα (που είναι ακέραιος αλλά αποθηκευμένος στο σύστημα με μορφή float, γιατί αυτό επιστρέφει η math.ceil) σε ακέραιο με τη συνάρτηση int.
Στην εσωτερική ανακύκλωση ελέγχουμε αν \(n=x^2+y^2\) για τα συγκεκριμένα \(x, y\) που έχουμε εκείνη τη στιγμή και αν ισχύει αυτό τότε επιστρέφουμε τα \(x, y\). Αν δεν πιάσει κανένα return μέσα στην ανακύκλωση αυτό σημαίνει ότι δε βρήκαμε καμία αναπαράσταση και άρα επιστρέφουμε 0,0 μόλις τελειώσει η ανακύκλωση.
Στο κυρίως πρόγραμμα ελέγχουμε όλους τους αριθμούς έως το 30 για το αν είναι άθροισμα δύο τετραγώνων και, αν είναι, τους τυπώνουμε μαζί με την αναπαράστασή τους που μας επέστρεψε η sumofsquares.
Στην εντολή print που είναι στην προτελευταία γραμμή (σε σχόλια) τυπώναμε αυτούς τους αριθμούς και την αναπαράστασή τους αλλά η print, αν χρησιμοποιηθεί όπως σε αυτή την εντολή, βάζει κενά ανάμεσα στα ορίσματά της που τυπώνει και έτσι το αποτέλεσμά της δεν ήταν ικανοποιητικό από αισθητική άποψη.
Γι'αυτό δείχνουμε ένα νέο τρόπο χρήσης της print με τη χρήση του format string που γράφεται στο τέλος. Μέσα στο string "{number_n}={number_x}**2+{number_y}**2" υπάρχουν κάποιες θέσεις με ονόματα σε άγκιστρα, οι {number_n}, {number_x} και {number_y}, οι οποίες δεν τυπώνονται αυτούσιες όπως στο υπόλοιπο string αλλά η τιμή που θα τυπωθεί στη θέση τους δίδεται με τη συνάρτηση format. Μέσα σε αυτή τη συνάρτηση προσδιορίζουμε ποια τιμή θα μπει στη θέση του {number_n} και των άλλων παρόμοιων.
import math
def sumofsquares(n):
"Επιστρέφει x, y τέτοια ώστε x**2 + y**2 = n. Αν δεν υπάρχουν επιστρέφει 0, 0"
sn = int(math.ceil(math.sqrt(n)))
for y in range(sn+1):
for x in range(1+y):
if x**2+y**2 == n:
return x, y
return 0,0
for n in range(30):
x, y = sumofsquares(n)
if x!=0 or y!= 0:
#print n, "=", x, "**2+", y, "**2"
print "{number_n}={number_x}**2+{number_y}**2".format(number_n=n, number_x=x, number_y=y)
Τώρα λύνουμε ένα παρόμοιο πρόβλημα, αλλά και κάπως διαφορετικό. Και πάλι αυτό που μας ενδιαφέρει είναι να αποφασίσουμε πότε ένας αριθμός είναι άθροισμα δύο τετραγώνων, μόνο που τώρα δε μας ενδιαφέρει να το λύσουμε το πρόβλημα για ένα μόνο αριθμό αλλά για όλους τους ακεραίους στο διάστημα \(1,\ldots,N\). Δε γράφουμε λοιπόν τώρα μια συνάρτηση που να λύνει το πρόβλημα για έναν φυσικό \(n\) αλλά γράφουμε ένα πρόγραμμα που βρίσκει απευθείας όλους τους αριθμούς στο ζητούμενο διάστημα που είναι αθροίσματα δύο τετραγώνων.
Για να το πετύχουμε αυτό ξεκινάμε με μια λίστα \(L\) που έχει κατ' αρχήν μόνο μηδενικά μέσα και εκτείνεται από το 0 έως και το Ν. Η λίστα αυτή δημιουργείται από την εντολή L = [0]*(N+1) ("πάρε τη λίστα [0] και πολλαπλασίασέ τη με το \(N+1\), κόλλα τη δηλ. με τον εαυτό της \(N+1\) φορές. Δημιουργείται έτσι μια λίστα μήκους \(N+1\) που περιέχει όλο μηδενικά.
Η στρατηγική μας τώρα είναι: παράγουμε με κάποιο τρόπο όλα τα πιθανά ζεύγη \(x, y\) και για κάθε τέτοιο ζεύγος πάμε στη θέση \(n=x^2+y^2\) και "μαρκάρουμε" (βάζουμε την τιμή 1) τη θέση αυτή στη λίστα L ως μια θέση που περιέχει άθροισμα δύο τετραγώνων. Στο τέλος του προγράμματος απλά διανύουμε αυτή τη λίστα και απλά αναφέρουμε εκείνους τους αριθμούς \(n\) για τους οποίους L[n] ισούται με 1.
Τα δυνατά \(x, y\) τα βρίσκουμε όπως και στο προηγούμενο: υποθέτουμε και πάλι \(0 \le x \le y \le \sqrt{N}\), διανύουμε όλες τις δυνατές τιμές του \(y\) με την εξωτερική ανακύκλωση for και για κάθε μια τιμή του \(y\) διανύουμε για το \(x\) όλες τις τιμές \(0, 1, \ldots, y\).
import math
N=100
L = [0]*(N+1)
for y in range(1+int(math.ceil(math.sqrt(N)))):
for x in range(y+1):
s = x**2+y**2
if s<=N:
L[s] = 1
for i in range(N+1):
if L[i] == 1:
print i,
Η ακολουθία Fibonacci, \(F_n\), για \(n \ge 0\), ορίζεται με τις αρχικές τιμές \(F_0 = F_1 = 1\) και για \(n\ge 2\) με την αναδρομική σχέση \(F_n = F_{n-1}+F_{n-2}\), κάθε όρος της ακολουθίας δηλ. είναι το άθροισμα των δύο προηγουμένων του, με την εξαίρεση φυσικά των δύο πρώτων όρων της ακολουθίας \(F_0, F_1\) οι οποίοι δεν έχουν δύο προηγούμενους όρους και άρα εκεί η ακολουθία πρέπει να οριστεί χωριστά.
Στο παρακάτω κελλί υπολογίζουμε όλους τους όρους της ακολουθίας Fibonacci μέχρι και τον \(N\)-οστό όρο. Φτιάχνουμε και πάλι μια λίστα L με το κατάλληλο μήκος (\(N+1\)), ορίζουμε τις δύο πρώτες τιμές να είναι 1 και μετά από το 2 έως και το N υπολογίζουμε τον κάθε όρο από το άθροισμα των δύο προηγουμένων του, οι οποίοι φυσικά έχουν ήδη υπολογιστεί προηγουμένως.
N=20
L = [0]*(N+1)
L[0] = 1
L[1] = 1
for i in range(2,N+1):
L[i] = L[i-1]+L[i-2]
print L
Στο επόμενο γράφουμε μια συνάρτηση fib(n) η οποία υπολογίζει το \(F_n\), ουσιαστικά κάνοντας ότι και το προηγούμενο πρόγραμμα αλλά επιστρέφοντας μόνο την τελευταία τιμή από τον πίνακα, που είναι και αυτή που μας ενδιαφέρει να επιστρέψουμε.
def fib(n):
if n==0 or n==1:
return 1
L=[0]*(n+1)
L[0] = 1; L[1] = 1
for i in range(2, n+1):
L[i] = L[i-1] + L[i-2]
return L[n]
print fib(20)
Στο επόμενο ξαναγράφουμε τη συνάρτηση fib(n) με ένα διαφορετικό τρόπο. Πρώτα ελέγχουμε αν \(n=0\) ή \(n=1\) και σε αυτή την περίπτωση επιστρέφουμε 1, όπως οφείλουμε. Αν αυτό δεν ισχύει (έχουμε \(n\ge 2\)) τότε ανατρέχουμε στον ορισμό μας και ξανακαλούμε την ίδια τη συνάρτησή μας αλλά με μικρότερες τιμές ως όρισμα \(n-1\) και \(n-2\).
Μια τέτοια συνάρτηση που καλεί τον εαυτό της ονομάζεται αναδρομική.
Είναι πολύ σημαντικό όταν γράφει κανείς μια αναδρομική συνάρτηση να έχει μια συνθήκη η οποία σταματάει την αναδρομή (τις κλήσεις δηλ. προς τον εαυτό της) κάποια στιγμή, αλλιώς η συνάρτηση θα καλεί συνεχώς τον εαυτό της και δεν πρόκειται να τελειώσει ποτέ.
Παρακολουθείστε για παράδειγμα εδώ με τον online python tutor το πώς η fib(5) καλεί συνεχώς τον εαυτό της αλλά μέχρι ενός σημείου που καθορίζεται από το πότε το \(n\) γίνεται 0 ή 1.
def fib(n):
if n==0 or n==1:
return 1
return fib(n-1)+fib(n-2)
print fib(20)
Αν κάποιος δεν προσέξει το πότε θα ισχύσει αυτή η συνθήκη που κόβει την αναδρομή τότε εύκολα μπορεί να καταλήξει με ένα πρόγραμμα που καλεί τον εαυτό του επ' άπειρον, δεν τελειώνει δηλ. ποτέ.
Αν για παράδειγμα κάνουμε τον έλεγχο αν \(n=0\) ή \(n=1\) μετά την κλήση στην fib, όπως φαίνεται στο παρακάτω πρόγραμμα, τότε καταλήγουμε ακριβώς σε μια τέτοια κατάσταση. Το πρόγραμμα δεν τελειώνει ποτέ και κάποια στιγμή το σταματά ο υπολογιστής βίαια.
def fib(n):
return fib(n-1)+fib(n-2)
if n==0 or n==1:
return 1
print fib(20)
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
<ipython-input-24-e359c5c1d1a2> in <module>()
4 return 1
5
----> 6 print fib(20)
<ipython-input-24-e359c5c1d1a2> in fib(n)
1 def fib(n):
----> 2 return fib(n-1)+fib(n-2)
3 if n==0 or n==1:
4 return 1
5
...Στο επόμενο βλέπουμε άλλο ένα παράδειγμα αναδρομικής συνάρτησης. Η συνάρτηση fact(n) υπολογίζει το παραγοντικό του \(n\), \(n! = 1\cdot2\cdot3\cdots(n-1)\cdot n\), χρησιμοποιώντας την απλή ιδιότητα \[
0! = 1
\] και \[
n! = n\cdot (n-1)!
\] για \(n \ge 1\).
def fact(n):
if n==0:
return 1
return n*fact(n-1)
print fact(5)
Στο επόμενο βλέπουμε ένα εναλλακτικό τρόπο υπολογισμού του παραγοντικού που δε χρησιμοποιεί αναδρομή.
Οι μη αναδρομικές συναρτήσεις υπερτερούν συνηθως σε αποτελεσματικότητα (ταχύτητα, χρήση μνήμης) αλλά οι αναδρομικές συναρτήσεις υπερτερούν σε εκφραστικότητα και απλότητα και είναι σε κάποιες περιπτώσεις ο μόνος καθαρός τρόπος να λυθεί ένα πρόβλημα.
def fact(n):
p=1
for i in range(2,n+1):
p *= i
return p
print fact(5)
print fact(0)
Αρχίσαμε να μιλάμε σήμερα για το πώς επεξεργαζόμαστε αρχεία του υπολογιστή μας. Το να μπορούμε να επεξεργαζόμαστε πληροφορία που είναι αποθηκευμένη σε ένα αρχείο είναι απολύτως κρίσιμο για να μπορούμε να είμαστε παραγωγικοί σχεδόν σε ό,τι και να κάνουμε. Από το να επεξεργαζόμαστε δεδομένα από μετρήσεις και να εξάγουμε ποσοτικά συμπεράσματα μέχρι το να επεξεργαζόμαστε βαθμολογίες φοιτητών ή μαθητών και άλλα δεδομένα, οποτεδήποτε η πληροφορία είναι κάπως μεγάλη δε μπορεί ο χρήστης να την δίνει με το χέρι κάθε φορά που τρέχει το όποιο πρόγραμμά μας που την επεξεργάζεται (πράγμα που άλλωστε συνήθως οδηγεί και στο να γίνονται πολλά λάθη) αλλά η πληροφορία παρέχεται στο πρόγραμμά μας αποθηκευμένη σε ένα ή περισσότερα αρχεία του υπολογιστή μας.
Ας υποθέσουμε ότι στον υπολογιστή μας είναι αποθηκευμένο ένα αρχείο με όνομα myfile.txt και περιεχόμενα
First line of text.
Third line of text. The second line is blank.
This is the last line of this file.Αν θέλετε να δοκιμάσετε το πρόγραμμα που φαίνεται παρακάτω τότε μπορείτε να κατεβάσετε αυτό το αρχείο από εδώ. Αποθηκεύστε το στον υπολογιστή σας στην ίδια θέση (ίδιο directory) όπου θα αποθηκεύσετε το παρακάτω πρόγραμμα, το οποίο ας πούμε ότι το ονομάζουμε ftest.py. Μπορείτε να τρέξετε το πρόγραμμά σας με την εντολή
python ftest.pyαπό τη γραμμή εντολών ευρισκόμενοι στον κατάλογο αυτό.
Το πρόγραμμα αυτό κάνει κάτι το πολύ απλό. Ανοίγει κατ' αρχήν το αρχείο myfile.txt (το οποίο, παρεπιπτόντως, θα μπορούσε να έχει οποιοδήποτε όνομα) για ανάγνωση. Αυτό γίνεται με τη συνάρτηση open("myfile.txt", "r") η οποία επιστρέφει ένα αντικείμενο τύπου file object το οποίο το φανταζόμαστε ως αποθηκευμένη πληροφορία για το πού είναι το αρχείο μας στο δίσκο, πόσο μέρος αυτού έχουμε διαβάσει ήδη, κ.ά. Οποιαδήποτε πρόσβασή μας στο αρχείο γίνεται με το αντικείμενο αυτό που έχει αποθηκευτεί στο πρόγραμμά μας στη μεταβλητή f, και πάντα αφού έχουμε πρώτα ανοίξει το αρχείο μας. Αφού έχουμε τελειώσει την επεξεργασία του αρχείου με το πρόγραμμά μας πρέπει πάντα να το κλείνουμε με τη συνάρτηση close(), όπως φαίνεται στο τέλος του προγράμματος.
Εδώ, μετά το άνοιγμα του αρχείου. βλέπουμε τη χρήση της μεθόδου readlines(), η οποία όταν καλείται για ένα ανοιχτό file object μας επιστρέφει μια λίστα μέλη της οποίας είναι, ως strings, όλες οι γραμμές του αρχείου κειμένου με το οποίο είναι συνδεδεμένο το file object μας. Έπειτα διανύουμε τη λίστα μας με το συνηθισμένο μας τρόπο και τυπώνουμε όλες τις γραμμές του κειμένου μία προς μία μαζί με τον αύξοντα αριθμό τους.
f = open("myfile.txt", "r")
s = f.readlines()
i = 1
for l in s:
print "Line {i} of file {name}: {line}".format(i=i, name="myfile.txt", line=l)
i += 1
f.close()