Σημειωματάριο Πέμπτης 22 Οκτ. 2015

Ανακύκλωση for

Το επόμενο πρόγραμμα το είχαμε δει την προηγούμενη φορά και βρίσκει αν ο ακέραιος που δίνει ο χρήστης είναι ή όχι πρώτος. Αν δεν είναι πρώτος μας βρίσκει και όλους τους γνήσιους διαιρέτες του.

In [1]: 
n = int(raw_input("Give me a positive integer > 1: "))

isprime = True
divisors = []

for k in range(2, n):
    if n % k == 0:
        isprime = False
        divisors.append(k)

if isprime:
    print "The number %d is a prime." % (n)
else:
    print "The number %d is not a prime." % (n)
    print "The list of divisors is: ",
    for x in divisors:
        print x,

Give me a positive integer > 1: 100
The number 100 is not a prime.
The list of divisors is:  2 4 5 10 20 25 50

Βλέπουμε στο επόμενο πρόγραμμα πώς χρησιμοποιείται η εντολή break. Όταν η εντολή break εκτελεστεί μέσα σε μια ανακύκλωση (όχι μόνο στην ανακύκλωση for) τότε σταματάει αμέσως να εκτελείται η ανακύκλωση αυτή (ούτε οι εντολές που έπονται της break μέσα στην ίδια εκτέλεση της ανακύκλωσης εκτελούνται) και ο έλεγχος του προγράμματος μεταβιβάζεται στην πρώτη εντολή αμέσως μετά το for (την print "END" στο παράδειγμα αυτό).

In [2]: 
for i in range(100):
    print i,
    if i>10:
        break
print "END"

0 1 2 3 4 5 6 7 8 9 10 11 END

Το επόμενο είναι ξανά το πρόγραμμα που αποφασίζει αν ένας ακέραιος είναι πρώτος με τη διαφορά ότι δεν κρατάμε τους διαιρέτες σε λίστα ή αλλού. Το τρέχουμε εδώ για ένα αρκετά μεγάλο ακέραιο και παρατηρούμε πόση ώρα κάνει να τρέξει (θα μπορούσαμε και να είχαμε εισαγάγει κάποιες επιπλέον εντολές python που να μετράγανε το χρόνο ακριβώς αλλά δεν το κάνουμε σε αυτή τη φάση).

Αυτό το κάνουμε για να συγκρίνουμε την ταχύτητα αυτού του προγράμματος με το μεθεπόμενο πρόγραμμα που κάνει την ίδια δουλειά αλλά πολύ πιο έξυπνα και γρήγορα.

In [7]: 
n = int(raw_input("Give me a positive integer > 1: "))

isprime = True


for k in range(2, n):
    if n % k == 0:
        isprime = False


if isprime:
    print "The number %d is a prime." % (n)
else:
    print "The number %d is not a prime." % (n)

Give me a positive integer > 1: 100000000
The number 100000000 is not a prime.

Η παρατήρηση που χρησιμοποιούμε στο επόμενο για να επιταχύνουμε τον έλεγχο του αν ένας ακέραιος είναι πρώτος είναι η παρακάτω πρόταση.

Πρόταση Αν \(n > 1\) είναι ακέραιος τότε ο \(n\) είναι πρώτος αν και μόνο αν δεν έχει διαιρέτες >1 και \(\le \sqrt{n}\).

Απόδειξη Αν ο \(n\) είναι πρώτος τότε δεν έχει καθόλου γνήσιους διαιρέτες, \(\le \sqrt{n}\) είτε \(> \sqrt{n}\) οπότε η μία κατεύθυνση της ισοδυναμίας είναι φανερή. Για την άλλη κατεύθυνση, ας υποθέσουμε ότι ο \(n\) δεν έχει γνήσιους διαιρέτες \(\le\sqrt{n}\). Αν \(k>\sqrt{n}\) είναι κάποιος γνήσιος διαιρέτης του \(n\) τότε ο αριθμός \(d = n/k\) είναι ακέραιος και, αφού \(k>\sqrt{n}\), έχουμε \(d<\sqrt{n}\). Αλλά και ο \(d\) (που δεν είναι ίσος με 1 γιατί \(k \neq n\)) είναι διαιρέτης του \(n\), που αντιφάσκει με την υπόθεσή μας ότι ο \(n\) δεν έχει γνήσιους διαιρέτες \(\le\sqrt{n}\). Άρα δεν υπάρχει τέτοιος διαιρέτης \(k\) και ο \(n\) είναι πρώτος.

Αρκεί λοιπόν, για να είμαστε σίγουροι ότι ο \(n\) είναι πρώτος, να ελέγξουμε ότι δεν έχει διαιρέτες \(\ge 1\) και \(\le \sqrt{n}\). Στην ανακύκλωση for λοιπόν όπου ελέγχουμε όλα τα δυνατά \(k\) για το αν διαιρούν το \(n\) μπορούμε να "σπάσουμε" την ανακύκλωση (με την εντολή break) μόλις το k ξεπεράσει το \(\sqrt{n}\), πράγμα που ελέγχουμε με τη συνθήκη k*k>n.

Με αυτό τον τρόπο ο έλεγχος για το αν ο \(n\) είναι πρώτος παίρνει περίπου \(\sqrt{n}\) ελέγχους ενώ με τον προηγούμενο τρόπο παίρνει περίπου \(n\) ελέγχους. Αυτή η διαφορά είναι τεράστια όταν το \(n\) είναι μεγάλο. Στο παράδειγμα που έχουμε εδώ \(n=10^8\) και αυτό λοιπόν συγκρίνεται με το \(n=10^4\). Τρέχοντας και τους δύο αλγορίθμους η διαφορά στο χρόνο που παίρνουν να τρέξουν είναι οφθαλμοφανής (κάντε το στον υπολογιστή σας).

In [8]: 
n = int(raw_input("Give me a positive integer > 1: "))

isprime = True


for k in range(2, n):
    if k*k>n:
        break
    if n % k == 0:
        isprime = False


if isprime:
    print "The number %d is a prime." % (n)
else:
    print "The number %d is not a prime." % (n)

Give me a positive integer > 1: 100000000
The number 100000000 is not a prime.

Στο επόμενο τροποποιούμε τη γρηγορότερη μέθοδο απόφασης του αν κάποιος ακέραιος είναι πρώτος ώστε να υπολογίζει και πάλι τη λίστα των γνήσιων διαιρετών όταν ο αριθμός είναι σύνθετος. Ο τρόπος που το κάνουμε είναι να παρατηρήσουμε ότι αν ξέρουμε όλους τους διαιρέτες \(k \le \sqrt{n}\) τότε οι μόνοι διαιρέτες που υπάρχουν πέρα από το \(\sqrt{n}\) είναι οι αριθμοί \(n/k\).

Για κάθε λοιπόν ακέραιο \(k \le \sqrt{n}\) που προσθέτουμε στη λίστα διαιρετών divisors προσθέτουμε και τον ακέραιο \(d = n/k\), αλλά μόνο στην περίπτωση που \(d>k\), ώστε να μη προσθέσουμε δύο φορές τον ίδιο τον \(\sqrt{n}\) αν αυτός τύχει να είναι ακέραιος.

In [11]: 
n = int(raw_input("Give me a positive integer > 1: "))

isprime = True
divisors = []

for k in range(2, n):
    if k*k>n:
        break
    if n % k == 0:
        isprime = False
        divisors.append(k)
        d = n/k
        if d > k:
            divisors.append(d)


if isprime:
    print "The number %d is a prime." % (n)
else:
    print "The number %d is not a prime." % (n)
    print "The list of divisors is: ",
    for x in divisors:
        print x,

Give me a positive integer > 1: 100
The number 100 is not a prime.
The list of divisors is:  2 50 4 25 5 20 10

Όμως με το πρόγραμμα στο προηγούμενο κελλί η λίστα διαιρετών δεν βγαίνει ταξινομημένη. Αυτό διορθώνουμε εδώ ώστε η λίστα διαιρετών που υπολογίζουμε να είναι πάντα σε άυξουσα σειρά.

Υπάρχουν πολλοί τρόποι για να γίνει αυτό. Εδώ κρατάμε δύο λίστες διαιρετών, την divisorsS (οι μικροί διαιρέτες, αυτοί που είναι \(\le\sqrt{n}\)) και την divisorsL (οι μεγάλοι διαιρέτες, αυτοί που είναι \(>\sqrt{n}\)). Και τις δύο φροντίζουμε να τις κρατάμε σε αύξουσα σειρά. Για τη λίστα divisorsL, που γεμίζει από το τέλος προς την αρχή, αυτό σημαίνει οτι θα πρέπει τα στοιχεία που προσθέτουμε σε αυτή να τα προσθέτουμε από μπροστά και όχι από πίσω με τη μέθοδο append όπως κάνουμε με τη λίστα divisorsS. Για να προσθέσουμε δηλ. τον ακέραιο d στη λίστα divisorsL δίνουμε την εντολή

divisorsL = [d] + divisorsL

Στο τέλος του προγράμματος απλά τυπώνουμε τα περιεχόμενα της λίστας divisorsS+divisorsL.

In [13]: 
n = int(raw_input("Give me a positive integer > 1: "))

isprime = True
divisorsS = []
divisorsL = []

for k in range(2, n):
    if k*k>n:
        break
    if n % k == 0:
        isprime = False
        divisorsS.append(k)
        d = n/k
        if d > k:
            divisorsL = [d] + divisorsL


if isprime:
    print "The number %d is a prime." % (n)
else:
    print "The number %d is not a prime." % (n)
    print "The list of divisors is: ",
    for x in divisorsS+divisorsL:
        print x,

Give me a positive integer > 1: 100
The number 100 is not a prime.
The list of divisors is:  2 4 5 10 20 25 50

Στο επόμενο κελλί βλέπουμε πώς μπορούμε από μια λίστα αριθμών L να εξάγουμε τους αριθμούς εκείνους της L που είναι \(\ge 0\) και να τους βάλουμε στη λίστα P και τους αριθμούς που είναι \(< 0\) και να τους βάλουμε στη λίστα N.

In [14]: 
L = input("Please give a list of numbers: ")

P = []
N = []

for x in L:
    if x>=0:
        P.append(x)
    else:
        N.append(x)

print "The list of nonnegative elements is:", P
print "The list of negative elements is:",N

Please give a list of numbers: [1.1, 2, -0.5, 3, -.56, 1e8, -1e8]
[1.1, 2, 3, 100000000.0]
[-0.5, -0.56, -100000000.0]

Ως προετοιμασία για ζωγράφισμα σχήματος με αστεράκια στην οθόνη βλέπουμε εδώ πώς μπορούμε να τυπώσουμε ένα \(10\times 10\) τετράγωνο από αστεράκια στην οθόνη.

In [16]: 
for x in range(10):
    for k in range(10):
        print '*',
    print
                

* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *

Κι εδώ πετυχαίνουμε το ίδιο αλλά μόνο με ένα απλό loop, όχι με διπλό loop όπως στο προηγούμενο παράδειγμα. Απλά κάθε 10 αστεράκια που τυπώνουμε αλλάζουμε γραμμή.

In [19]: 
for x in range(100):
    print '*',
    if x%10==9:
        print

* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *
* * * * * * * * * *

Στο παρακάτω πρόγραμμα τυπώνουμε αυτό το "ανθρωπάκι" που βλέπετε ως output του προγράμματος παρακάτω. Η παράμετρος N που προσδιορίζουμε στην αρχή είναι το μήκος των χεριών. Όλες οι άλλες διαστάσεις προσδιορίζονται από αυτόν τον αριθμό και από σταθερές που δεν τις αλλάζουμε (π.χ. το κεφάλι είναι ένα τετράγωνο \(5 \times 5\)).

Η στρατηγική εδώ είναι ότι προχωράει ο σχεδιασμός από πάνω προς τα κάτω και σε κάθε γραμμή τυπώνουμε τον κατάλληλο συνδυασμό από κενούς χαρακτήρες ' ' αστεράκια '*', ανάλογα με το τι θέλουμε να πετύχουμε.

Χρησιμοποιούμε επίσης πολλαπλασιασμό ενός string με αριθμό (αντί για να γράφουμε εσωτερική ανακύκλωση). Έτσι για να γράψουμε 10 αστεράκια το ένα μετά το άλλο τυπώνουμε το string '*'*10. Ή, για να γράψουμε 5 κενούς χαρακτήρες ακολουθούμενους από 10 αστεράκια γράφουμε το string ' '*5 + '*'*10.

In [36]: 
N = 15 # Μήκος χεριών

# Κεφάλι
for x in range(5):
    if x==1:
        print ' '*(N+2)+'** * **' # Γραμμή με τα μάτια
    elif x==3:
        print ' '*(N+2)+'**   **' # Γραμμή με το στόμα
    else:
        print ' '*(N+2)+'*'*7

    
# Λαιμός
for x in range(3):
    print ' '*(N+5)+'*'
    
# Σώμα
for x in range(3):
    print ' '*N+'*'*11
print '*'*(2*N+11) # Γραμμή με τα χέρια
for x in range(7):
    print ' '*N+'*'*11
    
# Πόδια
for x in range(10):
    print ' '*(N+3)+'*'+' '*3+'*'

                 *******
                 ** * **
                 *******
                 **   **
                 *******
                    *
                    *
                    *
               ***********
               ***********
               ***********
*****************************************
               ***********
               ***********
               ***********
               ***********
               ***********
               ***********
               ***********
                  *   *
                  *   *
                  *   *
                  *   *
                  *   *
                  *   *
                  *   *
                  *   *
                  *   *
                  *   *