Θέμα: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας

[Jammy]

Γεια σας.πλιζ χριαζομαι πολυ βοη8εια!γραφω αεπ κ μ ειπανε οτι επεσε αυτο κ δν εχει κανει ιδεα πως στο καλο λυνετε!ζηταει η ασκηση συγχωνευση 2 μονοδιαστατων πινακων Α,Β με Ν και Μ θεσεις αντιστοιχα αλλα πρεπει ο πινακας Γ που 8α προκυψει να ειναι ταξινομημενος διχως να εχουμε χρησιμοποιησει φυσσαλιδα στους 2 προηγουμενους ξεχωριστα.οσα κ αν προσπα8ησα το φτανω μεχρι ενα σημειο μετα ομως δεν βγαινει η ασκηση.πλιζ μεχρι αυριο στι 3 τ μεσημερι  θελω σωστη απαντηση αν γινεται!!ευχαριστω!!

[Νίκος Αδαμόπουλος]

Εννοείς μάλλον ότι ο Α και Β είναι ήδη ταξινομημένοι και ότι ο Γ πρέπει να είναι ταξινομημένος χωρίς να εφαρμόσουμε φυσαλίδα σ' αυτόν;

Δεν νομίζω να έχει πέσει ακριβώς αυτό... Το πιο σχετικό ήταν το Θέμα 4 στις επαναληπτικές του 2008:
http://dide.ilei.sch.gr/keplinet/education/docs/them_plir_kat_c_hmer_epan_0806.pdf

Τι έχεις κάνει μέχρι τώρα;

[Sergio]

Προσπάθησε να σκεφτείς τι ακριβώς θα έκανες "με το χέρι" σε αντίστοιχη περίπτωση..

Έστω ότι Ν = 5 και:
Α[1] = 'Ανδρέας'
Α[2] = 'Γιώργος'
Α[3] = 'Ζωή'
Α[4] = 'Θωμάς'
Α[5] = 'Νίκος'

ενώ Μ = 4 και:
Β[1] = 'Βαγγέλης'
Β[2] = 'Ηλίας'
Β[3] = 'Όλγα'
Β[4] = 'Σοφία'

Εδώ πρέπει να δουλέψεις ταυτόχρονα σε 3 πίνακες που ΔΕΝ είναι παράλληλοι..

Να συγκρίνεις κάποιο στοιχείο του Α με κάποιο στοιχείο του Β και να βάζεις το μικρότερο σε κάποια θέση του Γ.  Όλα τα "κάποιο" σε αυτή την πρόταση υλοποιούνται με δείκτες.  Προφανώς αυτοί ξεκινάνε όλοι με την τιμή 1.. Το ποιός, και πότε, αυξάνεται εξαρτάται από το αποτέλεσμα της σύγκρισης Α[κάποιος_στον_Α] < Β[κάποιος_στον_Β].  Αν ισχύει, τότε θα βάλεις το περιεχόμενο του Α[κάποιος_στον_Α] στη θέση Γ[κάποια_στον_Γ] και θα "προχωρήσεις" αυτούς τους δύο δείκτες κατά 1.  Αν δεν ισχύει, θα κάνεις το ίδιο αλλά με τους πίνακες Β και Γ αντίστοιχα.

Έτσι θα σου προκύψει ο Πίνακας Γ ως:
Γ[1] = 'Ανδρέας'
Γ[2] = 'Βαγγέλης'
Γ[3] = 'Γιώργος'
Γ[4] = 'Ηλίας'
Γ[5] = 'Ζωή'
Γ[6] = 'Θωμάς'
Γ[7] = 'Νίκος'

Όμως σε αυτό το σημείο, έχεις "τελειώσει" με τον Α.. (με άλλες τιμές, θα μπορούσες να έχεις "τελειώσει" με τον Β.. Πάντως να έχεις τελειώσει ΚΑΙ με τους δύο.. αποκλείεται.. η τελευταία σύγκριση, έχει "αφησει τον .. χαμένο πίσω").  Θα πρέπει λοιπόν να .. αλλάξεις τακτική.  Αφού τελείωσες με τον Α, το μόνο που χρεάζεται να κάνεις, είναι να "αντιγράψεις" στον "πάτο" του Γ ό,τι έμεινε στον Β.  Έτσι θα σου προκύψουν και τα:
Γ[8] = 'Όλγα'
Γ[9] = 'Σοφία'

Δες το.. δεν είναι τόσο δύσκολο όσο νομίζεις !!

[Jammy]

βασικα με ονοματα δεν μπορω  να το καταλαβω.κ γω ετσι το εκανα σε χαρτι  με νουμερα ωστε να υπαρχει κ λογος που 8α ταξινομη8ουν κ σκευτομαι τπτ με για...απο...μεχρι και μεσα να εχει καποια αν...
ελενχοντας min,max κτλ κ να κανει αντιμετα8εση σε αυτα.αλλα δεν ξερω πως να υλοποιησω συτη τη σκεψη στο χαρτι.αν μπορειτε δωστε ενα παραδειγμα σαν ασκηση.τελος δεν πρεπει να εχουμε κανει ταξινομηση στο Α κ Β απο πριν πρεπει να τα φτιαξουμε ετσι ωστε ο Γ να ειναι ηδη ταξινομημενος...τρεχα γυρευε...

[Νίκος Αδαμόπουλος]

Δεν είμαι σίγουρος ότι μιλάμε για την ίδια άσκηση... Είσαι σίγουρος ότι οι Α και Β δεν πρέπει να είναι ταξινομημένοι; Μας δίνεις την ακριβή διατύπωση της άσκησης για να μη μιλάμε στον αέρα;

[Jammy]

ναι βεβαια.
Να  συγχωνευσετε τους πινακας Α και Β  ουτοσωστε να προκυψει ταξινομημενος πινακας Γ διχως να ταξινομησετε κανεναν απτους δυο παραπανω.
αυτο λεει.ειναι εφικτο?οσους ρωτησα το ιδιο μ λενε οτι δεν γινεται..εστω και με αλλους τροπους μπορεις να μου δωσεις καποιες πι8ανες λυσεις?

[Sergio]

Αν η εκφώνηση είναι ακριβώς όπως λες, μία λύση θα ήταν:

1. βρες το μικρότερο από αυτά που έμειναν στον Α (αμαρκάριστα, δες βήμα 4)
2. βρες το μικρότερο από αυτά που έμειναν στον Β (αμαρκάριστα, δες βήμα 4)
3. Βάλε το μικρότερο από τα δύο στον Γ
4. Μαρκάρισε στον Α (ή Β) αυτό που έβαλες στον Γ ώστε να μην ξανασχοληθείς
5. Αν υπάρχουν ακόμα στοιχεία σε έναν από τους 2 αρχικούς, πήγαινε στο βήμα 1

    Στον πίνακα που έμεινε με στοιχεία:
6. βρες το μικρότερο από αυτά που έμειναν
7. Βάλε το στον Γ
8. Μαρκάρισέ το στον αρχικό ώστε να μην ξανασχοληθείς
9. Αν υπάρχουν ακόμα στοιχεία στον αρχικό, πήγαινε στο βήμα 7

Ένα προβληματάκι αφορά στην αρχικοποίηση του min για κάθε ένα από τους πίνακες, σε κάθε νέα σάρωση..  Αρχικά (βήμα 0) θα μπορούσες να βάλεις το μεγαλύτερο από τα δύο Α[1], Β[1].  Όμως, από τη στιγμή που έρθει η σειρά κάποιου από αυτά να μπει στον Γ, πλέον χρειάζεσαι καινούργιο max..  Οπότε, αξίζει ίσως, πριν ξεκινήσεις, να βρεις (βήμα 0) την μέγιστη τιμή για κάθε πίνακα και να την φυλάξεις για να μπορείς να κάνεις την αρχικοποίηση του min σε κάθε νέα σάρωση.

Όσο για το "μαρκάρισμα", θα μπορούσε να χρησιμοποιήσεις έναν παράλληλο πίνακα με λογικές μεταβλητές (έναν Εφυγε_Α[Ν], για τον Α και εναν Εφυγε_Β[Μ] για τον Β).  Αρχικοποιείς όλες τις τιμές σε ΨΕΥΔΗΣ κα, για κάθε στοιχείο που επιλέγεται να μπει στον Γ, δηλώνεις αυτή την επιλογή, σηκώνοντας σημαία "του" (αποδίδοντας την τιμή ΑΛΗΘΗΣ)

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

Είναι μια πρόχειρη ιδέα που μπορείς να δοκιμάσεις..

[Jammy]

ευχαριστω πολυ νομιζω ετσι οντως μπορει να βγει

[Sergio]

ευχαριστω πολυ νομιζω ετσι οντως μπορει να βγει

Ωραία !!  Όταν το κάνεις, αν θες ανέβασέ την και εδώ τη λύση

Καλή συνέχεια

[Jammy]

τελικα οι Α Β ταξινομημενοι ητανε κ μετα τους εβαζες στον Γ ωστε να βγει ταξινομημενος.λα8ος μου την ειχανε πει την εκφωνηση!οποιος το ξερει ας μου γραψει την ασκησουλα εδω!ευχαριστω!το εγραψα τ τεστ κ εκανα διαφορα αλλα 8ελω να συγκρινω να δω αν βγηκε σωστη!

[Jammy]

το μονο που καταφερα να κανω αλλα το δοκιμασα με νουμερα και παρολο π εβγενε πιστευω ειναι λα8ος γιατι πρεπει να εχω κανει χαζομαρα στα i και δν ηξερα πως αλλιως να τα μεταβαλω.δειτε

min<-A[1]
x<-B[ i ]
Για i απο 1 μεχρι Ν+Μ
  Αν min < x τοτε
   min<-A[ i+1 ]
   x<-B[ i ]
  αλλιως
   Γ<-B[ i ]
  Τελος_αν

μεσω αυτου προσπα8ησα να πετυχω να παραμεινει στασημος ο Β αν ειναι μικροτερο το νουμερο απτο Α και να παω στο επομενο κουτι του Α.αλλα δεν ξερω αν οντως γεμιζει ολες τις 8εσεις Ν+Μ σωστα.στηλτε μου κι εσεις αν εχετε κατι

[Sergio]

Τετράδιο Μαθητή, Κεφάλαιο 9, Παράγραφος 9.3, Παράδειγμα 3, σελ.91-92

Καλό θα ήταν να διαβάσεις προσεκτικά ό,τι υπάρχει σε βιβλίο και τετράδιο μαθητή και να λύσεις ΟΛΕΣ τις ασκήσεις που υπάρχουν εκεί.  Καλύπτει πολλά σημεία που ενδέχεται να σου δημιουργήσουν απορίες και, σε κάποιο βαθμό, δίνει το στίγμα του "σημαντικού".  Συχνά, θέματα εξετάσεων, έχουν βασιστεί σε σημεία του τετραδίου μαθητή. Άλλοτε σε άλυτες, άλλοτε σε λυμένες ασκήσεις του, και άλλοτε σε ερωτήσεις από τα τεστ αυτοαξιολόγησης.

Στους μαθητές μου συμβουλεύω να τα "γλύψουν" αυτά τα δύο..  Και, προσωπικά, στους μαθητές μου της ΠΔΣ, το κάνω με προσωπική "παρέμβαση"

Προτείνω να κάνεις το ίδιο..

Καλή συνέχεια

[Νίκος Αδαμόπουλος]

Τετράδιο μαθητή σε ηλεκτρονική μορφή:
https://alkisg.mysch.gr/steki/index.php?action=dlattach;topic=1436.0;attach=521

[Jammy]

ποπο ευχαριστω πολυ!! οντως τετραδιο μα8ητη δεν εχω αγγιξει αλλα τωρα που μ το ειπατε 8α πιασω να λυνω κ απο εκει!!

[Νίκος Αδαμόπουλος]

Ο αλγόριθμος της συγχώνευσης από το τετράδιο μαθητή σε ψευδογλώσσα (με Δεδομένα και Αποτελέσματα για λόγους συντομίας):

Αλγόριθμος Συγχώνευση
Δεδομένα // Α, Β, Ν, Μ //  ! Ν είναι το πλήθος των στοιχείων του πίνακα Α (<=100) και Μ το πλήθος των στοιχείων του πίνακα Β (<=100)

Ι <- 1
J <- 1
K <- 1
ΟΣΟ Ι <= Ν ΚΑΙ J <= Μ ΕΠΑΝΑΛΑΒΕ
  ΑΝ Α[Ι] < Β[J] ΤΟΤΕ
     Γ[Κ] <- Α[Ι]
     Κ <- Κ+1
     Ι <- Ι+1
  ΑΛΛΙΩΣ
     Γ[Κ] <- Β[J]
     Κ <- Κ+1
     J <- J +1
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΑΝ Ι > Ν ΤΟΤΕ
  ΓΙΑ Λ ΑΠO Κ ΜΕΧΡΙ Ν+Μ
     Γ[Λ] <- Β[J]
     J <- J +1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ
  ΓΙΑ Λ ΑΠO Κ ΜΕΧΡΙ Ν+Μ
     Γ[Λ] <- Α[Ι]
     Ι <- Ι+1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΑΝ

Αποτελέσματα // Γ //
Τέλος Συγχώνευση