Αποστολέας Θέμα: Άσκηση Αντι-ταξινόμησης..  (Αναγνώστηκε 3815 φορές)

Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3136
  • Dracarys
    • Panagiotis Tsiotakis
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #15 στις: 03 Μάρ 2011, 12:52:37 μμ »
και με υποπρόγραμμα την ταξινόμηση, που καλείται δυο φορές με αλλαγή στον πίνακα που ταξινομείται και αυτόν που αντιμετατίθεται
(προϋπόθεση να είναι ο πίνακας αριθμών (όπως και ο πίνακας δεικτών) ΑΚΕΡΑΙΟΣ)

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #16 στις: 03 Μάρ 2011, 12:59:45 μμ »
Και αν θέλαμε τα στοιχεία να είναι χαρακτήρες ;;
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3049
  • to Iterate is human to Recurse divine
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #17 στις: 03 Μάρ 2011, 01:14:51 μμ »
νομίζω με operator overloading στον τελεστή < και αντιμετάθεση μόνο των δεικτών λύνονται όλα τα προβλήματα :D
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3136
  • Dracarys
    • Panagiotis Tsiotakis
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #18 στις: 03 Μάρ 2011, 01:28:47 μμ »
Και αν θέλαμε τα στοιχεία να είναι χαρακτήρες ;;

να μην το κάνεις με διαδικασία  :-X

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #19 στις: 03 Μάρ 2011, 05:12:20 μμ »
Οδυσσέα μου φαίνεται ότι όταν στο τέλος προσπαθούμε να επαναφέρουμε τον πίνακα στην αρχική του μορφή υπάρχει κάποιο πρόβλημα.
Οι αντιμεταθέσεις στοιχείων στους πίνακες Θ και Π έχουν ως αποτέλεσμα να χαθεί η "παραλληλία".

Αυτό που θα μπορούσε να γίνει είναι να δημιουργηθεί ένας νέος πίνακας ως εξής :
Κώδικας: Text
  1. Για ι από 1 μέχρι Ν
  2.         ΝΠ[Θ[ι]] ← Π[ι]
  3. Τέλος_επανάληψης
  4.  
« Τελευταία τροποποίηση: 03 Μάρ 2011, 05:24:00 μμ από sstergou »
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #20 στις: 04 Μάρ 2011, 03:31:12 μμ »
Ταξινομούμε τον πίνακα Π παράλληλα με τον πίνακα Θ. Μετά την ταξινόμηση, το στοιχείο Θ[δ] περιέχει την αρχική θέση του Π[δ].

Κώδικας: [Επιλογή]
! μεταφορά στην αρχική θέση
ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ Ν-1
  αρχική <- Θ[δ]
  αντιμετάθεσε Π[δ], Π[αρχική]
  αντιμετάθεσε Θ[δ], Θ[αρχική]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Οι αντιμεταθέσεις στοιχείων στους πίνακες Θ και Π έχουν ως αποτέλεσμα να χαθεί η "παραλληλία".

Αφού το στοιχείο σε κάποια θέση του Π εξακολουθεί να αντιστοιχεί στο στοιχείο στην ίδια θέση του Θ, δε νομίζω πως χάνεται η παραλληλία.. Νομίζω πως το πρόβλημα είναι αλλού..

Ας δοκιμάσουμε τον κώδικα με 4 στοιχεία:

Έστω αρχικά  ο πίνακας Π με:
1. Ρ
2. Σ
3. Δ
4. Α

μετά τη δημιουργία του πίνακα δεικτών θα έχουμε (σε παρένθεση τα στοιχεία του πίνακα Θ):
1. Ρ (1)
2. Σ (2)
3. Δ (3)
4. Α (4)

μετά την ταξινόμηση θα έχουμε:
1. Α (4)
2. Δ (3)
3. Ρ (1)
4. Σ (2)

οπότε με την εκτέλεση του κώδικα επαναφοράς θα έχουμε:

1η επανάληψη: το Α πάει στη σωστή του θέση και έρχεται το Σ επάνω..
1. Σ (2)
2. Δ (3)
3. Ρ (1)
4. Α (4)

2η επανάληψη: το Δ πάει στη σωστή του θέση και έρχεται το Ρ επάνω..
1. Σ (2)
2. Ρ (1)
3. Δ (3)
4. Α (4)

3η επανάληψη: το Δ παραμένει στη σωστή του θέση..
1. Σ (2)
2. Ρ (1)
3. Δ (3)
4. Α (4)

ΤΕΛΟΣ.. χωρίς όλα τα στοιχεια να έχουν επανέρθει στην αρχική τους θέση :(

Καθ' όλη τη διάρκεια, οι δύο πίνακες παραμένουν "παράλληλοι".  Το πρόβλημα όμως δημιουργείται από την πρώτη κιόλας επανάληψη όταν, ενώ το Α πάει στη σωστή του θέση, έρχεται στη θέση του το Σ και, όταν μετά εξετάζεται το Δ και πάει στη σωστή του θέση, έρχεται στη θέση του το Ρ.  Έχοντας πλέον το δ (μεταβλητή ελέγχου της ΓΙΑ) πάρει την τιμή 3, δεν ξαναεξετάζεται ούτε το Ρ ούτε το Σ τα οποία έτσι παραμένουν σε λάθος θέσεις μέχρι το τέλος :(
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #21 στις: 04 Μάρ 2011, 03:55:17 μμ »
Ιδέα:

Αν "επιμέναμε" μέχρι στη θέση δ να βρεθεί το σωστό στοιχείο;

Κώδικας: [Επιλογή]
δ <- 1
Αρχή_επανάληψης
  Αρχή επανάληψης
    αρχική <- Θ[δ]
    αντιμετάθεσε Π[δ], Π[αρχική]
    αντιμετάθεσε Θ[δ], Θ[αρχική]
  Μέχρις_ότου Θ[δ]=δ
  δ <- δ + 1
Μέχρι_ότου δ > Ν

θα "δούλευε";  Έχω την εντύπωση ότι, με τον παραπάνω κώδικα, όταν το αυξάνεται το δ.. ό,τι έχει αφήσει πίσω του είναι "τακτοποιημένο"

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

Οπότε, μία τροποποίηση θα μπορούσε να είναι:
Κώδικας: [Επιλογή]
δ <- 1

βρ <- Ψευδής
Όσο δ < Ν και βρ = Ψευδής επανάλαβε
  Αν Θ[δ] <> δ τότε
    βρ <- Αληθής
  αλλιώς
    δ <- δ + 1
  Τέλος_αν
Τέλος_επανάληψης

Όσο δ < Ν επανάλαβε
  Αρχή επανάληψης
    αρχική <- Θ[δ]
    αντιμετάθεσε Π[δ], Π[αρχική]
    αντιμετάθεσε Θ[δ], Θ[αρχική]
  Μέχρις_ότου Θ[δ]=δ

  βρ <- Ψευδής
  Όσο δ < Ν και βρ = Ψευδής επανάλαβε
    Αν Θ[δ] <> δ τότε
      βρ <- Αληθής
    αλλιώς
      δ <- δ + 1
    Τέλος_αν
Τέλος_επανάληψης

Τι λέτε ;
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

odysseas

  • Ομάδα διαγωνισμάτων 2011
  • *
  • Μηνύματα: 842
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #22 στις: 05 Μάρ 2011, 12:13:55 πμ »
Αυτό που θα μπορούσε να γίνει είναι να δημιουργηθεί ένας νέος πίνακας [...]

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

Ιδέα: Αν "επιμέναμε" μέχρι στη θέση δ να βρεθεί το σωστό στοιχείο;

Ναι, αυτό που χαρακτηρίζεις παρακάτω και ως "αλυσίδα" είναι ένας καλός χαρακτηρισμός γι' αυτό που συμβαίνει. Οι περιττές αντιμεταθέσεις μπορούν να αποφευχθούν εύκολα αν χρησιμοποιήσει κανείς ΟΣΟ αντί για ΜΕΧΡΙΣ_ΟΤΟΥ.

Κώδικας: [Επιλογή]
ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ Ν-1
  ΟΣΟ Θ[δ] <> δ ΕΠΑΝΑΛΑΒΕ
    αρχική <- Θ[δ]
    αντιμετάθεσε Π[δ], Π[αρχική]
    αντιμετάθεσε Θ[δ], Θ[αρχική]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

θα "δούλευε";  Έχω την εντύπωση ότι, με τον παραπάνω κώδικα, όταν το αυξάνεται το δ.. ό,τι έχει αφήσει πίσω του είναι "τακτοποιημένο"

Αν επιμείνει κανείς να προχωρήσει μόνο όταν Θ[δ] = δ τότε είναι βέβαιο ότι κανένα στοιχείο στη συνέχεια δεν πρόκειται να διαταράξει τις υπάρχουσες τοποθετήσεις αφού τα στοιχεία που έχουν προηγηθεί είναι ήδη στις θέσεις τους.

και με υποπρόγραμμα την ταξινόμηση, που καλείται δυο φορές με αλλαγή στον πίνακα που ταξινομείται και αυτόν που αντιμετατίθεται

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