Δίνονται δύο ταξινομημένοι κατά αύξουσα σειρά μονοδιάστατοι πίνακες, ακεραίων αριθμών. Να γραφθει πρόγραμμα το οποίο να συγχωνεύει τους δύο πίνακες σε ένα τρίτο ο οποίος να είναι επίσης ταξινομημένος κατα αύξουσα σειρά. Οι δύο αρχικοί πίνακες δεν μπορούν να περιέχουν περισσότερα απο 100 στοιχεία ο καθένας.
Παράθεση:
Η συγχώνευση είναι μια βασική λειτουργία των πινάκων και γενικότερα των δομών δεδομένων. Στην συνέχεια δίνεται ένας απλος αλγόριθμος συγχώνευσης δυο ταξινομημένων πινάκων σε ενα τρίτο ταξινομοιμένο πίνακα.
Θεώρείτε οτι στην είσοδο του αλγορίθμου συγχωνευσης δίνονται δυο ταξινομοιμένοι, κατα αύξξουσα σειρά πίνακες, πίνακες Α και Β, μεγέθους Ν και Μ στοιχείων αντίστοιχα, ενώ στην έξοδο προκύπτει ένα τρίτος πίνακας Γ με Ν + Μ ταξινομοιμένα στοιχεία επίσης κατά αύξουσα σειρά.
Στο πρόγραμμα "Συγχώνευση" οι μεταβλητές i, j και k είναι δείκτες για την κίνηση μέσα στους πίνακες Α,Β και Γ. Η μέθοδος πηγένει ώς εξής:
" Το μικρότερο στοιχείο απο τους πίνακες Α & Β τοποθετήτε στον πίνακα Γ με ταυτόχρονη αύξηση του αντίστοιχου δείκτη (k). Η διαδικασία αυτή επαναλαμβάνεται μέχρις ότου τελιώσουν τα στοιχεία ενος πίνακα.
Στην συνέχεια τα υπολοιπα στοιχεία του άλλου πίνακα μεταφέρονται στον πίνακα Γ.
ΠΡΟΓΡΑΜΜΑ Συγχώνευση
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[100], Β[100], Γ[100], i, j, k, Ν, Μ, Λ
! Α και Β αρχικοί πίνακες, Γ τελικός συγχωνευμένος πίνακας
ΑΡΧΗ
!Διαβάζουμε τα δεδομένα
ΓΡΑΨΕ ' ΔΩΣΤΕ ΤΟ ΠΛΗΘΟΣ ΤΩΝ ΣΤΟΙΧΕΙΩΝ ΤΟΥ ΠΙΝΑΚΑ Α (<100)'
ΔΙΑΒΑΣΕ Ν
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
ΔΙΑΒΑΣΕ Α[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'ΔΩΣΤΕ ΤΟ ΠΛΗΘΟΣ ΤΩΝ ΣΤΟΙΧΕΙΩΝ ΤΟΥ ΠΙΝΑΚΑ Β(<100)'
ΔΙΑΒΑΣΕ Μ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Μ
ΔΙΑΒΑΣΕ Β[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! Συγχώνευση πινάκων
! i είναι ο δείκτης για τον πίνακα Α
! j είναι ο δείκτης για τον πίνακα Β
! k είναι ο δείκτης για τον πίνακα Γ
i <-- 1
j <-- 1
k <-- 1
ΟΣΟ i <= Ν ΚΑΙ j <= Μ ΕΠΑΝΑΛΑΒΕ
! Όσο και τα δύο έχουν στοιχεία
ΑΝ Α[i] < Β[j] ΤΟΤΕ
Γ[k] <-- Α[i]
k <-- k +1
i <-- i +1
ΑΛΛΙΩΣ
Γ[k] <-- Β[j]
k <-- k +1
j <-- j +1
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!Μεταφορά των υπολοιπων στοιχείων του Α ή του Β
ΑΝ i > Ν ΤΟΤΕ
ΓΙΑ Λ ΑΠΟ Κ ΜΕΧΡΙ Ν+Μ
Γ[Λ] <-- Β[j]
j <-- j +1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ
ΓΙΑ Λ ΑΠΟ Κ ΜΕΧΡΙ Ν+Μ
Γ[Λ] <--Α[i]
i <-- i +1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΑΝ
!Εκτύπωση τελικού πίνακα
ΓΙΑ Λ ΑΠΟ 1 ΜΕΧΡΙ Ν+Μ
ΓΡΑΨΕ Γ[Λ]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
ΚΑΛΗ ΕΠΙΤΥΧΙΑ ΣΤΟΥΣ ΜΑΘΗΤΕΣ ΠΟΥ ΔΕΊΝΟΥΝ ΦΕΤΟΣ ΠΑΝΝΕΛΗΝΙΕΣ, ΚΑΙ ΝΑ ΔΙΑΒΑΖΕΤΕ ΤΗΝ ΑΣΚΗΣΗ ΠΡΩΤΑ ΚΑΛΑ, ΝΑ ΤΗΝ ΑΝΑΛΥΕΤΕ ΣΕ ΚΟΜΜΑΤΙΑ ΚΑΙ ΣΤΟ ΤΕΛΟΣ ΝΑ ΤΑ ΕΝΝΟΝΕΤΕ ΟΠΩΣ ΠΡΕΠΕΙ.ΑΜΑ ΘΕΛΕΤΕ ΚΑΠΟΙΑ ΒΟΗΘΕΙΑ Η΄ ΕΞΗΓΗΣΗ ΚΑΠΟΙΑ ΑΣΚΗΣΗΣ ΑΠΛΑ ΣΤΕΙΛΤΕ ΤΗΝ!