Πληροφορική Ι — Εβδομάδα 5

Ο Βρόχος While · Ακέραιες Διαμερίσεις

Η εντολή while

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

while ελέγχει τη συνθήκη πριν από κάθε επανάληψη· γενικεύει τον for.

Sentinel & while True + break

while True: + break = ισοδύναμο ενός do-while (εκτελείται τουλάχιστον μία φορά).

Δυαδική αναζήτηση

Ταξινομημένη λίστα · παράθυρο [αριστερά..δεξιά] · μισό κάθε βήμα · πλήθος επαναλήψεων άγνωστο → while

flowchart LR
    C{"αριστερά ≤ δεξιά ;"} -- όχι --> H["-1"]
    C -- ναι --> M["μέσο = (αρ+δε)//2"]
    M --> E{"v[μέσο] ; στόχος"}
    E -- "=" --> F["μέσο"]
    E -- "στόχος <" --> L["δεξιά = μέσο-1"] --> C
    E -- "στόχος >" --> R["αριστερά = μέσο+1"] --> C

Ακέραιες Διαμερίσεις

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

\(4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1\) → \(p(4)=5\) (η σειρά δεν μετράει).

Naive παραγωγή με ρητή στοίβα

Χωρίς αναδρομή: εμείς διαχειριζόμαστε τη στοίβα ρητά, γραμμή προς γραμμή:

def all_partitions_naive(n):
    results = []
    stack = [(n, n, [])]
    while stack:
        remaining, max_part, chosen = stack.pop()
        if remaining == 0:
            results.append(chosen)
            continue
        for first in range(1, min(remaining, max_part) + 1):
            stack.append((remaining - first, first, chosen + [first]))
    return results

Δυναμικός προγραμματισμός: αποδοτική καταμέτρηση

dp[i] = πλήθος τρόπων να γραφτεί το i ως άθροισμα μερών {1,...,part} — χωρίς να παράγουμε καμία λίστα ρητά.

Υπολογιστική επαλήθευση σε κλίμακα

Ελέγχουμε ένα μοτίβο σε εκατοντάδες περιπτώσεις υπολογιστικά, πριν/αντί για αυστηρή απόδειξη.

Σύνοψη

• Βρόχος while, ιδίωμα while True + break
• Δυαδική αναζήτηση: ~log₂(n) βήματα, μισό διάστημα κάθε φορά
• Naive παραγωγή με ρητή στοίβα (προσομοίωση αναδρομής)
• Δυναμικός προγραμματισμός: πίνακας dp για αποδοτική καταμέτρηση
• Υπολογιστική επαλήθευση ενός μοτίβου σε μεγάλη κλίμακα

⤺ Πλήρεις σημειώσεις  ·  Πρόγραμμα μαθήματος