Τμήμα Μαθηματικών

Πληροφορική Ι

Εβδομάδα 5 · Ο Βρόχος While · Ακέραιες Διαμερίσεις

(Οδηγίες χρήσης του διαδραστικού κώδικα: δείτε την αρχική σελίδα.)

1 Ο Βρόχος While

1.1 Η εντολή `while`

Ο βρόχος while επαναλαμβάνεται όσο μια συνθήκη είναι αληθής — είναι βρόχος ελεγχόμενος με συνθήκη (condition-controlled loop), και ελέγχει τη συνθήκη πριν από κάθε επανάληψη (βρόχος προελέγχου):

while συνθήκη:
    εντολές

Σχηματικά, ο while ελέγχει πρώτα, εκτελεί μετά — αν η συνθήκη είναι εξαρχής False, το σώμα δεν εκτελείται ούτε μία φορά:

flowchart TD
    S(["πριν τον βρόχο"]) --> C{"συνθήκη ;"}
    C -- "True" --> B["σώμα του βρόχου"]
    B --> C
    C -- "False" --> E(["μετά τον βρόχο"])

Η συνθήκη πρέπει να μεταβάλλεται μέσα στον βρόχο ώστε τελικά να γίνει False· διαφορετικά προκύπτει ατέρμονας βρόχος (infinite loop). Ο while είναι πιο γενικός από τον for (Εβδομάδα 4): μπορεί πάντα να τον αντικαταστήσει, ενώ το αντίστροφο δεν ισχύει πάντα — χρησιμοποιούμε while ειδικά όταν το πλήθος των επαναλήψεων δεν είναι εκ των προτέρων γνωστό.

Δεν ξέραμε εκ των προτέρων πόσες επαναλήψεις χρειάζονται — γι’ αυτό while και όχι for. Ας κρατήσουμε το κεφάλαιο κάθε χρονιάς σε μια λίστα και ας το σχεδιάσουμε:

Μια πολύ χρήσιμη τεχνική είναι η επεξεργασία δεδομένων άγνωστου πλήθους μέχρι μια ειδική τιμή τερματισμού (sentinel):

1.2 Χαρακτηριστικό της Python: το ιδίωμα `while True` με `break`

Η Python δεν διαθέτει έτοιμη εντολή “do-while” (βρόχο που ελέγχει τη συνθήκη μετά την πρώτη εκτέλεση, όπως σε άλλες γλώσσες). Το αντίστοιχο ιδίωμα είναι ένας βρόχος while True: (μια συνθήκη που είναι πάντα αληθής, άρα ποτέ δεν σταματάει “μόνη της”) σε συνδυασμό με μια εσωτερική if που κάνει break όταν φτάσουμε στο επιθυμητό σημείο τερματισμού. Έτσι το σώμα του βρόχου εκτελείται σίγουρα τουλάχιστον μία φορά, σε αντίθεση με έναν κανονικό while, που μπορεί να μην εκτελεστεί καθόλου αν η συνθήκη είναι εξαρχής ψευδής:

flowchart TD
    S(["while True"]) --> B["σώμα — εκτελείται πάντα ≥ 1 φορά"]
    B --> C{"συνθήκη τερματισμού ;"}
    C -- "όχι" --> B
    C -- "ναι" --> D["break"] --> E(["έξοδος"])

Αυτό το μοτίβο είναι πολύ συνηθισμένο για επικύρωση εισόδου (input validation): ζήτα μια τιμή, και συνέχισε να ζητάς μέχρι να πάρεις μια αποδεκτή.

1.3 Δυαδική Αναζήτηση (Binary Search)

Στην Εβδομάδα 1 είδαμε τη γραμμική αναζήτηση: σάρωση στοιχείο-στοιχείο, έως και \(n\) έλεγχοι. Αν όμως η λίστα είναι ταξινομημένη, ο while μας επιτρέπει κάτι πολύ αποδοτικότερο — και είναι η τέλεια περίπτωση για while, γιατί δεν ξέρουμε εκ των προτέρων πόσες επαναλήψεις θα χρειαστούν.

Η ιδέα: κρατάμε ένα «παράθυρο» [αριστερά .. δεξιά] όπου μπορεί να βρίσκεται ο στόχος. Σε κάθε βήμα κοιτάμε το μεσαίο στοιχείο· αν δεν είναι ο στόχος, η ταξινόμηση μας λέει σε ποιο μισό να συνεχίσουμε — και πετάμε το άλλο μισό.

Σε φυσική γλώσσα

Όρισε αριστερά = 0 και δεξιά = μήκος(v) - 1.
Όσο αριστερά <= δεξιά (το παράθυρο δεν έχει αδειάσει):
1. μέσο = (αριστερά + δεξιά) // 2.
2. Αν v[μέσο] είναι ο στόχος, βρέθηκε — επίστρεψε μέσο.
3. Αν ο στόχος είναι μικρότερος, συνέχισε αριστερά: δεξιά = μέσο - 1.
4. Αλλιώς συνέχισε δεξιά: αριστερά = μέσο + 1.
Αν το παράθυρο άδειασε, ο στόχος δεν υπάρχει.

Ως διάγραμμα ροής

flowchart TD
    A(["Αρχή"]) --> B["αριστερά = 0
δεξιά = n - 1"]
    B --> C{"αριστερά <= δεξιά ;"}
    C -- "Όχι" --> H["Δεν βρέθηκε (-1)"]
    C -- "Ναι" --> D["μέσο = (αριστερά + δεξιά) // 2"]
    D --> E{"v[μέσο] == στόχος ;"}
    E -- "Ναι" --> F["Βρέθηκε στη θέση μέσο"]
    E -- "Όχι" --> G{"στόχος < v[μέσο] ;"}
    G -- "Ναι" --> I["δεξιά = μέσο - 1"]
    G -- "Όχι" --> J["αριστερά = μέσο + 1"]
    I --> C
    J --> C
    F --> K(["Τέλος"])
    H --> K

Ως κώδικας Python

Με μερικές επιπλέον print, βλέπουμε το παράθυρο να μισοκόβεται σε κάθε επανάληψη:

Πόσο πιο γρήγορη;

Κάθε βήμα υποδιπλασιάζει το παράθυρο, άρα ο αριθμός των βημάτων είναι περίπου \(\log_2 n\) αντί για \(n\):

Οι βρόχοι for και while μάς δίνουν πλέον όλα τα εργαλεία που χρειαζόμαστε για να μελετήσουμε διεξοδικά ένα κλασικό πρόβλημα απαρίθμησης: το πλήθος των τρόπων να γράψουμε έναν αριθμό ως άθροισμα.

2 Ακέραιες Διαμερίσεις (Integer Partitions)

2.1 Τι είναι μια διαμέριση

Μια ακέραια διαμέριση (integer partition) ενός φυσικού αριθμού \(n\) είναι ένας τρόπος να γράψουμε τον \(n\) ως άθροισμα θετικών ακεραίων, όπου η σειρά δεν έχει σημασία. Για παράδειγμα, οι διαμερίσεις του \(4\) είναι:

\[ 4, \quad 3+1, \quad 2+2, \quad 2+1+1, \quad 1+1+1+1, \]

δηλαδή υπάρχουν \(5\) διαμερίσεις του \(4\) (γράφουμε \(p(4) = 5\)). Παρατηρήστε ότι το \(3+1\) και το \(1+3\) θεωρούνται η ίδια διαμέριση (γι’ αυτό διαφέρει ριζικά από τις μεταθέσεις, όπου η σειρά μετρούσε).

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

flowchart TD
    R["διαμέρισε 4"] --> A["4"]
    R --> B["3 + διαμέρισε 1 (μέρη ≤ 3)"]
    R --> C["2 + διαμέρισε 2 (μέρη ≤ 2)"]
    R --> D["1 + διαμέρισε 3 (μέρη ≤ 1)"]
    B --> B1["3 + 1"]
    C --> C1["2 + 2"]
    C --> C2["2 + 1 + 1"]
    D --> D1["1 + 1 + 1 + 1"]

Ας τις παράγουμε naively — χωρίς κομψά τεχνάσματα, και συγκεκριμένα χωρίς αναδρομή (θα τη δούμε στην Εβδομάδα 9).

Η στρατηγική είναι αυτή του δέντρου παραπάνω: επιλέγουμε το μεγαλύτερο μέρος first (όχι μεγαλύτερο από ένα όριο max_part, ώστε τα μέρη να μένουν φθίνοντα), και μετά διαμερίζουμε το υπόλοιπο n - first με την ίδια λογική.

Κάθε «κλαδί» του δέντρου είναι ένα εκκρεμές υποπρόβλημα. Αντί να τα διαχειριστεί αυτόματα η Python (αυτό κάνει η αναδρομή), τα διαχειριζόμαστε εμείς με μια ρητή στοίβα (stack) — μια λίστα όπου βάζουμε υποπροβλήματα με append και τα βγάζουμε από το τέλος με pop, μέσα σε έναν while που τρέχει όσο η στοίβα δεν είναι άδεια:

Παρατηρήστε πόσο «χειροκίνητη» είναι αυτή η λύση: διαχειριζόμαστε εμείς τη στοίβα των εκκρεμών υποπροβλημάτων. Στην Εβδομάδα 9 θα ξαναδούμε το ίδιο πρόβλημα με αναδρομή, όπου η Python κάνει αυτή τη δουλειά αυτόματα.

Προς το παρόν, ας δούμε πώς να μετρήσουμε αποδοτικά το πλήθος \(p(n)\), χωρίς καν να παράγουμε τις διαμερίσεις — με μόνο εργαλεία for, while και λίστες.

2.2 Η συνάρτηση διαμέρισης \(p(n)\): πόσο γρήγορα μεγαλώνει;

Η all_partitions_naive παράγει ρητά όλες τις διαμερίσεις — κάτι που γίνεται γρήγορα απαγορευτικό: το \(p(50)\) ξεπερνά ήδη τις \(200{.}000\), και το \(p(100)\) τα \(190\) εκατομμύρια.

Αν μας ενδιαφέρει μόνο το πλήθος \(p(n)\) (όχι η ίδια η λίστα), υπάρχει πολύ πιο αποδοτικός τρόπος: ο δυναμικός προγραμματισμός (dynamic programming), εδώ με δύο απλούς ένθετους for — όχι αναδρομή.

Κρατάμε έναν πίνακα dp, όπου το dp[i] = πλήθος τρόπων να γραφτεί το i ως άθροισμα μερών από το σύνολο {1, ..., part}, με επανάληψη επιτρεπτή (π.χ. 6 = 2+2+2). Ο εξωτερικός βρόχος προσθέτει ένα δυνατό μέρος part κάθε φορά:

για κάθε i >= part, κάνουμε dp[i] += dp[i - part] — προσθέτουμε τους τρόπους που χρησιμοποιούν το part μία ακόμα φορά·
όταν εξεταστούν όλα τα μέρη μέχρι το N, ισχύει dp[i] == p(i) για κάθε i.

Ας δούμε πόσο γρήγορα μεγαλώνει το \(p(n)\) σε σχέση με το \(n\). Σε λογαριθμική κλίμακα στον κατακόρυφο άξονα (αλλιώς οι τελευταίες τιμές είναι τόσο μεγάλες που “ισοπεδώνουν” τις πρώτες):

Μια ευθεία γραμμή σε λογαριθμικό άξονα σημαίνει εκθετική ανάπτυξη· η καμπύλη του \(p(n)\) είναι λίγο πιο ήπια από ευθεία (υπο-εκθετική), αλλά πολύ πιο απότομη από κάθε πολυώνυμο. Η ακριβής συμπεριφορά δίνεται από τον περίφημο ασυμπτωτικό τύπο των Hardy και Ramanujan (1918):

\[ p(n) \sim \frac{1}{4n\sqrt{3}} \, e^{\pi\sqrt{2n/3}}. \]

2.3 Μοτίβα διαιρετότητας: οι ταυτότητες του Ramanujan

Ας εξετάσουμε τις τιμές του \(p(n)\) πάνω σε ειδικές αριθμητικές προόδους, δηλαδή για \(n\) της μορφής \(2n\), \(3n+2\), \(5n+4\):

Στις δύο πρώτες ακολουθίες δεν φαίνεται κάποιο προφανές μοτίβο διαιρετότητας. Στην τρίτη όμως κάτι ξεχωριστό συμβαίνει — ας το ελέγξουμε ρητά:

Αυτή είναι μία από τις περίφημες ταυτότητες διαιρετότητας του Ramanujan (1919):

\[ p(5n+4) \equiv 0 \pmod{5}. \]

Υπάρχουν και δύο “αδελφές” ταυτότητες, \(p(7n+5) \equiv 0 \pmod 7\) και \(p(11n+6) \equiv 0 \pmod{11}\) — δοκιμάστε τις στον παραπάνω κώδικα, αλλάζοντας κατάλληλα τους αριθμούς. Το γεγονός ότι το \(3n+2\) δεν έδειξε κανένα μοτίβο, ενώ το \(5n+4\) έδειξε ένα τόσο καθαρό, δείχνει ότι αυτές οι τρεις σχέσεις (mod 5, 7, 11) είναι κάτι πολύ ειδικό — όχι κάτι που ισχύει “τυχαία” για οποιαδήποτε αριθμητική πρόοδο.

Οπτικοποίηση σε 5 στήλες

Ένας κλασικός τρόπος να “δει κανείς με το μάτι” το μοτίβο mod 5 είναι να τυπώσουμε τις τιμές του \(p(n)\) σε πίνακα με 5 στήλες, όπου η στήλη \(n \equiv 4 \pmod 5\) (η τελευταία) θα πρέπει να είναι πάντα πολλαπλάσιο του 5:

Ακόμα καθαρότερα: χρωματίζουμε κάθε κελί n με το υπόλοιπο p(n) % 5. Η στήλη n ≡ 4 (mod 5) βγαίνει ολόκληρη ένα χρώμα — το μηδέν:

2.4 Η ιστορία: ο Ramanujan και ο πίνακας του MacMahon

Στις αρχές του 20ού αιώνα, ο Βρετανός μαθηματικός Major Percy MacMahon υπολόγισε με το χέρι έναν εκτενή πίνακα τιμών του \(p(n)\), μέχρι και το \(p(200)\) — έργο τεράστιας υπομονής, αφού δεν υπήρχε τότε κλειστός τύπος.

Ο ινδός μαθηματικός Srinivasa Ramanujan, μελετώντας αυτόν τον πίνακα γύρω στο 1919, παρατήρησε κάτι που είχε ξεφύγει από όλους: κάθε πέμπτη τιμή (\(p(4), p(9), p(14), \ldots\)) ήταν πάντα πολλαπλάσιο του 5. Βρήκε και αντίστοιχα μοτίβα modulo 7 και 11, και υποψιάστηκε ότι υπάρχουν άπειρα τέτοια για κάθε «αρκετά ειδικό» modulo.

Οι εικασίες αυτές — οι ταυτότητες διαιρετότητας του Ramanujan — τροφοδότησαν δεκαετίες έρευνας στη Θεωρία Αριθμών· η πλήρης εξήγηση ήρθε τη δεκαετία του 2000, από τον Ken Ono.

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

3 Σύνοψη

Σε αυτή την εβδομάδα είδαμε:

Τον βρόχο while, και το ιδίωμα while True + break (το ισοδύναμο ενός do-while).
Τη δυαδική αναζήτηση σε ταξινομημένη λίστα: ~\(\log_2 n\) βήματα αντί για \(n\), με παράθυρο που μισοκόβεται σε κάθε επανάληψη.
Πώς να παράγουμε συνδυαστικά αντικείμενα naively, με μια ρητή στοίβα (stack) αντί για αναδρομή — μια τεχνική “χειροκίνητης” προσομοίωσης αναδρομής με βρόχο.
Δυναμικό προγραμματισμό: έναν πίνακα dp για αποδοτική καταμέτρηση, χωρίς να παράγουμε ρητά όλα τα αντικείμενα.
Την τεχνική της υπολογιστικής επαλήθευσης ενός μοτίβου σε μεγάλη κλίμακα δεδομένων, πριν (ή αντί) από μια αυστηρή απόδειξη.

⤺ Πίσω στην αρχική σελίδα / πρόγραμμα μαθήματος · Διαφάνειες αυτής της εβδομάδας