Συγχώνευση με Ταξινόμηση και μοναδικότητα στοιχείων σ

[olga_ath]

Καλησπέρα

Διάβασα το thread για την συγχώνευση πινάκων https://alkisg.mysch.gr/steki/index.php?topic=1147.0 και κράτησα το εξής σημείο όπου και θα ήθελα την γνώμη σας.
Στην περίπτωση που η εκφώνηση ζητά να περιέχονται στον τελικό πίνακα όλα τα στοιχεία από μια φορά αυτο σημαίνει ότι τα διπλά δεν πρέπει να δημιουργηθούν εξαρχής ή μπορούμε μόλις δημιουργήσουμε τον πίνακα να εξαλοίψουμε τα διπλά;

Στην πρώτη περίπτωση (δλδ που ο αλγόριθμος της συγχώνευσης δεν αφήνει να προστεθεί ένα διπλό στοιχείο στον τελικά πίνακα) τι τροποποιήσεις πρέπει να κάνουμε στον αλγόριθμο;

ευχαριστώ εκ των προτέρων

[Sergio]

Καλησπέρα

Στην περίπτωση που η εκφώνηση ζητά να περιέχονται στον τελικό πίνακα όλα τα στοιχεία από μια φορά αυτο σημαίνει ότι τα διπλά δεν πρέπει να δημιουργηθούν εξαρχής ή μπορούμε μόλις δημιουργήσουμε τον πίνακα να εξαλοίψουμε τα διπλά;

Στην πρώτη περίπτωση (δλδ που ο αλγόριθμος της συγχώνευσης δεν αφήνει να προστεθεί ένα διπλό στοιχείο στον τελικά πίνακα) τι τροποποιήσεις πρέπει να κάνουμε στον αλγόριθμο;

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

ΑΝ Α[I] < Β[J] ΤΟΤΕ
   Γ[Κ] <- Α[I]
   I <- I + 1
ΑΛΛΙΩΣ_ΑΝ Β[J] < Α[I] ΤΟΤΕ
   Γ[Κ] <- Β[J]
   J <- J + 1
ΑΛΛΙΩΣ
   Γ[Κ] <- Α[I]     ! ή Γ[Κ] <- Β[J]
   I <- I + 1
   J <- J + 1
ΤΕΛΟΣ_ΑΝ
Κ <- Κ + 1

Λίγο βιαστικά απαντώντας, νομίζω ότι αυτό αρκεί..

Βέβαια, η παραπάνω λύση δεν καλύπτει την περίπτωση που κάποιος πίνακας έχει την ίδια τιμή σε περισσότερες από μία θέσεις

[olga_ath]

ευχαριστώ πολύ για την απάντηση !!!
Στην περίπτωση που κπ από τα στοιχεία υπάρχει φορές >2 τότε δοκίμασα να τρέξω αυτό τον αλγόριθμο-τέρας. Αν κπ έχει κπ συντομότερη-εξυπνότερη λύση θα ήθελα πολύ να την ακούσω γιατί και εγώ η ίδια που το έγραψα μπερδεύομαι πόσο μάλλον να το εξηγήσω αυτό στα παιδιά....

Αλγόριθμος Τεστ
Α[1]← 1
Α[2]← 2
Α[3]← 2
Α[4]← 3
Β[1]← 2
Β[2]← 3
Β[3]← 4
Ι← 1
J← 1
K← 1
ΟΣΟ Ι<=4 και J <=3 επανάλαβε
ΑΝ Α[Ι] < Β[J] ΤΟΤΕ
    Αν K > 1  τότε
      Αν Γ[K-1] <>  Α[Ι] τότε
      
              Γ[K] ←  Α[Ι]
         		K ←  K + 1
      Τέλος_αν
	Αλλιώς 
		Γ[K] ←  Α[Ι]
        K ←  K + 1
   Τέλος_αν
       Ι ←  Ι + 1
ΑΛΛΙΩΣ_ΑΝ Β[J] < Α[Ι] ΤΟΤΕ
   Αν K>1  τότε
      Αν Γ[K-1] <> Β[J]  τότε
              Γ[K] ←  Β[J]
              K ←  K + 1
      Τέλος_αν
	Αλλιώς
		Γ[K] ←  Β[J]
        K ←  K + 1
   Τέλος_αν
   J ←  J + 1
ΑΛΛΙΩΣ
  Αν K>1 τότε
      Αν Γ[K-1] <>  Α[Ι] τότε
      Γ[K] ←  Α[Ι]
      K ←  K + 1
      Τέλος_αν
	Αλλιώς
		Γ[K] ←  Α[Ι]
    	K ←  K + 1
	Τέλος_αν     
   Ι ←  Ι + 1
   J ←  J + 1
ΤΕΛΟΣ_ΑΝ
Τέλος_Επανάληψης
Γράψε "ΤΟ Κ ειναι ", K
Αν Ι >4 τότε
   Για λ από J μέχρι 3
      	Αν K>1  τότε
			Αν Γ[K-1] <>  Β[λ] τότε
         		Γ[K] ←  Β[λ]
      			K ←  K + 1
      		Τέλος_αν 
		Αλλιώς
  			Γ[K] ←  Β[λ]
      		K ←  K + 1
		Τέλος_αν
   Τέλος_Επαναληψης

Αλλιώς_αν J>3 τότε
   Για λ από Ι μέχρι 4
      Αν K>1  τότε
			Αν Γ[K-1] <>  Α[λ] τότε
         		Γ[K] ←  Α[λ]
      			K ←  K + 1
      		Τέλος_αν 
		Αλλιώς
  			Γ[K] ←  Α[λ]
      		K ←  K + 1
		Τέλος_αν 
   Τέλος_Επαναληψης
Τέλος_Αν
γράψε "Το Κ είναι ", K
Για ι από 1 μέχρι K -1 ! το μειώνω επειδή στην τελευταία επανάληψη πάνω αυξήθηκε αλλά μετά δεν προσέθεσα στοιχείο
	Γράψε Γ[ι]
Τέλος_Επανάληψης
Τέλος Τεστ

[Sergio]

..ιδέα έιναι ότι προσθέτουμε στον πίνακα Γ αν ελέγξουμε ότι δεν είναι ίδιο με το προηγούμενο..

Πολύ καλή ιδέα.  Μόνο που ο (σωστός) έλεγχος «..ΑΝ Κ > 1..» που επαναλαμβάνεται σε όλα τα σημεία, κάνει τον κώδικα λίγο περίπλοκο.

Μία λίγο διαφορετική υλοποίηση, βασισμένη κατά κύριο λόγο στη λογική που προτείνεις, θα μπορούσε να βασίζεται στη χρήση μιας βοηθητικής μεταβλητής (έστω.. ουρά) που θα φυλάει την τιμή που έχει εισαχθεί τελευταία, την τιμή δηλαδή που βρίσκεται στην 'ουρά' του νέου πίνακα.  Η λογική της δομής επιλογής που χρησιμοποιείται (τόσο στο πρώτο, όσο και στο δεύτερο μέρος του αλγόριθμου), μπορεί επιπλέον να απλουστευτεί με τη χρήση μιας επιπλέον βοηθητικής μεταβλητής (έστω.. τιμή) που θα φυλάει την τιμή που .. προσπαθεί να εισαχθεί.  Το αν θα εισαχθεί ή όχι, εξαρτάται από το αν είναι διαφορετική από την τιμή της 'ουράς' (η ιδέα που διατύπωσες ουσιαστικά).

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

ΑΝ Α[I] < Β[J] ΤΟΤΕ
   τιμή <- Α[Ι]
   I <- I + 1
ΑΛΛΙΩΣ_ΑΝ Β[J] < Α[I] ΤΟΤΕ
   τιμή <- Β[J]
   J <- J + 1
ΑΛΛΙΩΣ
   τιμή <- Α[Ι]      ! ή τιμή <- Β[J]
   I <- I + 1
   J <- J + 1
ΤΕΛΟΣ_ΑΝ

ΑΝ τιμή <> ουρά ΤΟΤΕ
   Γ[Κ] <- τιμή
   ουρά <- τιμή
   Κ <- Κ + 1
ΤΕΛΟΣ_ΑΝ

Έτσι αποφεύγουμε και τις πολλές αναφορές σε στοιχεία του πίνακα οπότε ο κώδικας γίνεται 'ταχύτερος'.  Όχι βέβαια ότι αυτό αφορά στο ελάχιστο το μαθητή..

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

Βέβαια υπάρχει το θέμα της απόδοσης αρχικής τιμής στην 'ουρά'.  Αυτό θα πρέπει να γίνει έξω από το βρόχο, αντικαθιστώντας και συμπληρώνοντας κατάλληλα τις εντολές αρχικοποίησης των δεικτών των πινάκων, ως εξής:

AN A[1] < B[1] TOTE
   Γ[1] <- Α[1]
   Ι <- 2
   J <- 1
ΑΛΛΙΩΣ
   Γ[1] <- Β[1]
   Ι <- 1
   J <- 2
ΤΕΛΟΣ_ΑΝ

ΤΕΛ <- Γ[1]

Κ <- 2

Βέβαια, η παραπάνω λύση δεν καλύπτει απόλυτα την περίπτωση που κάποιος πίνακας είναι άδειος ..  Και ίσως να υπάρχουν και άλλα σημεία στα οποία .. μπάζει   Δεν είμαι σίγουρος για τη σκοπιμότητα μιας τέτοιας άσκησης.  Οι περισσότεροι μαθητές προβληματίζονται ήδη αρκετά με την απλή περίπτωση που δίνεται στο τετράδιο μαθητή..

[Sergio]

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

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

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

1) αντιγραφή σε 2 νέους πίνακες, των μοναδικών στοιχείων των αρχικών πινάκων
2) συγχώνευση των δύο νέων πινάκων στον τελικό, αποφεύγοντας τα (μοναδικά) κοινά στοιχεία τους

Το πρώτο, κάνοντας Ν επαναλήψεις για τον πίνακα Α (και αντίστοιχα Μ επαναλήψεις για τον Β), θα μπορούσε εύκολα να κωδικοποιηθεί ως:

ΑΝ Ν > 0 ΤΟΤΕ    ! αν δεν είναι άδειος
   ΑΑ[1] <- Α[1]
   ΝΝ <- 1   ! πάτος νέου πίνακα
ΑΛΛΙΩΣ
   ΝΝ <- 0   ! πάτος νέου πίνακα
ΤΕΛΟΣ_ΑΝ

ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ Ν
   AN A[Ι] <> AA[ΝΝ] ΤΟΤΕ   ! μοναδικό (πρέπει να αντιγραφεί)
      ΝΝ <- ΝΝ + 1
      ΑΑ[ΝΝ] <- Α[I]
   ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Όσο για το δεύτερο, αρκεί πλέον η πρόταση του βιβλίου (όπως παρουσιάστηκε ελαφρά τροποποιημένη σε προηγούμενη απάντηση):

I <- 1   ! επόμενο προς έλεγχο στον ΑΑ
J <- 1   ! επόμενο προς έλεγχο στον ΒΒ
K <- 1   ! επόμενη κενή θέση στον Γ
ΟΣΟ I <= N ΚΑΙ J <= M ΕΠΑΝΑΛΑΒΕ
   ΑΝ ΑΑ[Ι] < ΒΒ[J] ΤΟΤΕ
      Γ[Κ] <- ΑΑ[I]
      I <- I + 1
   ΑΛΛΙΩΣ_ΑΝ ΒΒ[J] < ΑΒ[I] ΤΟΤΕ
      Γ[Κ] <- ΒB[J]
      J <- J + 1
   ΑΛΛΙΩΣ
      Γ[Κ] <- AΑ[I]     ! ή Γ[Κ] <- BΒ[J]
      I <- I + 1
      J <- J + 1
   ΤΕΛΟΣ_ΑΝ
   Κ <- Κ + 1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Κατόπιν, η αντιγραφή των στοιχείων που απέμειναν στον ένα από τους δύο πίνακες μπορεί να γίνει ακριβώς όπως την έχει το βιβλίο, αφού πλέον ο κάθε επιμέρους πίνακας ΔΕΝ έχει διπλές τιμές.

[olga_ath]

Πραγματικά μετα και τις τελευταιες προσθήκες πολύ ωραια διατυπωμένο θέμα (Θα σου έλεγα να το υποβάλλεις ως πιθανον θέμα στην Ομάδα Διαγωνισματων  ) και πολύ ομορφη (αλγοριθμικά) λύση .

[zeus.zeusold]

Αν μπορώ να βοηθήσω με τον παρακάτω αλγόριθμο.
ΠΙΝΑΚΑΣ Α Ν ΘΕΣΩΝ
ΠΙΝΑΚΑΣ Β Μ ΘΕΣΕΩΝ
ΠΙΝΑΚΑΣ Γ Ν+Μ ΘΕΣΕΩΝ
Με το Ι διατρέχουμε τον πίνακα Α
Με το J διατρέχουμε τον πίνακα B
Στον πίνακα Γ εκχωρούμε το  ΜΙΝ
ΟΙ ΠΙΝΑΚΕΣ ΕΙΝΑΙ ΤΑΞΙΝΟΜΗΜΕΝΟΙ ΚΑΤΑ ΑΥΞΟΥΣΑ ΣΕΙΡΑ
zeus.zeusold@gmail.com
Ι< -- 1
J< -- 1
ΓΙΑ Κ ΑΠΟ 1 ΜΕΧΡΙ Ν+Μ
     ΑΝ I> N TOTE
           MIN< -- B[J]
           J<-- J+1
     ΑΛΛΙΩΣ_ΑΝ J>M TOTE
           MIN< -- A
           I< --I+1
     ΑΛΛΙΩΣ_ΑΝ A[Ι]<B[J] ΤΟΤΕ
           ΜΙΝ <-- Α
           I< --I+1
     ΑΛΛΙΩΣ
           ΜΙΝ<-- Β[J]
           J <-- J+1
      ΤΕΛΟΣ_ΑΝ
      Γ[Κ]<-- ΜΙΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ