Σημειωματάριο Πέμπτης 12 Μαρτίου 2015

Εγγραφή σε αρχεία

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

Αρχίζουμε διαβάζοντας το αρχείο με το συνηθισμένο μας τρόπο, αφαιρούμε τα newlines από τα strings των γραμμών με τη μέθοδο rstrip, και δημιουργούμε ένα κενό λεξικό person στο οποίο θα κρατάμε το τρέχον ποσό του κάθε ατόμου.

Δημιουργούμε μια λίστα λέξεων words από κάθε γραμμή με διαχωριστικούς χαρακτήρες τους λευκούς (με τη μέθοδο split). Αν η λίστα αυτή λέξεων είναι κενή αυτό σημαίνει ότι έχουμε συναντήσει μια κενή γραμμή στο αρχείο και απλά την προσπερνούμε (continue) χωρίς να κάνουμε κάτι γι' αυτήν. Αν η λίστα δεν είναι κενή τότε η πρώτη λέξη της λίστας είναι το όνομα του ατόμου το οποίο το αποθηκεύουμε στη μεταβλητή name. Έπειτα αφαιρούμε από τη λίστα λέξεων το πρώτο της στοιχείο (το όνομα) ώστε αυτό που απομένει είναι μια λίστα από strings που το καθένα τους αναπαριστά ένα αριθμό.

Στη γραμμή linetotal = sum([float(x) for x in words]) υπολογίζουμε το άθροισμα των ποσών αυτών. Η λίστα από strings μετατρέπεται πρώτα σε μια λίστα αριθμών με το float και αυτής της λίστας παίρνουμε το άθροισμα.

Έπειτα κοιτάμε στο λεξικό person και ανάλογα με το αν το άτομο είναι ήδη μέσα ή όχι είτε επαυξάνουμε το ποσό του είτε το εισάγουμε στο λεξικό με το ποσό αυτό.

Αφού έχουμε τελειώσει τον υπολογισμό του λεξικού ανοίγουμε το αρχείο totals.txt για γράψιμο ("w") και για κάθε άτομο του λεξικού γράφουμε μια γραμμή στο αρχείο με το όνομα και το συνολικό ποσό (παρατηρείστε ότι περιλαμβάνουμε το χαρακτήρα newline "\n" στην κλήση της f.write η οποία, σε αντίθεση με την print, δεν τυπώνει από μόνη της αλλαγές γραμμής. Τέλος κλείνουμε το αρχείο.

Το αρχείο totals.txt που παράγεται πρέπει να έχει τη μορφή που φαίνεται εδώ.

In [21]:

f = open("sums.txt", "r")
lines = f.readlines()
f.close()

lines = [x.rstrip() for x in lines]

person={}

for l in lines:
    words = l.split()
    if len(words) == 0:
        continue
    name = words[0]
    words.pop(0)
    linetotal = sum([float(x) for x in words])    
    if name in person:
        person[name] += linetotal
    else:
        person[name] = linetotal

f = open("totals.txt", "w")
for p in person:
    f.write("{onoma} {poso}\n".format(onoma=p, poso=person[p]))
f.close()

Υπολογισμοί διάφορων αθροισμάτων με for loops

Εδώ βλέπουμε πώς μπορούμε να υπολογίσουμε το άθροισμα $\sum_{i=0}^N i^2$.

In [12]:

N = int(raw_input("Give me N: "))
s = 0.0
for i in range(N+1):
    s += i**2
print s

Give me N: 60
73810.0

Ένα διπλό άθροισμα όπως το $\sum_{i=1}^N \sum_{j=1}^i \cos(i+j)$ χρειάζεται ένα διπλό loop για να υπολογιστεί. Το εξωτερικό loop μετακινεί τη μεταβλητή $i$ και το εσωτερικό loop μετακινεί τη μεταβλητή $j$.

In [13]:

import math
N = int(raw_input("Give me N: "))
s = 0.0
for i in range(1, N+1):
    for j in range(1, i+1):
        s += math.cos(i+j)
print s

Give me N: 8
-1.67083230375

Σε περίπτωση που το άθροισμα είναι το $\displaystyle \sum_{\substack{i,j=1\\ i+j\le N}}^N \cos(i+j)$ τότε χρειάζεται αφενός διπλό loop αλλά χρειάζεται και να ελέγχουμε μέσα στο εσωτερικό loop αν ισχύει η επιθυμητή συνθήκη $i+j \le N$ και μόνο τότε επαυξάνουμε το τρέχον άθροισμα $s$.

In [14]:

import math
N = int(raw_input("Give me N: "))
s = 0.0
for i in range(1, N+1):
    for j in range(1, N+1):
        if i+j<=N:
            s+=math.cos(i+j)
print s

Give me N: 6
1.57843748277

Το κόσκινο του Ερατοσθένη

Εδώ υλοποιούμε το λεγόμενο κόσκινο του Ερατοσθένη που είναι ένας αλγόριθμος για την εύρεση όλων των πρώτων αριθμών από το 2 έως το N.

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

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

Ξεκινάμε λοιπόν με μια λίσταL με μήκος N+1 που στην αρχή περιέχει μόνο μηδενικά. Κάνουμε τη σύμβαση ότι αν σε μια θέση i της λίστας έχουμε L[i] == 0 τότε το στοιχείο δεν είναι "διαγραμμένο" ενώ αν L[i] == 1 τότε θεωρούμε ότι το στοιχείο i έχει διαγραφεί. Θέτουμε λοιπόν L[0] = L[1] = 1 εξ αρχής μια και τα στοιχεία 0 και 1 δε θέλουμε να παίξουν κάποιο ρόλο στα περαιτέρω. Ορίζουμε επίσης τη λίστα primes να είναι αρχικά κενή (θα γεμίσει με τους πρώτους).

Με το εξωτερικό while επαναλαμβάνουμε αυτά που πρέπει να κάνουμε (α) και (β) παραπάνω. Η επανάληψη αυτή σταματάει όταν δεν υπάρχει πλέον στοιχείο της λίστας που δεν έχει διαγραφεί, συνθήκη που ελέγχεται βλέποντας αν το άθροισμα όλων των στοιχείων της λίστας είναι το ίδιο με το μήκος της λίστας (σε αυτή και μόνο την περίπτωση έχουν διαγραφεί όλα).

Στο εσωτερικό while ξεκινάμε το μετρητή i από 2 και προχωράμε μέχρι να βρούμε το πρώτο μη διαγραμμένο στοιχείο. Αυτό το στοιχείο το βάζουμε στη λίστα με τους πρώτους και διαγράφουμε αυτό και όλα τα πολλαπλάσιά του από τη λίστα. Για την ακρίβεια διαγράφουμε όλα τα πολλαπλάσια του στοιχείου i που είναι $\le N$. Το τελευταίο τέτοιο πολλαπλάσιο είναι το $ki$, όπου $k=N/i$ είναι το πηλίκο της διαίρεσης N/i (ή, με άλλα λόγια, το ακέραιο μέρος του N/i).

In [18]:

N = int(raw_input("Give me N: "))
L = [0]*(N+1)
L[0] = 1
L[1] = 1
primes = []

while sum(L) < len(L):
    i=2
    while L[i] == 1:
        i += 1
    primes.append(i)
    for k in range(1,N/i+1):
        L[k*i] = 1

print primes

Give me N: 1000
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

Το τρίγωνο του Pascal

Ο διωνυμικός συντελεστής $n$ ανά $k$, που συμβολίζεται με ${n \choose k}$, είναι το πλήθος των τρόπων με τους οποίους μπορούμε να επιλέξουμε $k$ διαφορετικούς από τους αριθμούς $1, 2, \ldots, n-1, n$ όταν δε μας ενδιαφέρει η σειρά της επιλογής. Αποδεικνύεται ότι αν $0 \le k \le n$ τότε ισχύει $\displaystyle {n \choose k} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$. Επίσης αποδεικνύεται ότι $ = {n-1 k} + {n k-1}. $

Αυτή είναι η ιδιότητα που καθιστά δυνατό τον υπολογισμό όλων των συντελεστών ${n \choose k}$ με επανειλημμένη χρήση της παραπάνω ισότητας. Αν διατάξουμε τους διωνυμικούς συντελεστές ώστε συντελεστές με το ίδιο $n$ να είναι στην ίδια γραμμή όπως παρακάτω

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

αθροίζοντας τα δύο στοιχεία που είναι από πάνω και παρατηρώντας ότι πάντα το πρώτο και το τελευταίο στοιχείο είναι 1.

Τυπώνουμε λοιπόν την πρώτη γραμμή (ένα 1 μόνο). Στον υπολογισμό κάθε γραμμής θα χρησιμοποιήσουμε την προηγούμενη γραμμή που την έχουμε αποθηκευμένη στη λίστα L. Η νέα λίστα δημιουργείται στη μεταβλητή LL. Στο εξωτερικό loop μετακινούμε τη μεταβλητή n από 1 έως N. Για κάθε τέτοιο n και για κάθε k από 1 έως n-1 υπολογίζουμε το διωνυμικό συντελεστή αθροίζοντας τα δύο από πάνω στοιχεία (από τη λίστα L) και το προσθέτουμε στη λίστα LL. Τέλος προσθέτουμε και το στοιχείο 1 στη λίστα LL ως τελευταίο στοιχείο.

Τέλος τυπώνουμε τις N αυτές γραμμές.