2019, ΒΑΣΙΚΕΣ ΕΝΝΟΙΕΣ, ΕΠΑΝΑΛΗΠΤΙΚΕΣ, ΕΣΠΕΡΙΝΑ, ΗΜΕΡΗΣΙΑ, ΠΙΝΑΚΑΣ ΜΕΤΑΒΛΗΤΩΝ, ΠΙΝΑΚΕΣ, ΥΠΟΠΡΟΓΡΑΜΜΑΤΑ
ΘΕΜΑ B1
Β1. Ένας πίνακας λέγεται αραιός (sparse) αν ένα μεγάλο ποσοστό των στοιχείων του έχουν μηδενική τιμή. Ένας δισδιάστατος αραιός πίνακας μπορεί να αναπαρασταθεί από έναν μονοδιάστατο όπου κάθε μη μηδενικό στοιχείο του δισδιάστατου αντιπροσωπεύεται στον μονοδιάστατο από μία τριάδα στοιχείων, δηλαδή <γραμμή, στήλη, τιμή>. Για παράδειγμα, ο παρακάτω πίνακας Α [4,5] που θέλουμε να τον διαχειριστούμε ως αραιό
| 0 |
7 |
0 |
0 |
0 |
| 1 |
2 |
0 |
0 |
-3 |
| 0 |
0 |
4 |
0 |
0 |
| 0 |
0 |
0 |
0 |
0 |
αντιπροσωπεύεται από τον μονοδιάστατο Β[15].
| 1 |
2 |
7 |
2 |
1 |
1 |
2 |
2 |
2 |
2 |
5 |
-3 |
3 |
3 |
4 |
Η αντίστροφη διαδικασία είναι από τον μονοδιάστατο πίνακα να παραχθεί ένας ισοδύναμος αραιός δισδιάστατος.
Έστω ένας πίνακας Μ[18] που αναπαριστά 6 μη μηδενικά στοιχεία. Δίνεται ο παρακάτω αλγόριθμος, ο οποίος από τον μονοδιάστατο Μ[18] δημιουργεί τον αραιό δισδιάστατο Δ[10,20].
Αλγόριθμος αντίστροφος
Δεδομένα // Μ //
Για i από 1 μέχρι 20
Για j από 1 μέχρι 10
Δ[…(1), … (2)] <- 0
Τέλος_επανάληψης
Τέλος_επανάληψης
Για i από 1 μέχρι 18 με_βήμα … (3)
α <- Μ[i]
β <- Μ[i + … (4)]
γ <- Μ[i + … (5)]
Δ[α, β] <- γ
Τέλος_επανάληψης
Αποτελέσματα // Δ //
Τέλος αντίστροφος </code class="language-javascript">
Ο παραπάνω αλγόριθμος έχει 5 κενά αριθμημένα από (1)μέχρι (5). Για καθένα από τα κενά, να γράψετε στο τετράδιό σας τον αριθμό του και ό,τι χρειάζεται να συμπληρωθεί για να λειτουργήσει σωστά ο αλγόριθμος.
Μονάδες 10
2018, Α ΘΕΜΑ, ΕΠΑΝΑΛΗΠΤΙΚΕΣ, ΕΣΠΕΡΙΝΑ, ΗΜΕΡΗΣΙΑ, ΠΙΝΑΚΕΣ, ΣΥΜΠΛΗΡΩΣΗΣ
Α4. Ο παρακάτω αλγόριθμος αντιγράφει τα στοιχεία ενός μονοδιάστατου πίνακα Α[Y], όπου Υ=Μ*N, σε δισδιάστατο πίνακα Β[Μ,Ν] ξεκινώντας από την πρώτη στήλη και συνεχίζοντας με κάθε επόμενη στήλη γεμίζοντας καθεμιά από πάνω προς τα κάτω:
Αλγόριθμος Αντιγραφή
Δεδομένα // Α,Μ,Ν //
χ…(1)…
Για κ από 1 μέχρι …(2)...
Για λ από 1 μέχρι …(3)…
χ…(4)…
Β[λ,κ] Α[…(5)…]
Τέλος_Επανάληψης
Τέλος_Επανάληψης
Αποτελέσματα // Β //
Τέλος Αντιγραφή </code class="language-javascript">
Ο αλγόριθμος περιέχει αριθμημένα κενά (1 έως 5). Να γράψετε στο τετράδιό σας τους αριθμούς των κενών και δίπλα από κάθε αριθμό την έκφραση που πρέπει να συμπληρωθεί ώστε ο αλγόριθμος να επιτελεί τη λειτουργία που περιγράφεται.
Μονάδες 10
ΤΑΞΙΝΟΜΗΣΗ
Η Ταξινόμηση ενός διδιάστατου πίνακα συνολικά μπορεί να γίνει με την μετατροπή του σε μονοδιάστατο, ταξινόμηση του τελευταίου με φυσαλίδα (bubble sort) και επανασύνθεση του διδιάστατου.
Αν έχουμε τον περιορισμό της χρήσης βοηθητικού πίνακα, μπορούμε να χρησιμοποιήσουμε την ταξινόμηση επιλογής.
Ακολουθεί η ταξινόμηση επιλογής για μονοδιάστατο πίνακα, πρόγραμμα μετατροπής σειράς σε συντεταγμένες και με την βοήθεια του, η ταξινόμηση επιλογής για διδιάστατο πίνακα.
ΠΡΟΓΡΑΜΜΑ SELECTION_SORT_MONODIASTATOS
ΣΤΑΘΕΡΕΣ
Μ = 3
Ν = 3
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[Μ*Ν], Κ, Θ, Ι
ΑΡΧΗ
Α[1] <- 10
Α[2] <- 7
Α[3] <- 1
Α[4] <- 9
Α[5] <- 2
Α[6] <- 4
Α[7] <- 5
Α[8] <- 8
Α[9] <- 3
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Μ*Ν
ΓΡΑΨΕ Α[Ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ Κ ΑΠΟ 1 ΜΕΧΡΙ (Μ*Ν) - 1
Θ <- Κ
ΓΙΑ Ι ΑΠΟ Κ + 1 ΜΕΧΡΙ Μ*Ν
ΑΝ Α[Ι] < Α[Θ] ΤΟΤΕ
Θ <- Ι
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΚΑΛΕΣΕ ΑΝΤΙΜΕΤΑΘΕΣΗ(Α[Κ], Α[Θ])
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ '***'
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Μ*Ν
ΓΡΑΨΕ Α[Ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
ΔΙΑΔΙΚΑΣΙΑ ΑΝΤΙΜΕΤΑΘΕΣΗ(Α, Β)
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α, Β, TEMP
ΑΡΧΗ
TEMP <- Α
Α <- Β
Β <- TEMP
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ</code class="language-javascript">
Για την εφαρμογή της Selection Sort (Ταξινόμηση Επιλογής σε διδιάστατο πίνακα θα χρειαστούμε μια διαδικασία μετατροπής της σειράς αριθμών σε συντεταγμένες του διδιάστατου πίνακα.
ΠΡΟΓΡΑΜΜΑ ΣΥΝΤΕΤΑΓΜΕΝΕΣ
ΣΤΑΘΕΡΕΣ
Μ = 3
Ν = 3
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[Μ, Ν], Λ, Γ, Σ
ΑΡΧΗ
Α[1, 1] <- 10
Α[1, 2] <- 7
Α[1, 3] <- 1
Α[2, 1] <- 9
Α[2, 2] <- 2
Α[2, 3] <- 4
Α[3, 1] <- 5
Α[3, 2] <- 8
Α[3, 3] <- 3
ΓΙΑ Λ ΑΠΟ 1 ΜΕΧΡΙ Μ*Ν
ΓΡΑΨΕ Λ
ΑΝ Λ mod Ν = 0 ΤΟΤΕ
ΑΝ Λ div Ν = 0 ΤΟΤΕ
Γ <- 1
Σ <- Ν
ΑΛΛΙΩΣ
Γ <- Λ div Ν
Σ <- Ν
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ
ΑΝ Λ div Ν = 0 ΤΟΤΕ
Γ <- 1
Σ <- Λ mod Ν
ΑΛΛΙΩΣ
Γ <- 1 + Λ div Ν
Σ <- Λ mod Ν
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
ΓΡΑΨΕ "Α[", Γ, ", ", Σ, "] = ", Α[Γ, Σ]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ</code class="language-javascript">
Συνδυάζοντας τους 2 αλγορίθμους, προκύπτει η selection sort για διδιάστατο πίνακα.
ΠΡΟΓΡΑΜΜΑ SELECTION_SORT_2ΔΙΑΣΤΑΤΟΣ
ΣΤΑΘΕΡΕΣ
Μ = 3
Ν = 3
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[Μ, Ν], Κ, Θ, Ι, J, Γ1, Σ1, Γ2, Σ2
ΑΡΧΗ
Α[1, 1] <- 10
Α[1, 2] <- 7
Α[1, 3] <- 1
Α[2, 1] <- 9
Α[2, 2] <- 2
Α[2, 3] <- 4
Α[3, 1] <- 5
Α[3, 2] <- 8
Α[3, 3] <- 3
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Μ
ΓΙΑ J ΑΠΟ 1 ΜΕΧΡΙ Ν
ΓΡΑΨΕ Α[Ι, J]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ Κ ΑΠΟ 1 ΜΕΧΡΙ (Μ*Ν) - 1
Θ <- Κ
ΓΙΑ Ι ΑΠΟ Κ + 1 ΜΕΧΡΙ Μ*Ν
ΚΑΛΕΣΕ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Ι, Γ2, Σ2)
ΚΑΛΕΣΕ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Θ, Γ1, Σ1)
ΑΝ Α[Γ2, Σ2] > Α[Γ1, Σ1] ΤΟΤΕ
Θ <- Ι
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΚΑΛΕΣΕ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Κ, Γ1, Σ1)
ΚΑΛΕΣΕ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Θ, Γ2, Σ2)
ΚΑΛΕΣΕ ΑΝΤΙΜΕΤΑΘΕΣΗ(Α[Γ1, Σ1], Α[Γ2, Σ2])
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ '***'
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Μ
ΓΙΑ J ΑΠΟ 1 ΜΕΧΡΙ Ν
ΓΡΑΨΕ Α[Ι, J]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
ΔΙΑΔΙΚΑΣΙΑ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Λ, Γ, Σ)
ΣΤΑΘΕΡΕΣ
Μ = 3
Ν = 3
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Λ, Γ, Σ
ΑΡΧΗ
ΑΝ Λ mod Ν = 0 ΤΟΤΕ
ΑΝ Λ div Ν = 0 ΤΟΤΕ
Γ <- 1
Σ <- Ν
ΑΛΛΙΩΣ
Γ <- Λ div Ν
Σ <- Ν
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ
ΑΝ Λ div Ν = 0 ΤΟΤΕ
Γ <- 1
Σ <- Λ mod Ν
ΑΛΛΙΩΣ
Γ <- 1 + Λ div Ν
Σ <- Λ mod Ν
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΑΝΤΙΜΕΤΑΘΕΣΗ(Α, Β)
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α, Β, TEMP
ΑΡΧΗ
TEMP <- Α
Α <- Β
Β <- TEMP
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ</code class="language-javascript">
Πρόσφατα σχόλια