Η συνάρτηση isprime παρακάτω επιστρέφει True όταν ο ακέραιος n που της περνάμε είναι πρώτος, αλλιώς επιστρέφει False
def isprime(n):
"""
Επιστρέφει True αν και μόνο αν ο n είναι πρώτος
"""
if n<=1: # Πρώτοι θεωρούνται μόνο φυσικοί αριθμοί > 1
return False
d = 2
while d*d <= n: # Δοκιμάζουμε όλους τους ακεραίους από 2 έως την τετρ. ρίζα του n
if n%d == 0: # Αν βρήκαμε διαιρέτη επιστρέφουμε αμέσως False
return False
d += 1
return True # Το while παραπάνω τελείωσε και δε βρήκαμε διαιρέτη. Επιστρέφουμε True.
l = [2, 3, 4, 5, 10,11, 12, 29, 30] # Δοκιμάζουμε τη συνάρτηση isprime σε όλους αυτούς τους αριθμούς
for n in l:
if isprime(n):
print "Ο αριθμός %d είναι πρώτος" % n
else:
print "Ο αριθμός %d δεν είναι πρώτος" % n
Η συνάρτηση factors παρακάτω επιστρέφει σε μια λίστα (και μάλιστα με αύξουσα σειρά) όλους του φυσικούς αριθμούς που διαιρούν το φυσικό αριθμό n που της περνάμε ως όρισμα.
def factors(n):
"""
Επιστρέφει τη λίστα όλων των διαιρετών του n
που είναι στη διάστημα από 1 έως n.
Ο αριθμός n που περνάμε στη συνάρτηση πρέπει να είναι ακέραιος >= 1.
"""
l = [] # Σε αυτή τη λίστα βάζουμε κάθε διαιρέτη που βρίσκουμε
for i in range(1, n+1):
if n%i == 0:
l.append(i) # Βρήκαμε ένα διαιρέτη i του n και τον προσθέτουμε στη λίστα
return l
l = [2, 3, 4, 5, 10,11, 12, 29, 30] # Δοκιμάζουμε τη συνάρτησή μας σε όλους αυτούς τους ακεραίους
for n in l:
print "Η λίστα διαιρετών του %d είναι η %r." % (n, factors(n))
Αν \(a, b > 0\) είναι δύο ακέραιοι τότε ο Μέγιστος Κοινός Διαιρέτης τους (ΜΚΔ) είναι ο μέγιστος ακέραιος που διαιρεί και το \(a\) και το \(b\). Παρακάτω δίνουμε μια απλή συνάρτηση gcd(a,b) για τον υπολογισμό του ΜΚΔ των a και b, η οποία χρησιμοποιεί τη συνάρτηση factors που γράψαμε προηγουμένως.
def factors(n):
"""
Επιστρέφει τη λίστα όλων των διαιρετών του n
που είναι στη διάστημα από 1 έως n.
Ο αριθμός n που περνάμε στη συνάρτηση πρέπει να είναι ακέραιος >= 1.
"""
l = [] # Σε αυτή τη λίστα βάζουμε κάθε διαιρέτη που βρίσκουμε
for i in range(1, n+1):
if n%i == 0:
l.append(i) # Βρήκαμε ένα διαιρέτη i του n και τον προσθέτουμε στη λίστα
return l
def gcd(a, b):
"""
Επιστρέφει το ΜΚΔ των a, b. Τα a, b πρέπει να είναι ακέραιοι > 0.
"""
da = factors(a) # Βρίσκουμε τη λίστα με τους διαιρέτες του a
db = factors(b) # Βρίσκουμε τη λίστα με τους διαιρέτες του b
dab = [] # Εδώ βάζουμε τους κοινούς διαιρέτες των a, b
for x in da:
if x in db:
dab.append(x) # Το x είναι και στη λίστα da και στη λίστα db και άρα είναι κοινός διαιρέτης
return max(dab) # Επιστρέφουμε το μέγιστο κοινό διαιρέτη
print gcd(30, 25)
Ο προηγούμενος αλγόριθμος είναι πολύ απλός αλλά μπορεί επίσης να είναι και πολύ αργός. Ο λόγος είναι ότι στηρίζεται στην εύρεση όλων των διαιρετών των δύο αριθμών, και αυτή η διαδικασία είναι πάρα πολύ αργή όταν οι αριθμοί είναι μεγάλοι.
Ο αλγόριθμος του Ευκλείδη όμως, που είναι αυτός που πάντα χρησιμοποιούμε για την εύρεση του ΜΚΔ, είναι πολύ πιο γρήγορος και δε χρειάζεται να βρει τους διαιρέτες των δύο αριθμών. Η βασική παρατήρηση που κάνει τον αλγόριθμο να δουλεύει είναι η εξής.
Αν \(a \ge b > 0\) είανι δύο φυσικοί αριθμοί και \(r \in \{0, 1, 2, ... , b-1\}\) είναι το υπόλοιπο της διαίρεσης \(a/b\) τότε ο ΜΚΔ των \(a, b\) είναι ίσος με τον ΜΚΔ των \(b, r\). Ο μεγαλύτερος δηλ. από τους δύο αριθμούς, ο \(a\), αντικαταστάθηκε από έναν άλλο, τον \(r\), ο οποίος είναι μικρότερος από τον μικρότερο από τους αρχικούς δύο αριθμούς, δηλ. τον \(b\). Εφαρμοίζοντας συνεχώς αυτή την αναγωγή φτάνουμε σε κάποια στιγμή σε ένα ζεύγος αριθμών όπου το υπόλοιπο είναι \(0\), όπου δηλ. ο μικρότερος από τους δύο αριθμούς διαιρεί το μεγαλύτερο. Σε αυτή την περίπτωση είναι προφανές ότι ο ΜΚΔ είναι ο μικρότερος από τους δύο αριθμούς.
Η συνάρτηση gcd(a, b) που βλέπετε παρακάτω υλοποιεί ακριβώς αυτό τον αλγόριθμο. Πρώτα τυπώνουμε ένα ενημερωτικό μήνυμα ώστε να φαίνεται στο τέλος από ποια ζευγάρια πέρασε η συνάρτηση για να υπολογίσει το ΜΚΔ των δύο αριθμών. Έπειτα ελέγχουμε αν ο χρήστης πέρασε στον αριθμό b κάποιον που είναι μικρότερος από τον a. Αν αυτό έγινε τότε ανταλλάσουμε τις τιμές των δύο ορισμάτων ώστε από δω και πέρα να είμαστε σίγουροι ότι ο a είναι ο μεγαλύτερος.
Έπειτα ελέγχουμε αν ο b διαιρεί τον a. Αν αυτό συμβαίνει τότε ο ΜΚΔ είναι φυσικά ο b, και άρα επιστρέφουμε αυτό.
Αν το υπόλοιπο r δεν είναι 0 τότε επιστρέφουμε το ΜΚΔ των b και r. Πώς τον βρίσκουμε αυτόν; Απλά η συνάρτηση gcd καλεί τον εαυτό της (με άλλα ορίσματα φυσικά από αυτά που της είχαμε περάσει). Μια τέτοια συνάρτηση, που καλεί δηλ. τον εαυτό της, λέγεται αναδρομική (recursive) συνάρτηση. Με τον τρόπο αυτό πολλές συναρτήσεις που αλλιώς είναι πολύπλοκες να γραφούν γράφονται με πολύ εύκολο και καθαρό κώδικα. Χρειάζεται φυσικά προσοχή ώστε η κλήση αυτή (από μια συνάρτηση στον εαυτό της) να μη γίνεται επ' άπειρο.
def gcd(a, b):
"""
Βρίσκει το ΜΚΔ των a, b με τον αλγόριθμο του Ευκλείδη.
Αναδρομική συνάρτηση (καλεί τον εαυτό της).
"""
print "Computing gcd(%d, %d)" % (a, b)
if b>a:
a, b = b, a # Φροντίζουμε το b να είναι πάντα το μικρότερο από τα δύο
r = a%b # Το υπόλοιπο της διαίρεσης a/b
if r == 0: # Αν το b διαιρεί το a τελειώσαμε. Ο ΜΚΔ είναι το b.
return b
return gcd(b, r) # Αλλιώς υπολογίζουμε το ΜΚΔ των b, r και επιστρέφουμε αυτό.
print gcd(968745278367, 256273642395)
Η ακολουθία Fibonacci \(f_n\) για \(n=1, 2, \ldots\), ορίζεται ως εξής:
\(f_1 = f_2 = 1\) και
\(f_n = f_{n-1}+f_{n-2}\), για \(n \ge 3\).
Παρακάτω δίνουμε δύο συναρτήσεις για τον υπολογισμό της \(f_n\), τις fibr και fib (η πρώτη είναι αναδρομική αλλά όχι η δεύτερη).
Η fibr είναι ουσιαστικά μια μετάφραση του ορισμού της \(f_n\) σε γλώσσα Python, κι εδώ φαίνεται πολύ καθαρά η δύναμη της αναδρομής (αλλά όχι τα μειονεκτήματά της: η μη αναδρομική συνάρτηση fib είναι πολύ γρηγορότερη από την fibr).
Διαβάστε τα σχόλια που υπάρχουν μέσα στις δύο συναρτήσεις για να καταλάβετε πώς δουλεύουν.
def fibr(n):
"""
Υπολογίζει το n-οστό όρο της ακολουθίας Fibonacci (αναδρομική).
"""
if n==1 or n==2:
return 1 # Αν n=1 ή 2 επιστρέφουμε 1
return fibr(n-1)+fibr(n-2) # Αλλιώς καλούμε την ίδια τη συνάρτηση με μικρότερες τιμές.
def fib(n):
"""
Υπολογίζει το n-οστό όρο της ακολουθίας Fibonacci (μη αναδρομική).
"""
if n==1 or n==2:
return 1 # Αν n=1 ή 2 επιστρέφουμε 1
prev = 1
prevprev = 1 # Χρησιμοποιούμε τις δύο μεταβλητές prev και prevprev για να κρατάμε το προηγούμενο και
# το προ-προηγούμενο στοιχείο αυτού που υπολογίζουμε κάθε φορά.
for k in range(3, n+1): # Για να υπολογίσουμε τo f_n πρέπει να υπολογίσουμε και όλα τα f_k για όλα
# τα μικρότερα k.
f = prev + prevprev # Γνωρίζοντας τα δύο προηγούμενα η τιμή f του τρέχοντος n υπολογίζεται από το άθροισμά τους
prevprev = prev
prev = f # Με αυτή τη γραμμή και την προηγούμενη ενημερώνονται οι μεταβλητές prev και prevprev
# με τις νέες τιμές τους, τώρα που υπολογίσαμε μια ακόμη τιμή της ακολουθίας.
return f
print fib(30), fibr(30)
Για να βρούμε τα υποσύνολα του συνόλου \(S = \{s_1, s_2, \ldots, s_n\}\) τα χωρίζουμε σε δύο κατηγορίες. Στην κατηγορία 1 μπαίνουν όλα τα υποσύνολα που δεν περιέχουν το στοιχείο \(s_1\) ενώ στην κατηγορία 2 αυτά που το περιέχουν.
Παρατηρούμε ότι τα υποσύνολα κατηγορίας 1 είναι ακριβώς όλα τα υποσύνολα του \(S' = \{ s_2, s_3, \ldots, s_n\}\). Επίσης τα υποσύνολα κατηγορίας 1 και τα υποσύνολα κατηγορίας 2 είναι σε 1 προς 1 αντιστοιχεία μέσω της απεικόνισηςπου απεικονίζει το τυχόν σύνολο A κατηγορίας 1 σε ένα μοναδικό υποσύνολο κατηγορίας 2.
Η συνάρτησή μας λοιπόν, subsets(S) λειτουργεί αναδρομικά. Η βασική περίπτωση (εκεί όπου σταματάνε οι αναδρομικές κλήσεις προς τον εαυτό της) είναι όταν το σύνολό μας είναι το κενό, όταν δηλ. S=[], οπότε το μόνο υποσύνολο είναι το κενό και άρα η λίστα με όλα τα υποσύνολα (που επιστρέφει η subsets) είναι η [ [] ].
Διαβάστε τα σχόλια μέσα στη συνάρτηση για να δείτε πώς δουλεύει.
def subsets(S):
"""
Επιστρέφει μια λίστα με όλα τα υποσύνολα του S (που είναι επίσης μια λίστα)
"""
if len(S) == 0: # Αν S είναι το κενό σύνολο τότε το μόνο υποσύνολο είναι το κενό.
return [[]]
l = subsets(S[1:]) # Εδώ υπολογίζουμε όλα τα υποσύνολα που δεν περιέχουν το πρώτο στοιχείο (αναδρομική κλήση)
ret = []
for s in l: # Εδώ βάζουμε μαζί όλα τα υποσύνολα κατηγορίας 1 (που βρήκαμε με την αναδρομική κλήση) και για κάθε
# υποσύνολο κατηγορίας 1 βάζουμε και το υποσύνολο κατηγοριας 2 που προκύπτει αν προσθέσουμε στο
# υποσύνολό μας το στοιχείο s_1
ret.append(s)
ret.append(S[:1] + s)
return ret
print subsets([1, 2, 3])
Η έκφραση \((x_n x_{n-1} \cdots x_2 x_1 x_0)_b\) ονομάζεται το \(b\)-αδικό ανάπτυγμα του \(x\) και τα \(x_j\) ονομάζονται \(b\)-αδικά ψηφία του \(x\).
Η συνηθισμένη περίπτωση είναι η \(b=10\) οπότε μιλάμε για το 10-αδικό ανάπτυγμα του \(x\), και τα \(x_j\) είναι τα συνηθισμένα του δεκαδικά ψηφία, που είναι όλα από 0 έως 9. Δεν υπάρχει όμως κάτι πραγματικό ιδιαίτερο με την περίπτωση \(b=10\) και κάθε αριθμός έχει ένα (μοναδικό) ανάπτυγμα σε κάθε βάση \(b\).
Μια ιδιαίτερα σημαντική περίπτωση είναι η περίπτωση \(b=2\). Στο δυαδικό ανάπτυγμα του \(x\)
όλα τα ψηφία \(x_j\) είναι είτε 0 είτε 1.
Στην παρακάτω συνάρτηση binary(n) υπολογίζουμε τα δυαδικά ψηφία του n σε μια λίστα. Το πρώτο στοιχείο της λίστας είναι το ψηφίο των μονάδων (το \(x_0\)).
Από την παραπάνω εξίσωση για το \(x\) προκύπτει ότι ο αριθμός \(x-x_0\) είναι άρτιος και επίσης ότι
Η τελευταία ισότητα μας λέει ότι το δυαδικό ανάπτυγμα του \(\frac{x-x_0}{2}\) είναι το \((x_n x_{n-1} \cdots x_2 x_1)_2\). Σε αυτή την παρατήρηση στηρίζουμε την αναδρομική κλήση. Η άλλη βασική παρατήρηση είναι ότι το \(x_0\) είναι 0 αν το \(x\) είναι άρτιο και 1 αν το \(x\) είναι περιττό.
Στα σχόλια της συνάρτησης θα βρείτε περισσότερη λεπτομέρεια.
def binary(n):
"""
Επιστρέφει μια λίστα με τα δυαδικά ψηφία του n.
L[0] θα είναι το ψηφίο των μονάδων.
"""
if n==0 or n==1:
return [ n ] # Αν ο αριθμός δεν έχει παρά μόνο ενα ψηφίο τότε δεν κάνουμε αναδρομή
# αλλά επιστρέφουμε μόνο το ένα αυτό ψηφίο.
if n%2 == 0: # Σε αυτό το if υπολογίζουμε το πρώτο ψηφίο (το x_0 στο κείμενο παραπάνω).
digit = 0
else:
digit = 1
l = binary( (n-digit)/2 ) # Εδώ κάνουμε την αναδρομική κλήση που περιγράφεται παραπάνω.
# Μας επιστρέφει τη λίστα l που είανι η λίστα [x_1, x_2, ...]
return [digit] + l # Προσθέτουμε σε αυτή τη λίστα το x_0 που είχαμε βρει πριν και επιστρέφουμε
ll = binary(1024)
print ll[::-1] # Τυπώνουμε τη λίστα των ψηφίων με την ανάποδη σειρά ώστε να δούμε το δυαδικό ανάπτυγμα με το
# συνηθισμένο τρόπο.