Αποστολέας Θέμα: "Αναίρεση" ταξινόμησης  (Αναγνώστηκε 291 φορές)

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 879
"Αναίρεση" ταξινόμησης
« στις: 10 Μάρ 2018, 10:59:55 πμ »
Η παρακάτω ασκησούλα μου άρεσε πάντα, και πάντα απολαμβάνω την πρώτη φορά που τη δίνω στους μαθητές και παρακολουθώντας τη στιγμή που αντιλαμβάνονται την παγίδα της και τι τρόπο θα βρουν να την ξεπεράσουν.
Υποθέτω ότι όλοι μας λίγο πολύ την έχουμε συναντήσει με κάποια μορφή της και αν όχι, είναι ενδιαφέρον κάποιος να την δει, οπότε ας την επιχειρήσει πριν διαβάσει το σχολιασμό παρακάτω.

"Οι φανέλες των παικτών της βασικής 11άδας μιας ποδοσφαιρικής ομάδας είναι αριθμημένες απο το 1 ως το 11 και τα ονόματα των παικτών δίνονται σε πίνακα ΟΝ[11], όπου στο πρώτο κελί βρίσκεται το όνομα του παίκτη με τη φανέλα με νούμερο 1 κ.ο.κ. και στο τελευταίο, το όνομα του παίκτη με τη φανέλα με νούμερο 11. Να γίνει αλγόριθμος που εμφανίζει το όνομα του κάθε παίκτη και τον αριθμό της φανέλας του, με τα ονόματα σε αλφαβητική σειρά."
Αν είναι να την επιχειρήσετε, σταματήστε εδώ πριν διαβάσετε παρακάτω.

Σύντομα κάποιος θα αντιληφθεί ότι (επειδή ο αριθμός της φανέλας είναι η θέση του παίκτη στον πίνακα) μετά την ταξινόμηση, οι αρχικές θέσεις των ονομάτων του πίνακα χάνονται και στην ουσία δεν ξέρουμε τον αριθμό της φανέλας τους. Το τρικ που απαιτείται είναι να δημιουργήσουμε παράλληλο πίνακα με τις αρχικές θέσεις, έστω ΘΕΣΗ[11] (όπου ΘΕΣΗ[κ]=κ) και ο πίνακας ΟΝ να ταξινομηθεί διατηρώντας την παραλληλία του με τον ΘΕΣΗ.

Η άσκηση που θέλω να δώσω τώρα είναι η εξής:
Μετά την ταξινόμηση, και αξιοποιώντας τον πίνακα ΘΕΣΗ  που περιέχει τις αρχικές θέσεις των ονομάτων, να επαναφέρουμε τον πίνακα ΟΝ στην αρχική του κατάσταση !
(αποφύγετε το προφανές shortcut του να δημιουργήσετε αντίγραφο του πίνακα ΟΝ πριν τον ταξινομήσετε)
Φιλικά,
Γιώργος Θαλασσινός

Κωστας τζιαννης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 173
Απ: "Αναίρεση" ταξινόμησης
« Απάντηση #1 στις: 13 Ιούν 2018, 10:58:27 μμ »
.εχουμε 2 πινακες εναν με ονοματα και εναν με αριθμους φανελας.αρχικα
ο πινακας θεσεις εχει θεσεις=1,2,3,4,..11 .κανουμε μια ταξινομηση στον πινακα ονοματα αλλαζοντας και τον πινακα θεσεις οταν χρειαζεται και μετα κανουμε μια δευτερη ταξινομηση ως προς τον πινακα θεσεις τωρα και αλλαζοντας τον πινακα ονοματα οπου χρειαζεται.ουσιαστικα απλα θελει 2 ταξινομησεις μια με κριτηριο τον πινακα ονοματα και μια δευτερη με κριτηριο τον πινακα θεσεις

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 879
Απ: "Αναίρεση" ταξινόμησης
« Απάντηση #2 στις: 14 Ιούν 2018, 01:07:33 πμ »
Ουπς!
Ντρέπομαι ...  :-[
Αυτή η άσκηση καταρρίπτεται τόσο απλά με μια απλή ξανα-ταξινόμηση, φυσικά...  :-\
Πραγματικά δεν θυμάμαι τι σκεφτόμουν τότε που την έγραψα.
Θα το ξαναδώ όταν μπορέσω, γιατί αξίζει ίσως (αν γίνεται) να την ανασκευάσω ώστε να σώσω το ενδιαφέρον σημείο της.
Γιατί θυμάμαι σίγουρα πως είχα ανακαλύψει μια πολύ ενδιαφέρουσα διαδικασία και ίσως απορροφημένος από αυτή, δεν είδα και το άλλο μονοπάτι.
(αν έχεις χρόνο και όρεξη πάντως σκέψου το και χωρίς ταξινόμηση και ίσως ανακαλύψεις αυτό που είχα βρει και τώρα δεν θυμάμαι)
Φιλικά,
Γιώργος Θαλασσινός

Κωστας τζιαννης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 173
Απ: "Αναίρεση" ταξινόμησης
« Απάντηση #3 στις: 14 Ιούν 2018, 02:50:23 πμ »
Ουπς!
Ντρέπομαι ...  :-[
Αυτή η άσκηση καταρρίπτεται τόσο απλά με μια απλή ξανα-ταξινόμηση, φυσικά...  :-\
Πραγματικά δεν θυμάμαι τι σκεφτόμουν τότε που την έγραψα.
Θα το ξαναδώ όταν μπορέσω, γιατί αξίζει ίσως (αν γίνεται) να την ανασκευάσω ώστε να σώσω το ενδιαφέρον σημείο της.
Γιατί θυμάμαι σίγουρα πως είχα ανακαλύψει μια πολύ ενδιαφέρουσα διαδικασία και ίσως απορροφημένος από αυτή, δεν είδα και το άλλο μονοπάτι.
(αν έχεις χρόνο και όρεξη πάντως σκέψου το και χωρίς ταξινόμηση και ίσως ανακαλύψεις αυτό που είχα βρει και τώρα δεν θυμάμαι)

καταλαβα τι ειχες σκεφτει απλα εγραψα αυτο σαν λυση που θα μπορουσε ανετα να σκεφτει ενας μαθητης.η αλλη λυση ειναι να χρησιμοποιησεις τον δευτερο πινακα σαν δεικτη στον πρωτο καπως.οταν την κανω θα την ανεβασω.εδω ειναι μια λυση προχειρη χωρις δευτερη ταξινομηση που απλα κανει αναζητηση στον πινακα θεσεις για να βρει το 1,2,3 κτλ. υπαρχει κι αλλη λυση δεν ξερω αν εννοουσες αυτη που πχ για να βρεις τον αριθμο 1,μεσα σε μια επαναληψη λες α<-θεσεις[ι] αν θεσεις[α]<>1 τοτε α<-θεσεις[ι] κτλ που απλα θελει μια προσοχη για το τι γινεται αν θεσεις[ι]=ι.αλλα δεν νομιζω οτι πρεπει καποιος να τραβηξει ολη αυτη την ταλαιπωρια.
« Τελευταία τροποποίηση: 14 Ιούν 2018, 03:33:30 πμ από Κωστας τζιαννης »

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 879
Απ: "Αναίρεση" ταξινόμησης
« Απάντηση #4 στις: 14 Ιούν 2018, 12:26:13 μμ »
Ωραίο και αυτό!

Βρήκα τι είχα κάνει:  (για πλάκα και μόνο...)
Κώδικας: [Επιλογή]
! επαναφορά
Για i από 1 μέχρι 11
  Όσο P[i] ≠ i επανάλαβε
    θ ← P[i]
    Αντιμετάθεσε A[i], A[θ]
    Αντιμετάθεσε P[i], P[θ]
  Τέλος_επανάληψης
Τέλος_επανάληψης
όπου P ο πίνακας θέσεων (positions) και Α τα ονόματα
Φιλικά,
Γιώργος Θαλασσινός

Κωστας τζιαννης

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 173
Απ: "Αναίρεση" ταξινόμησης
« Απάντηση #5 στις: 14 Ιούν 2018, 07:46:04 μμ »
Ωραίο και αυτό!

Βρήκα τι είχα κάνει:  (για πλάκα και μόνο...)
Κώδικας: [Επιλογή]
! επαναφορά
Για i από 1 μέχρι 11
  Όσο P[i] ≠ i επανάλαβε
    θ ← P[i]
    Αντιμετάθεσε A[i], A[θ]
    Αντιμετάθεσε P[i], P[θ]
  Τέλος_επανάληψης
Τέλος_επανάληψης
όπου P ο πίνακας θέσεων (positions) και Α τα ονόματα

ωραιος!!ειναι ωραια αυτα