Συγχωνευση δισδιαστατου

Ξεκίνησε από kiro, 10 Μαρ 2006, 02:16:35 ΜΜ

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

kiro

Γεια σας!!!!

Θα ήθελα να ρωτήσω αν μπορεί να γίνει συγχώνευση σε δυο δισδιάστατους ταξινομημένους πίνακες, θα ελέγχουμε γραμμή προς γραμμή? Μήπως θα μπορούσατε να μου δώσετε ένα παράδειγμα?

Ευχαριστώ…


P.Tsiotakis


Υπάρχουν δισδιάστατοι ταξινομημένοι πίνακες ;


alkisg

Ε, ναι, είναι λίγο τραβηγμένο... :)

Γενικά ότι γίνεται σε μονοδιάστατο πίνακα μπορεί να γίνει και σε δισδιάστατο. Χρειάζεται όμως να γίνει μετατροπή των δύο δεικτών (ι, κ) του δισδιάστατου σε έναν (ι), αυτόν του αντίστοιχου μονοδιάστατου.

Δες το αντίστοιχο θέμα για την ταξινόμηση δισδιάστατου πίνακα. Χρησιμοποιώντας τους ίδιους τύπους μετατροπής δεικτών μπορείς να κάνεις συγχώνευση σε δισδιάστατους πίνακες σαν να ήταν μονοδιάστατοι.

evry

 Για ποιο λόγο να κάνουν οι μαθητές συγχώνευση διδιάστατων πινάκων; Ποιος είναι ο σκοπός αυτής της άσκησης; Αν θέλεις να τους βάλεις λίγο πιο δύσκολες ασκήσεις με πίνακες άνοιξε ένα βιβλίο γραμμικής άλγεβρας Α' έτους θετικής σχολής και από εκεί μπορείς να βγάλεις άπειρες ασκήσεις: διαγώνιοι, τριδιαγώνιοι, συμμετρικοί, ανάστροφοι και άλλοι πίνακες. Υπάρχει και το μαγικό τετράγωνο που έχει το τετράδιο του μαθητή.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

EleniK

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

gpapargi

Εύκολα καταλαβαίνει κανείς ότι μπορούμε να πάρουμε οποιοδήποτε αλγόριθμο των μονοδιάστατων πινάκων και να ρωτήσουμε αν μπορούμε να τον υλοποιήσουμε για πίνακες 2 διαστάσεων.

Αυτό που θα ήθελα να πω είναι ότι τέτοια προβλήματα αν και μπορουν να λυθούν (όπως λέει ο Άλκης),  θα πρέπει να αναρωτηθούμε αν έχουν πάντα νόημα.

Στο μονοδιάστατο πίνακα τα στοιχεία έχουν μια φυσική διάταξη Αυτό που έχει μικρότερο δείκτη προηγείται. Σε πίνακα 2 διαστάσεων η διάταξη δεν είναι ορισμένη. Θα πρέπει κάπως να οριστεί. Πιο στοιχείο προηγείται στη διάταξη έτσι ώστε εκεί να βάλουμε το δεύτερο εγαλύτερο; το Α[2,1] ή το Α[1,2];

Μπορούμε να σκεφτούμε και το γεωμετρικό ανάλογο. Στην ευθεία των πραγματικών κάθε σημείο αντιστοιχεί με ένα αριθμό. Όποιο σημείο είναι πιο αριστερά προηγείται. Στο επίπεδο όμως κάθε σημείο αντιστοιχεί με ένα ζεύγος αριθμών. Τα ζεύγη όμως δεν είναι τοποθετημένα σε σειρά. Πιο προηγείται; Αυτό που είναι πιο αριστερά; Αυτό που είναι πιο κάτω; Αυτό που είναι πιο κοντά την αρχή των αξόνων;

Συνήθως σιωπηλά θεωρούμε το Α[1,2] πριν το Α[2,1]. Υποθέτω πως αυτό γίνεται λόγω του ότι εμείς οι άνθρωποι γράφουμε/διαβάζουμε κείμενο γραμμή γραμμή από πάνω προς τα κάτω.  Και φαντάζομαι πως αυτό γίνεται επειδή τα μάτια μας είναι το ένα δίπλα στο άλλο και έτσι έχουμε ευρύτερο οπτικό πεδίο οριζόντια παρά κάθετα. Αν τα λέω καλά, αν είχαμε τα μάτια μας το ένα κάτω από το άλλο τότε θα διαβάζαμε αυθαίρετα τους πίνακες κατά στήλη.  ;D
Ότι όμως κι αν εφαρμόσουμε στους πίνακες είναι αυθαίρετο.

Ας δούμε και ένα συγκεκριμένο παράδειγμα. ʼς πούμε ότι σε ένα πίνακα 2 διαστάσεων αποθηκεύθουμε τους πόντους που έχει βάλει κάθε παίκτης μιας ομάδας μπάσκετ σε κάθε αγωνιστική. Γιατί να βάλουμε το δεύτερο νούμερο στο Α[1,2] και όχι το Α[2,1];

Τέλος θα ήθελα να σταθώ στον ορισμό της ταξινόμησης που δίνει το βιβλίο στη σελίδα 66. Ορίζει την ταξινόμηση για μονοδιάστατο πίνακα. Η συνήθης αύξουσα ταξινόμηση θεωρεί σαν f  την ταυτοτική συνάρτηση. Δεν ορίζεται όμως η ταξινόμηση για πίνακες 2 διαστάσεων.

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

Λάμπρος Μπουκουβάλας

γίνεται ταξινόμηση φυσαλίδας ανά γραμμή ή ανά στήλη σε 2 διαστάσεις. αλλά αν ακολουθήσει και συγχώνευση, νομίζω ότι ξεφεύγει λιγάκι...
Λάμπρος Μπουκουβάλας
MSc - MRes

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται...

nekis

Θα προσπαθήσω να θέσω ένα θεωρητικό σχετικό ερώτημα.
Η ταξινόμηση είναι κατά τον ορισμό του βιβλίου μια μετάθεση στοιχείων δωθείσης μιας συνάρτησης f κλπ.
Σε μια άσκηση "ταξινόμησης" σε διασδιάστατο θα πρέπει να μπορούμε να ορίσουμε μια τέτοια συνάρτηση διάταξης.
Αυτό δεν είναι προφανές και πιθανώς και μη υλοποιήσιμο. Γι αυτό δεν μπορούμε να μιλήσουμε για ταξινόμηση αλλά για μια εμφάνιση του δισδιάστατου πίνακα.
Συμφωνείτε;
Παρακαλώ για τις απόψεις σας
Ν.Κυριακου

evry

Ας μην ξεχνάμε ότι ένας πίνακας δυο διαστάσεων είναι ουσιαστικά ένας μονοδιάστατος πίνακας του όποιου τα στοιχεία είναι επίσης μονοδιάστατοι πίνακες.
   Οπότε η ταξινόμηση μπορεί να οριστεί μια χαρά αρκεί να ορίσουμε μια σχέση διάταξης μεταξύ των μονοδιάστατων πινάκων-στοιχείων (θα μπορούσαν να είναι οι γραμμές ή οι στήλες).
   Δηλαδή θέλουμε μια σχέση διάταξης μεταξύ διανυσμάτων, δηλαδή θα πρέπει να χρησιμοποιήσουμε κάποια από τις υπάρχουσες νόρμες ή να ορίσουμε μια δική μας. Αν ορίσουμε δική μας (για παράδειγμα το μέσο όρο ή το ελάχιστο στοιχείο) θα πρέπει να είμαστε πολύ προσεκτικοί ώστε να πληρεί τις τρεις ιδιότητες για να ορίζει μια μετρική σχέση.
       
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

xaidi

Πολλές φορές η απόφαση της επιλογής κάποιας άσκησης γίνεται με όχι με την λογική του πως να βοηθήσουμε τα παιδιά για το δύσκολο έργο για το οποίο προετοιμάζονται αλλά τι ποιο δύσκολο περίεργο μπορούμε να τους βάλουμε ώστε να αποδείξουμε ότι είμαστε ειδήμονες του μαθήματος που παραδίδουμε και…ας μην καταλαβαίνει κανείς.
Βέβαια πρέπει να θυμόμαστε το ότι κάποιος δεν μας καταλαβαίνει δεν σημαίνει και ότι μας θαυμάζει!!
Ευχαριστώ,

evry


Προφανώς η παραπάνω απάντηση που έγραψα απευθύνεται σε καθηγητές και όχι σε μαθητές. Απλά απάντησα στο θεωρητικό ερώτημα που έθεσε ο nekis.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

xaidi

evry δεν αναφέρρομαι σε σένα αλλά στο συντάκτη του θέματος.
συγνώμη αν κατάλαβες λάθος.
Ευχαριστώ,

dimitrios67

Νομίζω πως η πιο σωστη λύση ειναι αυτη που λέει ο Αλκης. Ειναι "κλασικό" θεμα Δομων Δεδομένων, δηλ. το πώς αποθηκευονται οι δισδιάστατοι πίνακες στη μνημη του ΗΥ, δηλ. σαν μονοδιάστατοι κατα γραμμές.
Αρα σε εναν πίνακα ΜχΝ το στοιχείο [i,j] αντιστοιχεί στο[(i-1)*N+(j-1)] σε εναν μονοδιάστατο....
Τωρα για ΑΕΠΠ, προφανως ειναι υπερβολικά δύσκολο.....