Γεια σας!!!!
Θα ήθελα να ρωτήσω αν μπορεί να γίνει συγχώνευση σε δυο δισδιάστατους ταξινομημένους πίνακες, θα ελέγχουμε γραμμή προς γραμμή? Μήπως θα μπορούσατε να μου δώσετε ένα παράδειγμα?
Ευχαριστώ
Υπάρχουν δισδιάστατοι ταξινομημένοι πίνακες ;
Ε, ναι, είναι λίγο τραβηγμένο... :)
Γενικά ότι γίνεται σε μονοδιάστατο πίνακα μπορεί να γίνει και σε δισδιάστατο. Χρειάζεται όμως να γίνει μετατροπή των δύο δεικτών (ι, κ) του δισδιάστατου σε έναν (ι), αυτόν του αντίστοιχου μονοδιάστατου.
Δες το αντίστοιχο θέμα για την ταξινόμηση δισδιάστατου πίνακα (//index.php?board=9;topic=310.2). Χρησιμοποιώντας τους ίδιους τύπους μετατροπής δεικτών μπορείς να κάνεις συγχώνευση σε δισδιάστατους πίνακες σαν να ήταν μονοδιάστατοι.
Για ποιο λόγο να κάνουν οι μαθητές συγχώνευση διδιάστατων πινάκων; Ποιος είναι ο σκοπός αυτής της άσκησης; Αν θέλεις να τους βάλεις λίγο πιο δύσκολες ασκήσεις με πίνακες άνοιξε ένα βιβλίο γραμμικής άλγεβρας Α' έτους θετικής σχολής και από εκεί μπορείς να βγάλεις άπειρες ασκήσεις: διαγώνιοι, τριδιαγώνιοι, συμμετρικοί, ανάστροφοι και άλλοι πίνακες. Υπάρχει και το μαγικό τετράγωνο που έχει το τετράδιο του μαθητή.
Την ταξινόμηση την μαθαίνουν μόνο για μονοδιάστατους πίνακες. Πώς λοιπόν είναι δυνατόν να ζητήσουν ή έστω να κάνουμε ασκήσεις που να φορούν συγχώνευση δυο ταξινομημένων δισδιάστατων πινάκων? Ας μην γινόμαστε υπερβολικοί.
Εύκολα καταλαβαίνει κανείς ότι μπορούμε να πάρουμε οποιοδήποτε αλγόριθμο των μονοδιάστατων πινάκων και να ρωτήσουμε αν μπορούμε να τον υλοποιήσουμε για πίνακες 2 διαστάσεων.
Αυτό που θα ήθελα να πω είναι ότι τέτοια προβλήματα αν και μπορουν να λυθούν (όπως λέει ο Άλκης), θα πρέπει να αναρωτηθούμε αν έχουν πάντα νόημα.
Στο μονοδιάστατο πίνακα τα στοιχεία έχουν μια φυσική διάταξη Αυτό που έχει μικρότερο δείκτη προηγείται. Σε πίνακα 2 διαστάσεων η διάταξη δεν είναι ορισμένη. Θα πρέπει κάπως να οριστεί. Πιο στοιχείο προηγείται στη διάταξη έτσι ώστε εκεί να βάλουμε το δεύτερο εγαλύτερο; το Α[2,1] ή το Α[1,2];
Μπορούμε να σκεφτούμε και το γεωμετρικό ανάλογο. Στην ευθεία των πραγματικών κάθε σημείο αντιστοιχεί με ένα αριθμό. Όποιο σημείο είναι πιο αριστερά προηγείται. Στο επίπεδο όμως κάθε σημείο αντιστοιχεί με ένα ζεύγος αριθμών. Τα ζεύγη όμως δεν είναι τοποθετημένα σε σειρά. Πιο προηγείται; Αυτό που είναι πιο αριστερά; Αυτό που είναι πιο κάτω; Αυτό που είναι πιο κοντά την αρχή των αξόνων;
Συνήθως σιωπηλά θεωρούμε το Α[1,2] πριν το Α[2,1]. Υποθέτω πως αυτό γίνεται λόγω του ότι εμείς οι άνθρωποι γράφουμε/διαβάζουμε κείμενο γραμμή γραμμή από πάνω προς τα κάτω. Και φαντάζομαι πως αυτό γίνεται επειδή τα μάτια μας είναι το ένα δίπλα στο άλλο και έτσι έχουμε ευρύτερο οπτικό πεδίο οριζόντια παρά κάθετα. Αν τα λέω καλά, αν είχαμε τα μάτια μας το ένα κάτω από το άλλο τότε θα διαβάζαμε αυθαίρετα τους πίνακες κατά στήλη. ;D
Ότι όμως κι αν εφαρμόσουμε στους πίνακες είναι αυθαίρετο.
Ας δούμε και ένα συγκεκριμένο παράδειγμα. ʼς πούμε ότι σε ένα πίνακα 2 διαστάσεων αποθηκεύθουμε τους πόντους που έχει βάλει κάθε παίκτης μιας ομάδας μπάσκετ σε κάθε αγωνιστική. Γιατί να βάλουμε το δεύτερο νούμερο στο Α[1,2] και όχι το Α[2,1];
Τέλος θα ήθελα να σταθώ στον ορισμό της ταξινόμησης που δίνει το βιβλίο στη σελίδα 66. Ορίζει την ταξινόμηση για μονοδιάστατο πίνακα. Η συνήθης αύξουσα ταξινόμηση θεωρεί σαν f την ταυτοτική συνάρτηση. Δεν ορίζεται όμως η ταξινόμηση για πίνακες 2 διαστάσεων.
Νομίζω λοιπόν πως το ζήτημα της ταξινόμησης πινάκων 2 διαστάσεων δεν είναι ένα καλώς ορισμένο πρόβλημα. Θα πρέπει πρώτα να το ορίσουμε. Προφανώς αυτά ισχύουν και για τη συγχώνευση αφού η έννοια της ταξινόμησης εμπεριέχεται.
γίνεται ταξινόμηση φυσαλίδας ανά γραμμή ή ανά στήλη σε 2 διαστάσεις. αλλά αν ακολουθήσει και συγχώνευση, νομίζω ότι ξεφεύγει λιγάκι...
Θα προσπαθήσω να θέσω ένα θεωρητικό σχετικό ερώτημα.
Η ταξινόμηση είναι κατά τον ορισμό του βιβλίου μια μετάθεση στοιχείων δωθείσης μιας συνάρτησης f κλπ.
Σε μια άσκηση "ταξινόμησης" σε διασδιάστατο θα πρέπει να μπορούμε να ορίσουμε μια τέτοια συνάρτηση διάταξης.
Αυτό δεν είναι προφανές και πιθανώς και μη υλοποιήσιμο. Γι αυτό δεν μπορούμε να μιλήσουμε για ταξινόμηση αλλά για μια εμφάνιση του δισδιάστατου πίνακα.
Συμφωνείτε;
Παρακαλώ για τις απόψεις σας
Ν.Κυριακου
Ας μην ξεχνάμε ότι ένας πίνακας δυο διαστάσεων είναι ουσιαστικά ένας μονοδιάστατος πίνακας του όποιου τα στοιχεία είναι επίσης μονοδιάστατοι πίνακες.
Οπότε η ταξινόμηση μπορεί να οριστεί μια χαρά αρκεί να ορίσουμε μια σχέση διάταξης μεταξύ των μονοδιάστατων πινάκων-στοιχείων (θα μπορούσαν να είναι οι γραμμές ή οι στήλες).
Δηλαδή θέλουμε μια σχέση διάταξης μεταξύ διανυσμάτων, δηλαδή θα πρέπει να χρησιμοποιήσουμε κάποια από τις υπάρχουσες νόρμες ή να ορίσουμε μια δική μας. Αν ορίσουμε δική μας (για παράδειγμα το μέσο όρο ή το ελάχιστο στοιχείο) θα πρέπει να είμαστε πολύ προσεκτικοί ώστε να πληρεί τις τρεις ιδιότητες για να ορίζει μια μετρική σχέση.
Πολλές φορές η απόφαση της επιλογής κάποιας άσκησης γίνεται με όχι με την λογική του πως να βοηθήσουμε τα παιδιά για το δύσκολο έργο για το οποίο προετοιμάζονται αλλά τι ποιο δύσκολο περίεργο μπορούμε να τους βάλουμε ώστε να αποδείξουμε ότι είμαστε ειδήμονες του μαθήματος που παραδίδουμε και
ας μην καταλαβαίνει κανείς.
Βέβαια πρέπει να θυμόμαστε το ότι κάποιος δεν μας καταλαβαίνει δεν σημαίνει και ότι μας θαυμάζει!!
Προφανώς η παραπάνω απάντηση που έγραψα απευθύνεται σε καθηγητές και όχι σε μαθητές. Απλά απάντησα στο θεωρητικό ερώτημα που έθεσε ο nekis.
evry δεν αναφέρρομαι σε σένα αλλά στο συντάκτη του θέματος.
συγνώμη αν κατάλαβες λάθος.
Νομίζω πως η πιο σωστη λύση ειναι αυτη που λέει ο Αλκης. Ειναι "κλασικό" θεμα Δομων Δεδομένων, δηλ. το πώς αποθηκευονται οι δισδιάστατοι πίνακες στη μνημη του ΗΥ, δηλ. σαν μονοδιάστατοι κατα γραμμές.
Αρα σε εναν πίνακα ΜχΝ το στοιχείο [i,j] αντιστοιχεί στο[(i-1)*N+(j-1)] σε εναν μονοδιάστατο....
Τωρα για ΑΕΠΠ, προφανως ειναι υπερβολικά δύσκολο.....