Άσκηση Αντι-ταξινόμησης..

Ξεκίνησε από Sergio, 02 Μαρ 2011, 11:00:44 ΠΜ

« προηγούμενο - επόμενο »

P.Tsiotakis

και με υποπρόγραμμα την ταξινόμηση, που καλείται δυο φορές με αλλαγή στον πίνακα που ταξινομείται και αυτόν που αντιμετατίθεται
(προϋπόθεση να είναι ο πίνακας αριθμών (όπως και ο πίνακας δεικτών) ΑΚΕΡΑΙΟΣ)

Sergio

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

evry

νομίζω με operator overloading στον τελεστή < και αντιμετάθεση μόνο των δεικτών λύνονται όλα τα προβλήματα :D
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

P.Tsiotakis

Παράθεση από: Sergio στις 03 Μαρ 2011, 12:59:45 ΜΜ
Και αν θέλαμε τα στοιχεία να είναι χαρακτήρες ;;

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

sstergou

#19
Οδυσσέα μου φαίνεται ότι όταν στο τέλος προσπαθούμε να επαναφέρουμε τον πίνακα στην αρχική του μορφή υπάρχει κάποιο πρόβλημα.
Οι αντιμεταθέσεις στοιχείων στους πίνακες Θ και Π έχουν ως αποτέλεσμα να χαθεί η "παραλληλία".

Αυτό που θα μπορούσε να γίνει είναι να δημιουργηθεί ένας νέος πίνακας ως εξής :
Κώδικας: Ψευδογλώσσα
Για ι από 1 μέχρι Ν
	ΝΠ[Θ[ι]] ← Π[ι] 
Τέλος_επανάληψης


Sergio

Παράθεση από: odysseas στις 03 Μαρ 2011, 01:17:13 ΠΜ
Ταξινομούμε τον πίνακα Π παράλληλα με τον πίνακα Θ. Μετά την ταξινόμηση, το στοιχείο Θ[δ] περιέχει την αρχική θέση του Π[δ].

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


Παράθεση από: sstergou στις 03 Μαρ 2011, 05:12:20 ΜΜ
Οι αντιμεταθέσεις στοιχείων στους πίνακες Θ και Π έχουν ως αποτέλεσμα να χαθεί η "παραλληλία".

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

Ας δοκιμάσουμε τον κώδικα με 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

Ιδέα:

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

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


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

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

Οπότε, μία τροποποίηση θα μπορούσε να είναι:
δ <- 1

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

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

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


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

odysseas

Παράθεση από: sstergou στις 03 Μαρ 2011, 05:12:20 ΜΜ
Αυτό που θα μπορούσε να γίνει είναι να δημιουργηθεί ένας νέος πίνακας [...]

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

Παράθεση από: Sergio στις 04 Μαρ 2011, 03:55:17 ΜΜ
Ιδέα: Αν "επιμέναμε" μέχρι στη θέση δ να βρεθεί το σωστό στοιχείο;

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

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


Παράθεση από: Sergio στις 04 Μαρ 2011, 03:55:17 ΜΜ
θα "δούλευε";  Έχω την εντύπωση ότι, με τον παραπάνω κώδικα, όταν το αυξάνεται το δ.. ό,τι έχει αφήσει πίσω του είναι "τακτοποιημένο"

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

Παράθεση από: ptsiotakis στις 03 Μαρ 2011, 12:52:37 ΜΜ
και με υποπρόγραμμα την ταξινόμηση, που καλείται δυο φορές με αλλαγή στον πίνακα που ταξινομείται και αυτόν που αντιμετατίθεται

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