Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Μονοδιάστατοι πίνακες => Μήνυμα ξεκίνησε από: Jammy στις 30 Ιαν 2011, 07:18:52 ΜΜ

Τίτλος: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Jammy στις 30 Ιαν 2011, 07:18:52 ΜΜ
Γεια σας.πλιζ χριαζομαι πολυ βοη8εια!γραφω αεπ κ μ ειπανε οτι επεσε αυτο κ δν εχει κανει ιδεα πως στο καλο λυνετε!ζηταει η ασκηση συγχωνευση 2 μονοδιαστατων πινακων Α,Β με Ν και Μ θεσεις αντιστοιχα αλλα πρεπει ο πινακας Γ που 8α προκυψει να ειναι ταξινομημενος διχως να εχουμε χρησιμοποιησει φυσσαλιδα στους 2 προηγουμενους ξεχωριστα.οσα κ αν προσπα8ησα το φτανω μεχρι ενα σημειο μετα ομως δεν βγαινει η ασκηση.πλιζ μεχρι αυριο στι 3 τ μεσημερι  θελω σωστη απαντηση αν γινεται!!ευχαριστω!! ::)
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Νίκος Αδαμόπουλος στις 30 Ιαν 2011, 07:44:12 ΜΜ
Εννοείς μάλλον ότι ο Α και Β είναι ήδη ταξινομημένοι και ότι ο Γ πρέπει να είναι ταξινομημένος χωρίς να εφαρμόσουμε φυσαλίδα σ' αυτόν;

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

Τι έχεις κάνει μέχρι τώρα;
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Sergio στις 31 Ιαν 2011, 06:17:18 ΠΜ
Προσπάθησε να σκεφτείς τι ακριβώς θα έκανες "με το χέρι" σε αντίστοιχη περίπτωση..

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

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

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

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

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

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

Δες το.. δεν είναι τόσο δύσκολο όσο νομίζεις !!
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Jammy στις 31 Ιαν 2011, 09:16:42 ΠΜ
βασικα με ονοματα δεν μπορω  να το καταλαβω.κ γω ετσι το εκανα σε χαρτι  με νουμερα ωστε να υπαρχει κ λογος που 8α ταξινομη8ουν κ σκευτομαι τπτ με για...απο...μεχρι και μεσα να εχει καποια αν...
ελενχοντας min,max κτλ κ να κανει αντιμετα8εση σε αυτα.αλλα δεν ξερω πως να υλοποιησω συτη τη σκεψη στο χαρτι.αν μπορειτε δωστε ενα παραδειγμα σαν ασκηση.τελος δεν πρεπει να εχουμε κανει ταξινομηση στο Α κ Β απο πριν πρεπει να τα φτιαξουμε ετσι ωστε ο Γ να ειναι ηδη ταξινομημενος...τρεχα γυρευε...
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Νίκος Αδαμόπουλος στις 31 Ιαν 2011, 12:58:18 ΜΜ
Δεν είμαι σίγουρος ότι μιλάμε για την ίδια άσκηση... Είσαι σίγουρος ότι οι Α και Β δεν πρέπει να είναι ταξινομημένοι; Μας δίνεις την ακριβή διατύπωση της άσκησης για να μη μιλάμε στον αέρα;
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Jammy στις 31 Ιαν 2011, 01:36:58 ΜΜ
ναι βεβαια.
Να  συγχωνευσετε τους πινακας Α και Β  ουτοσωστε να προκυψει ταξινομημενος πινακας Γ διχως να ταξινομησετε κανεναν απτους δυο παραπανω.
αυτο λεει.ειναι εφικτο?οσους ρωτησα το ιδιο μ λενε οτι δεν γινεται..εστω και με αλλους τροπους μπορεις να μου δωσεις καποιες πι8ανες λυσεις?
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Sergio στις 31 Ιαν 2011, 02:43:39 ΜΜ
Αν η εκφώνηση είναι ακριβώς όπως λες, μία λύση θα ήταν:

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

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

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

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

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

Είναι μια πρόχειρη ιδέα που μπορείς να δοκιμάσεις..
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Jammy στις 31 Ιαν 2011, 06:28:57 ΜΜ
ευχαριστω πολυ νομιζω ετσι οντως μπορει να βγει
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Sergio στις 31 Ιαν 2011, 09:15:36 ΜΜ
Παράθεση από: Jammy στις 31 Ιαν 2011, 06:28:57 ΜΜ
ευχαριστω πολυ νομιζω ετσι οντως μπορει να βγει
Ωραία !!  Όταν το κάνεις, αν θες ανέβασέ την και εδώ τη λύση ;)

Καλή συνέχεια :)
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Jammy στις 06 Φεβ 2011, 12:22:21 ΠΜ
τελικα οι Α Β ταξινομημενοι ητανε κ μετα τους εβαζες στον Γ ωστε να βγει ταξινομημενος.λα8ος μου την ειχανε πει την εκφωνηση!οποιος το ξερει ας μου γραψει την ασκησουλα εδω!ευχαριστω!το εγραψα τ τεστ κ εκανα διαφορα αλλα 8ελω να συγκρινω να δω αν βγηκε σωστη!
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Jammy στις 06 Φεβ 2011, 12:50:02 ΠΜ
το μονο που καταφερα να κανω αλλα το δοκιμασα με νουμερα και παρολο π εβγενε πιστευω ειναι λα8ος γιατι πρεπει να εχω κανει χαζομαρα στα i και δν ηξερα πως αλλιως να τα μεταβαλω.δειτε

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

μεσω αυτου προσπα8ησα να πετυχω να παραμεινει στασημος ο Β αν ειναι μικροτερο το νουμερο απτο Α και να παω στο επομενο κουτι του Α.αλλα δεν ξερω αν οντως γεμιζει ολες τις 8εσεις Ν+Μ σωστα.στηλτε μου κι εσεις αν εχετε κατι
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Sergio στις 06 Φεβ 2011, 06:23:04 ΠΜ
Τετράδιο Μαθητή, Κεφάλαιο 9, Παράγραφος 9.3, Παράδειγμα 3, σελ.91-92

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

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

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

Καλή συνέχεια
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Νίκος Αδαμόπουλος στις 06 Φεβ 2011, 12:48:50 ΜΜ
Τετράδιο μαθητή σε ηλεκτρονική μορφή:
https://alkisg.mysch.gr/steki/index.php?action=dlattach;topic=1436.0;attach=521
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Jammy στις 10 Φεβ 2011, 11:39:39 ΜΜ
ποπο ευχαριστω πολυ!! οντως τετραδιο μα8ητη δεν εχω αγγιξει αλλα τωρα που μ το ειπατε 8α πιασω να λυνω κ απο εκει!!
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Νίκος Αδαμόπουλος στις 12 Φεβ 2011, 07:17:42 ΜΜ
Ο αλγόριθμος της συγχώνευσης από το τετράδιο μαθητή σε ψευδογλώσσα (με Δεδομένα και Αποτελέσματα για λόγους συντομίας):

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

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

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

Αποτελέσματα // Γ //
Τέλος Συγχώνευση
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Νίκος Αδαμόπουλος στις 12 Φεβ 2011, 08:50:32 ΜΜ
Εναλλακτικός αλγόριθμος:

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

Ι <- 1
J <- 1
Για Κ από 1 μέχρι Ν+Μ
  Αν Ι <= Ν και J <= Μ τότε
     Αν Α[Ι] < Β[J] τότε
        Γ[Κ] <- Α[Ι]
        Ι <- Ι+1
     αλλιώς
        Γ[Κ] <- Β[J]
        J <- J +1
     Τέλος_αν
  αλλιώς_αν Ι <= Ν τότε
     Γ[Κ] <- Α[Ι]
     Ι <- Ι+1
  αλλιώς
     Γ[Κ] <- Β[J]
     J <- J +1
  Τέλος_αν
Τέλος_επανάληψης

Αποτελέσματα // Γ //
Τέλος Συγχώνευση
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Λαμπράκης Μανώλης στις 15 Ιαν 2014, 12:00:05 ΜΜ
Καλημέρα σε άλους, χρόνια πολλά και χρονιά

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

1) αν μία άσκηση ζητάει συγχώνευση δύο πινάκων, δίχως να είναι ταξινομημένοι, μποροούμε να τους συγχωνεύσουμε σε έναν με μέγεθος Α+Β δίχως να χρειάζεται να κάνουμε ταξινόμηση

2) αν οι δύο πίνακες είναι ταξινομημένοι και τους συγχωνεύσουμε σε έναν με μέγαθος Α+Β, πρέπει να ταξινομήσουμε απαραίτητα και τον τελικό, αλλιώς είναι λάθος

3) αν σκεφτούμε εν τέλει να ταξινομήσουμε τον τελικό πίνακα, μπορούμε να το κάνουμε είτε με την "έξυπνη συγχώνευση" ταξινομώντας απευθείας τα στοιχεία του τελικού , είτε σε "δύο βήματα", δηλαδή να ενώσουμε τους δύο πίνακες, και στην συνέχεια να ταξινομήσουμε τον τελικό ....

εγω θα έλεγα

1) --> σωστή, αν δεν είναι ταξινομημένοι οι αρχικοί, δεν χρειάζεται ταξινόμηση στον τελικό (είναι άραγε "λάθος" να ταξινομήσουμε τον τελικό  ?? )
2) --> σωστή, αν είναι ταξινομημένοι οι αρχικοί, πρέπει να έιναι και ο τελικός  (αν τους ενώσουμε δίχως ταξινόμηση του τελικού είναι λάθος ?? )
3) --> σωστή, μπορούμε να ταξινομήσουμε όπως θέλουμε (έχουμε υποχρέωση να είναι "απευθείας" ταξινομημένος και ο τελικό ??)

θα ήθελα τις γνώμες σας

ευχαριστώ
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: petrosp13 στις 15 Ιαν 2014, 01:57:24 ΜΜ
Η συγχώνευση και η ταξινόμηση είναι 2 διαφορετικές λειτουργίες επί των δομών δεδομένων
Νομίζω ότι όλη η σύγχυση προέρχεται από την ανόητη έκφραση του βιβλίου που μιλάει για συγχώνευση 2 ή περισσότερων ταξινομημένων πινάκων σε έναν επίσης ταξινομημένο
Λες και δεν είναι εφικτό αυτό σε αταξινόμητους πίνακες
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: Λαμπράκης Μανώλης στις 15 Ιαν 2014, 03:01:15 ΜΜ
Οπότε συμφωνούμε και στις παραπάνω προτάσεις ?? το θέμα με όλες τις "γκρίζες ζώνες" του βιβλίου, είναι ότι εμείς πρέπει να δώσουμε μία απάντηση στους μαθητές...μπορεί το "δεν είναι ακριβώς έτσι" να είναι η πιο πλήρης ή η σωστή απάντηση σε κάποιες περιπτώσεις, όμως οι μαθητές περιμένουν μία απάντηση και εμείς πρέπει να δώσουμε μία, καλώς ή κακώς....

ευχαριστώ
Τίτλος: Απ: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας
Αποστολή από: evry στις 15 Ιαν 2014, 08:27:05 ΜΜ

Όταν οι πίνακες δεν είναι ταξινομημένοι μιλάμε για συνένωση και όχι για συγχώνευση.
Τον όρο συγχώνευση τον χρησιμοποιούμε συνήθως για ταξινομημένους πίνακες, από εκεί προκύπτει και η ταξινόμηση merge-sort.
Παραθέτω και το σχετικό λήμμα στη wikipedia για το τι είναι συγχώνευση
http://en.wikipedia.org/wiki/Merge_algorithm (http://en.wikipedia.org/wiki/Merge_algorithm)

Για αυτό και στο βιβλίο όταν μιλάει για συγχώνευση στο κεφ.9 μιλάει αποκλειστικά για ταξινομημένους πίνακες. Η ιδέα είναι να σχεδιάσεις αλγόριθμο που να εκμεταλεύεται το γεγονός ότι είναι ταξινομημένοι και να έχει πολυπλοκότητα πολύ καλύτερη από O(n^2) που έχουν άλλοι αλγόριθμοι.

Προσωπικά πιστεύω ότι ο μόνος τρόπος να το ζητήσουν είναι να το περιγράψουν με λόγια, και να σου ζητήσουν να το δώσεις σε ψευδογλώσσα. Μόνο έτσι γιατί δεν μπορούν να σε υποχρεώσουν να δώσεις αλγόριθμο τάξης O(M+N).