ΤΑΞΙΝΟΜΗΣΗ ΠΙΝΑΚΑ ΜΕ ΜΕΤΑΘΕΣΗ 2 ΣΤΟΙΧΕΙΩΝ

Ξεκίνησε από olmp, 15 Μαρ 2008, 08:08:08 ΜΜ

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

olmp

ΓΕΙΑ ΣΑΣ,
ΜΗΠΩΣ ΘΑ ΜΠΟΡΟΥΣΕ ΚΑΠΟΙΟΣ ΝΑ ΜΕ ΒΟΗΘΗΣΕΙ ΜΕ ΤΟΝ ΠΑΡΑΚΑΤΩ ΑΛΓΟΡΙΘΜΟ?
ΖΗΤΕΙΤΑΙ ΝΑ ΤΑΞΙΝΟΜΗΘΕΙ  ΜΟΝΟΔΙΑΣΤΑΤΟΣ ΠΙΝΑΚΑΣ ΠΟΥ ΠΕΡΙΕΧΕΙ ΟΝΟΜΑΤΑ ΚΑΙ ΤΗΛΕΦΩΝΑ ΕΝΑΛΛΑΞ. ΔΗΛΑΔΗ ΠΡΩΤΗ ΓΡΑΜΜΗ ΕΧΕΙ ΕΝΑ ΟΝΟΜΑ ΚΑΙ Η ΔΕΥΤΕΡΗ ΤΟ ΑΝΤΙΣΤΟΙΧΟ ΤΗΛΕΦΩΝΟ Κ.Ο.Κ.ΠΩΣ ΜΠΟΡΕΙ ΝΑ ΥΛΟΠΟΙΗΘΕΙ ΑΥΤΟ?

Laertis

Ποιος νοσηρός εγκέφαλος σκέφτηκε τέτοια υλοποίηση ;
Τέλος πάντων , μονές θέσεις ονόματα , ζυγές τηλεφωνα και ταξινόμηση αλφαβητικά φαντάζομαι ...Επίσης ο πίνακας πρέπει υποχρεωτικά να έχει άρτιο αριθμό θέσεων, δεχόμαστε δλδ ότι το ν είναι πάντα άρτιος .
Κάπως έτσι μου βγαίνει:

Για ι απο 3 μέχρι ν
Για j απο ν-1 μέχρι ι με_βήμα -2
Αν table[j-2] > table[j] τότε
    αντιμετάθεσε table[j-2] , table[j]
    αντιμετάθεσε table[j-1] , table[j+1]
Τέλος-αν
Τέλος_επανάληψης
Τέλος_επανάληψης
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

Michael

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

Για i από 3 μέχρι Ν με_βήμα 2
.
.
.

Δεν το έχω ψάξει ακόμα πολύ αναλυτικά, αλλά οι δοκιμές που έκανα μέχρι στιγμής δεν δείχνουν να υπάρχει πρόβλημα. Απλώς γλυτώνουμε κάποιους περιττούς ελέγχους. Θα το ξαναδώ βέβαια...

olmp

ΝΑΙ, ΖΗΤΕΙΤΑΙ ΑΛΦΑΒΗΤΙΚΗ ΤΑΞΙΝΟΜΗΣΗ ΞΕΧΑΣΑ ΝΑ ΤΟ ΑΝΑΦΕΡΩ..ΕΥΧΑΡΙΣΤΩ!

P.Tsiotakis

Πρόκειται για την άσκηση 12, στο http://users.kor.sch.gr/ptsiotakis/aepp/aepp_ask3_4.htm

Παιδιά, και η λύση σας είναι πολύ κομψή

Φίλε olmp, μάλλον ρώτησες πως γίνεται να είναι αποθηκευμένα ονόματα και τηλέφωνα στον ίδιο πίνακα. Τα 10ψήφια τηλέφωνα, εφόσον δε θα υποστούν αριθμητική επεξεργασία, αποθηκεύονται ως αλφαριθμητικά...


ΥΓ: νοσώ άσχημα :D

olmp

ΑΥΤΗ ΕΙΝΑΙ Η ΑΣΚΗΣΗ...ΑΝ ΤΗΝ ΕΙΧΑ ΒΡΕΙ ΣΤΟ SITE  ΠΡΟΦΑΝΩΣ Κ ΔΕΝ ΘΑ ΡΩΤΟΥΣΑ ΓΙΑ  ΤΗΝ ΛΥΣΗ ΤΗΣ.Η ΕΡΩΤΗΣΗ ΜΟΥ ΔΕΝ ΕΙΧΕ ΝΑ ΚΑΝΕΙ ΜΕ ΤΟΝ ΠΙΝΑΚΑ ΚΑΙ ΠΩΣ ΕΙΝΑΙ ΔΥΝΑΤΩΝ ΝΑ ΕΧΕΙ ΑΡΙΘΜΟΥΣ ΚΑΙ ΝΟΥΜΕΡΑ ΑΛΛΑ ΠΩΣ ΘΑ ΤΡΟΠΟΠΟΙΗΣΩ ΤΗΝ BUBBLE SORT.
ΕΥΧΑΡΙΣΤΩ ΓΙΑ ΤΗΝ ΒΟΗΘΕΙΑ

olmp

Α!ΞΕΧΑΣΑ ΟΜΩΣ ΚΑΙ ΜΙΑΣ ΚΑΙ ΑΝΑΦΕΡΘΗΚΕ..ΜΕ ΠΡΟΓΡΑΜΜΑ ΔΕΝ ΘΑ ΜΠΟΡΟΥΣΕ ΝΑ ΛΥΘΕΙ ΕΤΣΙ ΔΕΝ ΕΙΝΑΙ?

olmp

...ΩΧ ΠΡΟΣ ΣΤΙΓΜΗΝ ΜΠΕΡΔΕΥΤΗΚΑ ΔΕΝ ΞΕΡΩ ΓΙΑΤΙ...ΦΥΣΙΚΑ ΚΑΙ ΓΙΝΕΤΑΙ!ΑΚΥΡΟ

P.Tsiotakis

αν το Ν γίνει συγκεκριμένο και διαβαστεί ο πίνακας Π (αν απαλειφθεί η εντολή Δεδομένα) μπορεί να υλοποιηθεί σε ΓΛΩΣΣΑ.

Που δόθηκε η άσκηση; Σχολείο/Φροντιστήριοποιας ποιας περιοχής;

Laertis

Αχα εσύ Παναγιώτη είσαι ο "νοσηρός" εγκέφαλος  αυτής της άσκησης. :D

Φίλε Michael μπορεί όντως να είναι για σένα η πιο "όμορφη" άσκηση στην ΑΕΠΠ αλλά εγώ διατηρώ σοβαρές επιφυλάξεις γιατί η "ομορφιά" της στηρίζεται μόνο και μόνο στην παράξενη υλοποίηση που γίνεται. Αντί ενός πίνακα 100 θέσεων για 50 συνδρομητές και 50 τηλέφωνα εναλλάξ γιατί να μην γίνει με 2 παράλληλους μονοδιάστατους 50 θέσεων (πιο εύκολο - σούπα θα έλεγα- με τις ίδιες θέσεις μνήμης) οπότε η άσκηση αυτομάτως μετατρέπεται σε βάτραχο από πρίγκηπα.  ;)
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

P.Tsiotakis

θα μπορούσαμε στην αρχή από τον 1 πίνακα να δημιουργήσουμε 2 παραλληλους:

Δεδομένα // Ν, Π //
κ ← 0
Για i από 1 μέχρι N με_βήμα 2
  κ ← κ + 1
  ΟΝ[κ] ← Π[ i ]
  ΤΗΛ[κ]  ← Π[i+1]
Τέλος_επανάληψης
! προφανώς κ = N div 2
...............

και μετά κλασσική επεξεργασία, όπως λες Γιώργο

Michael

Σωστά, είχα μείνει στην αρχική εκφώνηση του πρώτου post που ζητούσε ο τελικός πίνακας να είναι μονοδιάστατος, όπως και ο αρχικός.
Οπότε μετά την κλασσική επεξεργασία, θα απαιτούνταν ένα ακόμα κόψε-ράψε ώστε ο τελικός μας πίνακας να είναι μονοδιάστατος και να περιέχει ονόματα και τηλέφωνα εναλλάξ. Γι' αυτό μου αρέσει η άσκηση. Μου θυμίζει κάποια θέματα Μαθηματικών όπου ο παρατηρητικός που θα δει την κρυμμένη σχέση επιβραβεύεται λύνοντας την άσκηση σε δευτερόλεπτα (και σε δύο σειρές). Αυτός που δεν θα την δει... καλό ταξίδι σύντροφε... :)

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

ΠαράθεσηΥΓ: νοσώ άσχημα
Αν είναι να συνεχίσεις έτσι, μην περιμένεις από εμένα να σου πω περαστικά. :)

gpapargi

Να πω και εγώ 2 λόγια. Όπως υπάρχει ο βέλτιστος αλγόριθμος έτσι υπάρχει και υπάρχει και η κατάλληλη επιλογή των δομών, δηλαδή η δομή που θα κάνει τον αλγόριθμο ευκολότερο λόγω του ότι ταιριάζει φυσικά στο πρόβλημά μας.

Δεν πρέπει να ξεχνάμε ότι οι πίνακες 2 διαστάσεων κάθονται ανά γραμμή στη μνήμη του υπολογιστή, άρα κατά βάση είναι μονοδιάστατοι. Θα μπορούσαμε κάλλιστα να τους χειριστούμε έτσι. Όμως έχει τόσο μεγάλη ξεχωριστή σημασία κάποιο υποσύνολό τους που αξίζει να τους διαθέσουμε ένα ξεχωριστό δείκτη για να βηματίζουμε μόνο σε αυτά. Έτσι καταλήγουμε στην έννοια των δισδιάστατων. Τον μονοδιάστατο πίνακα που είναι στη μνήμη τον «βλέπουμε» σα δισδιάστατο. Στο συγκεκριμένο πρόβλημα χειριζόμαστε τα στοιχεία όπως θα το κάναμε αν δεν υπήρχε η έννοια του δισδιάστατου. Δηλαδή αν έχουμε πίνακα 2 διαστάσεων και στην πρώτη στήλη έχουμε όνομα και στη δεύτερη τηλέφωνο (χαρακτήρες για να υποστηρίζουμε τηλέφωνα που αρχίζουν από 0) κάνει ο υπολογιστής σιωπηλά αυτό που στη συγκεκριμένη άσκηση κάνουμε manually. 

Ένα τέτοιο παράδειγμα άσκησης από το διδακτικό πακέτο είναι στο τετράδιο μαθητή κεφάλαιο 3 παράδειγμα 5 (αυτό με τους αραιούς πίνακες). Δες πόσο ευκολότερη θα ήταν η επεξεργασία αν αντί να βάζουμε τα μη μηδενικά στοιχεία σε μονοδιάστατο,  βάζαμε το μη μηδενικό περιεχόμενο του αρχικό δισδιάστατου σε ένα πίνακα μιας διάστασης και δίπλα βάζαμε τη γραμμή και τη στήλη του μη μηδενικού στοιχείου σε δισδιάστατο πίνακα 2 στηλών (μια για τη γραμμή του στοιχείου και μια για τη στήλη).  Θα κάναμε πολύ εύκολα αναζήτηση για κάποιο στοιχείο, ταξινόμηση, αθροίσματα ... ότι θέλουμε. Είναι ένα από τα παραδείγματα που δείχνουν πόσο συνυφασμένες με τους αλγόριθμους είναι οι δομές δεδομένων.

Βολική δομή -> εύκολος αλγόριθμος
Άβολη δομή -> δύσκολος αλγόριθμος

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

andreas_p

Έστω   Σ[100] ο πίνακας με τα παραπάνω στοιχεία.

Στις περιττές θέσεις τα ονόματα και στις  άρτιες τα τηλέφωνα.


...

ΑΡΧΗ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΔΙΑΒΑΣΕ  Ν
ΜΕΧΡΙΣ_ΟΤΟΥ Ν >0  ΚΑΙ Ν <=100  ΚΑΙ Ν MOD 2 =0

  ΓΙΑ Ι ΑΠΟ 3  ΜΕΧΡΙ  Ν  ΜΕ_ΒΗΜΑ 2
     ΓΙΑ  J   ΑΠΟ  Ν  ΜΕΧΡΙ  Ι  ΜΕ_ΒΗΜΑ -2
         ΑΝ  Σ[J] < Σ[J-2]  ΤΟΤΕ   !  αλφαβητικά τα ονόματα
              ΚΑΛΕΣΕ  αντι(Σ[J],Σ[J-2])
              ΚΑΛΕΣΕ  αντι(Σ[J+1],Σ[J-2+1])
          ΤΕΛΟΣ_ΑΝ
     ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

όπου  αντι  διαδικασία αντιμετάθεσης.

Ανδρέας

andreas_p


... κάτι ξέφυγε 

Διόρθωση :

ΓΙΑ Ι ΑΠΟ 3  ΜΕΧΡΙ  Ν-1  ΜΕ_ΒΗΜΑ 2  ! Ν DIV 2  -1  σαρώσεις
     ΓΙΑ  J   ΑΠΟ  Ν-1  ΜΕΧΡΙ  Ι  ΜΕ_ΒΗΜΑ -2
        ...