Θέμα: Μοναδικότητα Στοιχείων Πίνακα

[olga_ath]

Χαιρεται

Θα ήθελα την γνώμη σας σχετικά με την παρακάτω άσκηση που έχω βρει εδώ http://karakiza-tsampika.gr/epimorfotikoyliko/likio/diagonismata/ σε ένα διαγώνισμα που έχει διαμορφωθεί από αρκετούς συναδέλφους από το στέκι.

Σε έναν μονοδιάστατο πίνακα Α είναι καταχωρημένοι 100 ακέραιοι αριθμοί και σε έναν δεύτερο πίνακα Β είναι καταχωρημένοι 200 ακέραιοι αριθμοί. Να γίνει αλγόριθμος ο οποίος:
A. Θα υπολογίζει και θα εμφανίζει το πλήθος των διαφορετικών αριθμών που υπάρχουν σε
κάθε πίνακα ξεχωριστά
B. Θα εμφανίζει το πλήθος των διαφορετικών αριθμών που εμφανίζονται μόνο στον έναν από τους δυο πίνακες, δηλαδή αυτούς που εμφανίζονται μόνο στον Α ή μόνο στον Β.
Να θεωρήσετε τους πίνακες Α, Β δεδομένους. Να μη γίνει εισαγωγή των στοιχείων τους.

Εχω σκεφτεί την παράτω προσέγγιση:
Για το Α ερωτημα ταξινομούμε αρχικά κάθεναν πίνακα ξεχωριστά και στην συνέχεια βρίσκουμε πόσους μοναδικούς-διαφορετικούς αριθμούς περιέχει κάθε πίνακας ως εξής:

! ευρεση μοναδικών στοιχείων σε πίνακα Α
πληθος_μονΑ <---0
Για ι από 2 μέχρι 100
       Αν Α[ι]<>Α[ι-1] τότε
               πληθος_μονΑ <---πληθος_μονΑ +1
       Τέλος_Αν
Τέλος_Επανάληψης

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

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

κατάλαβα σωστά το β ερώτημα?
υπάρχει κάποιος ποιο "εξυπνος τρόπος" για την ευρεση των μοναδικών σε Α Η Β και διαφορετικών στοιχείων χωρίς να γίνεται συνένωση;

ευχαριστώ προκαταβολικά

[bagelis]

Σε ελεύθερο κείμενο εγώ θα έκανα το εξής:


Σε έναν μονοδιάστατο πίνακα Α είναι καταχωρημένοι 100 ακέραιοι αριθμοί και σε έναν δεύτερο πίνακα Β είναι καταχωρημένοι 200 ακέραιοι αριθμοί. Να γίνει αλγόριθμος ο οποίος:
A. Θα υπολογίζει και θα εμφανίζει το πλήθος των διαφορετικών αριθμών που υπάρχουν σε
κάθε πίνακα ξεχωριστά
Για κάθε στοιχείο του πίνακα
     Αναζήτησέ το στον πίνακα και μέτρα πλήθος εμφανίσεων
     Αν το πλήθος = 1 τότε εμφάνισέ το
Τέλος_Για



B. Θα εμφανίζει το πλήθος των διαφορετικών αριθμών που εμφανίζονται μόνο στον έναν από τους δυο πίνακες, δηλαδή αυτούς που εμφανίζονται μόνο στον Α

Για κάθε στοιχείο του Α
     Αναζήτηση Σειριακή με Όσο στον Β
     Αν δεν βρέθηκε τότε Εμφάνισέ το
Τέλος_Για

Παρόμοια και για το αντίθετο...

[olga_ath]

ευχαριστώ πολύ για την άμεση απάντηση!

Οσον αφορά την δευτερο ερώτημα νομίζω ότι το έχουμε αντιληφθεί διαφορετικά. Εχω την αίσθηση ότι για εμφανίζουμε-μετράμε το πληθος ενός στοιχείου δεν φτάνει να είναι μόνο στο Α ή μόνο στο Β αλλά πρέπει να είναι και μοναδικό στον καθένα πίνακα  . Φυσικά μπορεί να κάνω και λάθος οπότε διορθώστε με!

Ωραια και η δικιά σου προσέγγιση  . Σε όρους απόδοσης βέβαια λόγω της φυσαλίδας η δικιά μου ειναι λογικά πιο δαπανηρή!

[michaeljohn]

! ευρεση μοναδικών στοιχείων σε πίνακα Α
πληθος_μονΑ <---0

πληθος_μονΑ <--- 1

Μετράμε πάντα το 1ο στοιχείο

[olga_ath]

ευχαριστώ πολύ για την διόρθωση!

[bagelis]

Οσον αφορά την δευτερο ερώτημα νομίζω ότι το έχουμε αντιληφθεί διαφορετικά. Εχω την αίσθηση ότι για εμφανίζουμε-μετράμε το πληθος ενός στοιχείου δεν φτάνει να είναι μόνο στο Α ή μόνο στο Β αλλά πρέπει να είναι και μοναδικό στον καθένα πίνακα  . Φυσικά μπορεί να κάνω και λάθος οπότε διορθώστε με!

ξανακοιτώντας το, νομίζω ότι θέλει να εμφανίζει ΜΙΑ ΦΟΡΑ τον κάθε αριθμό που υπάρχει στον έναν πίνακα και όχι στον άλλον, και όχι περισσότερες, οπότε τα στοιχεία που προκύπτουν στο Α ερώτημα τα βάζουμε σε έναν πίνακα και τα χρησιμοποιούμε από εκεί για το Β ερώτημα.

[gpapargi]

Δες λίγο το θέμα 4 στο παρακάτω διαγώνισμα.
https://alkisg.mysch.gr/steki/index.php?topic=870.0

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

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

[olga_ath]

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

Παντως είναι από τα πιο ωραία θέματα που υπάρχουν !

[evry]

Η εκφώνηση θέλει να πει "το πλήθος των διαφορετικών αριθμών συνολικά".
Τώρα μια πιο αποδοτική λύση μπορεί να γίνει με το εξής σκεπτικό:

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

  για κάθε στοιχείο Γ[ι]
    κοιτάμε αν υπάρχει από τη θέση ι+1 και κάτω
        Αν υπάρχει τότε δεν κάνουμε τίποτα και συνεχίζουμε
        Αλλιώς  αν δεν υπάρχει τότε αυξάνουμε τον μετρητή και σταματάμε την μέσα επανάληψη (με κάποια λογική μεταβλητή)
             και προχωράμε στο Γ[ι+1]

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

ελπίζω τα παραπάνω να είναι κατανοητά

[gpapargi]

Για να μιλήσουμε για ταχύτητα θα πρέπει πρώτα να ξεκαθαρίσουμε για το αν μιλάμε την ύλη τη φετινή ή γενικότερα.

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

Αν μιλάμε γενικότερα μπορείς να αντικαταστήσεις την ταξινόμηση με μια πιο γρήγορη μέθοδο ταξινόμησης (που πιάνει nlogn).

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

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

Γενικά όλα αυτά θέλουν μαθηματική ανάλυση για να δεις τι είναι πιο γρήγορο και δεν αρκεί η διαίσθηση. Αυτά είναι τα θέματα που θα έπρεπε να μας απασχολούν, αλλά…

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

[Γιαννούλης Γιώργος]

Η εκφώνηση θέλει να πει "το πλήθος των διαφορετικών αριθμών συνολικά".
Τώρα μια πιο αποδοτική λύση μπορεί να γίνει με το εξής σκεπτικό:

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

  για κάθε στοιχείο Γ[ι]
    κοιτάμε αν υπάρχει από τη θέση ι+1 και κάτω
        Αν υπάρχει τότε δεν κάνουμε τίποτα και συνεχίζουμε
        Αλλιώς  αν δεν υπάρχει τότε αυξάνουμε τον μετρητή και σταματάμε την μέσα επανάληψη (με κάποια λογική μεταβλητή)
             και προχωράμε στο Γ[ι+1]

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

ελπίζω τα παραπάνω να είναι κατανοητά

Ωραίος τρόπος, υπάρχει και άλλος ένας ψιλοπερίεργος τώρα μου ήρθε και είπα να τον μοιραστώ.

Αρχικά τα βάζω όλα τα στοιχεία σε έναν πίνακα Γ μεγέθους Ν.
διαφορετικά<--0
Σαρώνεις τον πίνακα και βρίσκεις το μέγιστο και το ελαχιστο στοιχείο του.
Για ι απο ελάχιστο μέχρι μέγιστο
   Σειριακή αναζήτηση στον πίνκα Γ για το κλειδί ι
   Αν βρέθηκε τοτε διαφορετικά<--διαφορετικά+1
Είναι ακόμα πιο γρήγορος απο τον παραπάνω αν το μέγεθος μεγιστο-ελάχιστο είναι μικρότερο από το logN.

Απλά είπα να τον αναφέρω.


Ένας άλλος τρόπος πιο εύκολος για τον μαθητή με την ίδια πολυπλοκότητα Ευριπίδη είναι

Ταξινόμηση πίνακα Α με αύξουσα σειρά
διαφορετικα<--1
Για ι από 1 μέχρι Ν-1
   Αν Α[Ν]<>Α[Ν+1] τότε
       διαφορετικά<--διαφορετικά +1
   Τέλος_αν
Τέλος_επανάληψης

Δηλαδή ταξινομείς τα στοιχεία και ελέγχεις πόσες εναλλάγες θα βρείς μέσα στον πίνακα +1, άρα τόσα και τα διαφορετικά στοιχεία... με ίδια πολυπλοκότητα.

[Plug and Pray]

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

(  πληθος_μονΑ <--- 1
Μετράμε πάντα το 1ο στοιχείο  ) 

Αν στον πίνακα τα πρώτα 2-3 στοιχεία του είναι ίδια; Γιατί να ξεκινήσω θεωρώντας ότι έχω ήδη ένα διαφορετικό;

[painter1971]

έχω να προτείνω το εξής:
Αλγόριθμος Διαφορετικοί
   Δεδομένα // Α, Β//
   Διαφ_Α ← 0 ! Α’  Ε Ρ Ω Τ Η Μ Α
    Διαφ_Β ← 0
δείκτης1 ← 0
δείκτης2 ← 0
   Για i από 1 μέχρι 99
      Διαφορετικός ← Αληθής
      Όσο j <= 100 και Διαφορετικός  = Αληθής επανέλαβε
         Αν Α = Α[j] τότε
            Διαφορετικό ← Ψευδής
         j ← j + 1
      Τέλος_επανάληψης
      Αν Διαφορετικό = Αληθής τότε
         Διαφ_Α ← Διαφ_Α + 1
         δείκτης1 ← δείκτης1 + 1
         ΔΑ[δείκτης1] ← Α
      Τέλος_αν
   Τέλος_επανάληψης
   Για i από 1 μέχρι 199
      Διαφορετικός ← Αληθής
      Όσο j <= 200 και Διαφορετικός  = Αληθής επανέλαβε
         Αν Β = Β[j] τότε
            Διαφορετικό ← Ψευδής
         j ← j + 1
      Τέλος_επανάληψης
      Αν Διαφορετικό = Αληθής τότε
         Διαφ_Β ← Διαφ_Β + 1
         δείκτης2 ← δείκτης2 + 1
         ΔΒ[δείκτης2] ← Β
      Τέλος_αν
   Τέλος_επανάληψης
   Εμφάνισε Διαφ_Α, Διαφ_Β
   Για i από 1 μέχρι δείκτης1 ! Β’  Ε Ρ Ω Τ Η Μ Α
      Για j από 1 μέχρι δείκτης2
         Αν ΔΑ =ΔΒ[j] τότε Διαφ_Α ← Διαφ_Α – 1
      Τέλος_επανάληψης
   Τέλος_επανάληψης
   Για i από 1 μέχρι δείκτης2
      Για j από 1 μέχρι δείκτης1
         Αν ΔΒ =ΔΑ[j] τότε Διαφ_Β ← Διαφ_Β – 1
      Τέλος_επανάληψης
   Τέλος_επανάληψης
   Εμφάνισε Διαφ_Α, Διαφ_Β
Τέλος_ Διαφορετικοί

[vtsakan]

Πολύ ωραία θέματα συνάδερφοι.

Ουσιαστικά το αρχικό πρόβλημα λύνεται έαν συνδιάσουμε κατάλληλα τους δύο επόμενους αλγορίθμους:


Αλγόριθμος Μοναδικότητα
   Δεδομένα //Α, n//
   μ ← 0
   Για i από 1 μέχρι n
      υπάρχει ← Ψευδής
      Για ξ από 1 μέχρι μ
         Αν (Α = B[ξ]) τότε
            υπάρχει ← Αληθής
         Τέλος_Αν
      Τέλος_επανάληψης
      Αν όχι(υπάρχει) τότε
            μ ← μ + 1
            Β[μ] ← Α
      Τέλος_Αν
   Τέλος_επανάληψης
   Αποτελέσματα //Β, μ//
Τέλος Μοναδικότητα




Αλγόριθμος Διαφορά
   Δεδομένα //A, n, B, m//
   δ ← 0
Για i από 1 μέχρι n
      υπάρχει ← Ψευδής
      ξ ← 1
      Όσο ΟΧΙ(υπάρχει) ΚΑΙ (ξ <= m) επανέλαβε
         Αν (Α = B[ξ]) τότε
            υπάρχει ← Αληθής
         Τέλος_αν
         ξ ← ξ + 1
      Τέλος_επανάληψης
      Αν ΟΧΙ(υπάρχει) τότε
         δ ← δ + 1
         Γ[δ] ← Α
      Τέλος_αν
   Τέλος_επανάληψης
   Αποτελέσματα //Γ, δ//
Τέλος Διαφορά


Ο αλγόριθμος Μοναδικότητα θα πρέπει να τρέξει 2 φορές για να υπολογίσει τα μοναδικά στοιχεία των πινάκων και ο αλγόριθμος Διαφορά άλλες 2 φορές για να υπολογίσει την πρώτη τα στοιχεία που ανήκουν στον Α και όχι στον Β και την δεύτερη τα στοιχεία που ανήκουν στον Β και όχι στον Α.

αυτά...

[vtsakan]

όπου Α στην προηγούμενη απάντηση μου έπρεπε να εμφανιστεί Α.
Ο δαίμων του forum...

[vtsakan]

A {i}

[alkisg]

Αν βάζεις τον κώδικα μέσα σε [cοde]κώδικας[/cοde] tags, τότε το [ί] δεν ...εξαφανίζεται:

Κώδικας: Text

1. A[i]
2.  

[vtsakan]

ευχαριστώ,

δεν το ήξερα