Τυπικές επεξεργασίες πινάκων
Κεφ. 9 §9.4 · Αθροίσματα, μέγιστο/ελάχιστο, αναζήτηση, ταξινόμηση, συγχώνευση
Το Θέμα Δ είναι σχεδόν πάντα ένα πρόβλημα με πίνακες: σύνολα ανά γραμμή, το κατάστημα με τις περισσότερες πωλήσεις, ταξινόμηση, αναζήτηση. Οι επεξεργασίες είναι λίγες και επαναλαμβάνονται — αν τις ξέρεις σαν «έτοιμα κομμάτια», συναρμολογείς τη λύση γρήγορα και σωστά.
Αθροίσματα σε δισδιάστατο πίνακα
Για πίνακα Π[Ν, Μ]:
Άθροισμα κάθε γραμμής (ο αθροιστής μηδενίζεται για κάθε γραμμή):
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν Σ ← 0 ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ Μ Σ ← Σ + Π[i, j] ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΣΓ[i] ← Σ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Άθροισμα κάθε στήλης: αντιστρέφεις τους βρόχους — εξωτερικό το j, εσωτερικό το i — και αποθηκεύεις στο ΣΣ[j].
Συνολικό άθροισμα: ένας αθροιστής, μηδενισμένος μία φορά πριν από τους δύο βρόχους.
Μέγιστο και ελάχιστο
Αρχική τιμή του μέγιστου είναι το πρώτο στοιχείο· κρατάμε και τη θέση του, αν ζητείται:
μεγ ← Α[1] θμεγ ← 1 ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν ΑΝ Α[i] > μεγ ΤΟΤΕ μεγ ← Α[i] θμεγ ← i ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Με > βρίσκεις την πρώτη θέση του μέγιστου· με >= την τελευταία. Αν ζητούνται όλες οι θέσεις με τη μέγιστη τιμή, χρειάζεται δεύτερο πέρασμα: πρώτα βρίσκεις το μέγιστο και μετά εμφανίζεις κάθε i με Α[i] = μεγ.
Η σειριακή αναζήτηση και η ταξινόμηση ευθείας ανταλλαγής σε ΓΛΩΣΣΑ παρουσιάζονται αναλυτικά στην αναζήτηση και ταξινόμηση και η δυαδική αναζήτηση στις τεχνικές σχεδίασης.
Ο πίνακας Α έχει τα στοιχεία [4, 9, 2, 9, 7]. Τι εμφανίζεται;
θ ← 1 ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 5 ΑΝ Α[i] >= Α[θ] ΤΟΤΕ θ ← i ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ θ
Συγχώνευση ταξινομημένων πινάκων
Δύο πίνακες ταξινομημένοι σε αύξουσα σειρά, Α[Ν] και Β[Μ], συγχωνεύονται σε έναν ταξινομημένο Γ[Ν + Μ]: σε κάθε βήμα συγκρίνουμε τα «τρέχοντα» στοιχεία των δύο και μεταφέρουμε το μικρότερο. Όταν τελειώσει ο ένας πίνακας, αντιγράφουμε τα υπόλοιπα στοιχεία του άλλου.
i ← 1 j ← 1 k ← 0 ΟΣΟ i <= Ν ΚΑΙ j <= Μ ΕΠΑΝΑΛΑΒΕ k ← k + 1 ΑΝ Α[i] <= Β[j] ΤΟΤΕ Γ[k] ← Α[i] i ← i + 1 ΑΛΛΙΩΣ Γ[k] ← Β[j] j ← j + 1 ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΟΣΟ i <= Ν ΕΠΑΝΑΛΑΒΕ k ← k + 1 Γ[k] ← Α[i] i ← i + 1 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΟΣΟ j <= Μ ΕΠΑΝΑΛΑΒΕ k ← k + 1 Γ[k] ← Β[j] j ← j + 1 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Από τα δύο τελευταία ΟΣΟ εκτελείται μόνο εκείνο του πίνακα που δεν έχει εξαντληθεί.
Παράδειγμα 1: Ίχνος συγχώνευσης για Α = [2, 5, 9] και Β = [3, 4, 10, 12].
- 2 <= 3 → Γ[1] = 2 (i = 2)
- 5 <= 3 ψευδές → Γ[2] = 3 (j = 2)
- 5 <= 4 ψευδές → Γ[3] = 4 (j = 3)
- 5 <= 10 → Γ[4] = 5 (i = 3)
- 9 <= 10 → Γ[5] = 9 (i = 4, ο Α εξαντλήθηκε)
- αντιγραφή υπολοίπων του Β: Γ[6] = 10, Γ[7] = 12
Γ = [2, 3, 4, 5, 9, 10, 12], με 5 συγκρίσεις ().
Κατά τη συγχώνευση των ταξινομημένων Α = [1, 3, 5] και Β = [2, 4, 6, 8, 10], πόσα στοιχεία αντιγράφονται στο τελευταίο τμήμα (μετά την κύρια επανάληψη);
Μέθοδος: επιλογή επεξεργασίας σε Θέμα Δ
- «Σύνολο/μέσος όρος ανά γραμμή ή στήλη» → αθροιστής μέσα στον εξωτερικό βρόχο, αποτέλεσμα σε βοηθητικό πίνακα.
- «Ποιο/ποια έχει το μέγιστο» → πρώτα τα σύνολα, μετά μέγιστο με θέση στον βοηθητικό πίνακα· το όνομα βγαίνει από τον παράλληλο πίνακα ονομάτων στην ίδια θέση.
- «Όλα όσα έχουν το μέγιστο» → δύο περάσματα.
- «Να εμφανιστούν ταξινομημένα» → φυσαλίδα, αντιμεταθέτοντας και τους παράλληλους πίνακες.
- «Υπάρχει; σε ποια θέση;» → σειριακή αναζήτηση (ή δυαδική αν είναι ταξινομημένος).
Θέμα τύπου Πανελλαδικών: Ο πίνακας ΠΩΛ[5, 12] περιέχει τις πωλήσεις 5 καταστημάτων (γραμμές) για τους 12 μήνες (στήλες) και ο πίνακας ΚΑΤ[5] τα ονόματα των καταστημάτων. Να γραφεί τμήμα που (α) υπολογίζει τις ετήσιες πωλήσεις κάθε καταστήματος, (β) εμφανίζει το όνομα του καταστήματος με τις μεγαλύτερες ετήσιες πωλήσεις (θεωρούμε μοναδικό) και (γ) εμφανίζει τον μήνα με τις μεγαλύτερες συνολικές πωλήσεις όλων των καταστημάτων (θεωρούμε μοναδικό).
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 5 ΕΤ[i] ← 0 ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ 12 ΕΤ[i] ← ΕΤ[i] + ΠΩΛ[i, j] ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ θ ← 1 ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 5 ΑΝ ΕΤ[i] > ΕΤ[θ] ΤΟΤΕ θ ← i ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ 'Κορυφαίο κατάστημα: ', ΚΑΤ[θ] ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ 12 ΜΗΝ[j] ← 0 ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 5 ΜΗΝ[j] ← ΜΗΝ[j] + ΠΩΛ[i, j] ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ μ ← 1 ΓΙΑ j ΑΠΟ 2 ΜΕΧΡΙ 12 ΑΝ ΜΗΝ[j] > ΜΗΝ[μ] ΤΟΤΕ μ ← j ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ 'Καλύτερος μήνας: ', μ
Τα ΕΤ[5] και ΜΗΝ[12] είναι βοηθητικοί πίνακες (αθροίσματα γραμμών και στηλών). Κρατώντας μόνο τη θέση του μέγιστου, έχουμε και την τιμή (ΕΤ[θ]) και το όνομα (ΚΑΤ[θ]).
Παράδειγμα 2: Ο πίνακας ΒΑΘ[30] περιέχει βαθμούς και ο ΟΝ[30] τα ονόματα. Να εμφανιστούν όλοι οι μαθητές με τον μεγαλύτερο βαθμό.
μεγ ← ΒΑΘ[1] ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 30 ΑΝ ΒΑΘ[i] > μεγ ΤΟΤΕ μεγ ← ΒΑΘ[i] ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 30 ΑΝ ΒΑΘ[i] = μεγ ΤΟΤΕ ΓΡΑΨΕ ΟΝ[i] ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Στο πρώτο πέρασμα δεν ξέρουμε ακόμη ποιο είναι το μέγιστο, άρα δεν μπορούμε να εμφανίσουμε ονόματα· γι' αυτό χρειάζεται δεύτερο πέρασμα με σύγκριση ισότητας.
Ποιο είναι το λάθος στο τμήμα που υπολογίζει το άθροισμα κάθε γραμμής του Π[4, 6];
Σ ← 0 ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 4 ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ 6 Σ ← Σ + Π[i, j] ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ Σ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Η συγχώνευση είναι το «κόλλημα» της ταξινόμησης με συγχώνευση (merge sort): επειδή κάθε σύγκριση μεταφέρει ένα στοιχείο, δύο ταξινομημένοι πίνακες συνολικού μεγέθους ενώνονται με το πολύ συγκρίσεις. Με την ίδια ιδέα οι βάσεις δεδομένων ταξινομούν αρχεία τόσο μεγάλα που δεν χωρούν στη μνήμη: ταξινομούν κομμάτια και μετά τα συγχωνεύουν.
Ο πίνακας Α[Ν] είναι ταξινομημένος σε αύξουσα σειρά και μπορεί να έχει επαναλαμβανόμενες τιμές. Να γραφεί τμήμα που αντιγράφει στον πίνακα Β τις διαφορετικές τιμές του Α (από μία φορά την καθεμία) και εμφανίζει πόσες είναι — με ένα πέρασμα.
Δοκίμασε πρώτα μόνος σου — μετά δες τη λύση
Αφού ο Α είναι ταξινομημένος, οι ίσες τιμές είναι γειτονικές: αρκεί να συγκρίνουμε κάθε στοιχείο με το προηγούμενο.
κ ← 1 Β[1] ← Α[1] ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν ΑΝ Α[i] <> Α[i - 1] ΤΟΤΕ κ ← κ + 1 Β[κ] ← Α[i] ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΡΑΨΕ κ
Για Α = [2, 2, 5, 7, 7, 7, 9]: Β = [2, 5, 7, 9] και εμφανίζεται 4. Σε μη ταξινομημένο πίνακα θα έπρεπε κάθε στοιχείο να αναζητηθεί σε όλο τον Β — γι' αυτό συχνά συμφέρει να ταξινομήσεις πρώτα.
- Αθροιστής γραμμής μηδενισμένος έξω από τον εξωτερικό βρόχο: κάθε γραμμή «κουβαλάει» το σύνολο των προηγούμενων.
- Για αθροίσματα στηλών κρατάς εξωτερικό το i: ο αθροιστής μηδενίζεται ανά γραμμή και βγαίνουν αθροίσματα γραμμών. Για στήλες, εξωτερικό πρέπει να είναι το j.
- Στη συγχώνευση ξεχνάς να αντιγράψεις τα υπόλοιπα στοιχεία του πίνακα που δεν εξαντλήθηκε.
- Εύρεση ονόματος του μέγιστου χωρίς θέση: κράτα τη θέση και διάβασε το όνομα από τον παράλληλο πίνακα.
- Αθροίσματα γραμμών: εξωτερικό i, αθροιστής μηδενίζεται για κάθε i· στηλών: εξωτερικό j.
- Μέγιστο/ελάχιστο: αρχική τιμή το πρώτο στοιχείο, κράτα και τη θέση· > δίνει πρώτη, >= τελευταία εμφάνιση.
- Όλες οι θέσεις του μέγιστου: δύο περάσματα.
- Συγχώνευση: μεταφορά του μικρότερου από τα τρέχοντα στοιχεία, μετά τα υπόλοιπα του μη εξαντλημένου πίνακα.
- Παράλληλοι πίνακες: ίδια θέση = ίδια οντότητα (όνομα – βαθμός – πωλήσεις).