Ταξινόμηση σε δισδιάστατους πίνακες???

Ξεκίνησε από bookitsa, 14 Μαρ 2008, 04:14:54 ΜΜ

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

pgrontas

Παράθεση από: alkisg στις 16 Μαρ 2008, 10:29:27 ΠΜ
Ο λόγος που τα βάζεις σε δισδιάστατο ορίζεται από το πρόβλημα, όχι από την ταξινόμηση. Η ταξινόμηση είναι απλά ένα μικρό κομμάτι του όλου προβλήματος, δεν είναι αυτοσκοπός.
Σε αυτό συμφωνώ - πώς ήρθαμε στο συμπέρασμα αυτό από διαφορετικούς δρόμους είναι περίεργο ;D

Παράθεση από: alkisg στις 16 Μαρ 2008, 10:29:27 ΠΜ
Εσύ λοιπόν θα μετέτρεπες το δισδιάστατο σε μονοδιάστατο, θα έκανες ταξινόμηση, και στη συνέχεια θα τον ξαναέκανες δισδιάστατο για να τους τον επιστρέψεις.
Εγώ θα ταξινομούσα απευθείας το δισδιάστατο.
Δεν θεωρώ ότι η μετατροπή ΔΙΣ->ΜΟΝ->ΤΑΞ->ΔΙΣ είναι ευκολοσυντήρητη, ούτε καν από αυτόν που έγραψε τον κώδικα. ΥΓ: και αυτό χακεριά είναι (με αρνητική όμως επίδραση στην απόδοση - σε σχέση με αυτήν που πρότεινες στην polar ταξινόμηση)

Παράθεση από: alkisg στις 16 Μαρ 2008, 10:29:27 ΠΜ
Η αντίρρησή σου ποια από τις δύο είναι;
α) Ότι ο δικός σου κώδικας θα είναι πιο λογικός/ευκολοδιάβαστος από το δικό μου;
β) Ή ότι η εταιρία έκανε λάθος και δεν έπρεπε να χρησιμοποιεί δισδιάστατο στο κυρίως πρόγραμμα;
Η αντίρρηση μου είναι στο Β. Δεν θα έπρεπε να χρησιμοποιηθεί δισδιάστατος εφόσον το πρόβλημα εμπεριέχει και ταξινόμηση.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

pgrontas

Παράθεση από: alkisg στις 16 Μαρ 2008, 11:40:07 ΠΜ
Υ.Γ. για το κλασσικό puzzle που παίζαμε μικροί,


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

Αυτό το πρόβλημα οπτικά μόνο έχει δισδιάστατη αναπαράσταση - τα δεδομένα δεν σημαίνουν τίποτα.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

alkisg

Όταν όμως ήθελες να δεις ποια κομμάτια μπορείς να κινήσεις, στο δισδιάστατο θα κοιτούσες τα
A[i-1,j], A[i+1,j], A[i,j-1], A[i,j+1]
όπου i,j η θέση της τρύπας (που στον κώδικα θα εκφραζόταν με μηδενικό). Το +-1 εδώ προφανώς εκφράζει προηγούμενη ή επόμενη γραμμή/στήλη. Κι αν ήθελες να ελέγξεις για τοίχωμα θα έλεγες αν i=1 ή i=N.

Αν το έκανες με μονοδιάστατο θα έπρεπε να κοιτάς τα κομμάτια
A[i-1], A[i+1], A[i-N], A[i+N]
όπου πλέον i είναι η θέση της τρύπας στο μονοδιάστατο.

Ουσιαστικά δηλαδή θα μετέτρεπες τις συντεταγμένες του μονοδιάστατου σε συντεταγμένες δισδιάστατου για τις ανάγκες του αλγορίθμου, προσθέτοντας ή αφαιρώντας Ν για να πας στην πάνω ή κάτω γραμμή. Κι αν ήθελες να ελέγξεις για τοίχωμα, θα έπρεπε να παίρνεις (i-1) mod N + 1 και (i-1) div N + 1 για να δεις αν είναι 1 ή Ν.

Δεν είναι πολύ πιο λογικό να αναπαρασταθεί απευθείας με δισδιάστατο;

pgrontas

Παράθεση από: alkisg στις 16 Μαρ 2008, 12:37:06 ΜΜ
Δεν είναι πολύ πιο λογικό να αναπαρασταθεί απευθείας με δισδιάστατο; (χωρίς να το ελέγξω, θεωρώ πολύ πιθανό ότι όλες οι υλοποιήσεις που θα βρούμε αν ψάξουμε στο διαδίκτυο θα χρησιμοποιούν δισδιάστατο).
Και εγώ συμφωνώ, και έτσι θα το έκανα πιθανότατα - αλλά στην περίπτωση αυτή τα περιεχόμενα δεν σημαίνουν τίποτα.
Αυτή είναι η διαφορά μας.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

alkisg

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

Ο δισδιάστατος πίνακας είναι απλά η δομή που βολεύει να χρησιμοποιήσουμε για να λύσουμε το πρόβλημα.
Τα δεδομένα π.χ. θα μπορούσαν να είναι records με τον αριθμό και με handles για bitmaps, ώστε να μπορούν να ζωγραφιστούν οι αντίστοιχες εικόνες του puzzle στην οθόνη του Η/Υ.

edit#2:
Παράθεση από: pgrontas στις 16 Μαρ 2008, 12:08:02 ΜΜ
Παράθεση από: alkisg στις 16 Μαρ 2008, 10:29:27 ΠΜ
Ο λόγος που τα βάζεις σε δισδιάστατο ορίζεται από το πρόβλημα, όχι από την ταξινόμηση. Η ταξινόμηση είναι απλά ένα μικρό κομμάτι του όλου προβλήματος, δεν είναι αυτοσκοπός.
Σε αυτό συμφωνώ - πώς ήρθαμε στο συμπέρασμα αυτό από διαφορετικούς δρόμους είναι περίεργο ;D

Παράθεση από: alkisg στις 16 Μαρ 2008, 10:29:27 ΠΜ
Η αντίρρησή σου ποια από τις δύο είναι;
α) Ότι ο δικός σου κώδικας θα είναι πιο λογικός/ευκολοδιάβαστος από το δικό μου;
β) Ή ότι η εταιρία έκανε λάθος και δεν έπρεπε να χρησιμοποιεί δισδιάστατο στο κυρίως πρόγραμμα;
Η αντίρρηση μου είναι στο Β. Δεν θα έπρεπε να χρησιμοποιηθεί δισδιάστατος εφόσον το πρόβλημα εμπεριέχει και ταξινόμηση.

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

sstergou

Δηλαδή, αυτό που καταλαβαίνω εγώ :

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

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

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

Όσον αφορά το γεγονός ότι οι γραμμές και οι στήλες σημαίνουν κάτι π.χ. στο παράδειγμα με τους φοιτητές :
1η γραμμή - Φοιτητής : Παναγιώτης
2η γραμμή - Φοιτητής : Άλκης

...
1η στήλη - Μάθημα : Δίκτυα
2η στήλη - Μάθημα : Αλγόριθμοι

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

alkisg

Σχετικά με το να "σημαίνουν κάτι" οι γραμμές και οι στήλες (γραμμές = φοιτητές, στήλες = μαθήματα, περιεχόμενα = βαθμοί κτλ):

Όπως είπε και ο Στάθης, αυτό είναι υποπερίπτωση των προβλημάτων που μπορούν να αναπαρασταθούν με δισδιάστατο πίνακα. Δεν είναι υποχρέωση. Μπορούν απλά να σημαίνουν τη γραμμή και τη στήλη, όπως και στην ταξινόμηση φυσαλίδας το i εκφράζει απλά τη στήλη και όχι μαθήματα.

Στην παραπάνω περίπτωση δεν μπορεί να μεταφερθεί ένας βαθμός μιας στήλης (=μάθημα) σε άλλη στήλη. Μάλιστα, δεν μπορεί καν να μεταφερθεί από γραμμή σε γραμμή, παρά μόνο να αλλαχθούν ολόκληρες γραμμές μεταξύ τους. Αυτό ανάγεται σε ταξινόμηση μονοδιάστατου πίνακα εγγραφών (ή παράλληλων πινάκων).
Σε άλλη υποπερίπτωση θα μπορούσαμε να επιτρέπουμε να μετακινηθούν τα στοιχεία σε οποιαδήποτε γραμμή θέλουμε, αλλά να μην αλλάζουν στήλη. Αυτό ανάγεται σε ξεχωριστές ταξινομήσεις Ν μονοδιάστατων πινάκων.
Και φυσικά θα μπορούσαμε (ανάλογα πάντα με το πρόβλημα) να επιτρέπουμε να μετακινηθούν οπουδήποτε. Αυτό είναι η πιο γενική περίπτωση ταξινόμησης δισδιάστατου, χωρίς φυσικά αυτό να σημαίνει ότι οι άλλες περιπτώσεις δεν είναι ταξινομήσεις δισδιάστατου.

Για να βρούμε φυσικό παράδειγμα για την τρίτη περίπτωση, θα πρέπει και οι στήλες και οι γραμμές να εκφράζουν το ίδιο πράγμα. Π.χ. ομάδες και ομάδες. Θέση puzzle και θέση puzzle. Όχι όμως μαθήματα-φοιτητές, γιατί τότε δεν μπορούμε να κάνουμε αλλαγή στήλης.

Παναγιώτη, ένα τέτοιο παράδειγμα θα σε έπειθε; Να υπάρχει και ένας φυσικός τίτλος των γραμμών/στηλών πέρα από το "δίνεται ένας πίνακας με αριθμούς";

pgrontas

Παράθεση από: alkisg στις 16 Μαρ 2008, 03:47:42 ΜΜ
Στην παραπάνω περίπτωση δεν μπορεί να μεταφερθεί ένας βαθμός μιας στήλης (=μάθημα) σε άλλη στήλη. Μάλιστα, δεν μπορεί καν να μεταφερθεί από γραμμή σε γραμμή, παρά μόνο να αλλαχθούν ολόκληρες γραμμές μεταξύ τους. Αυτό ανάγεται σε ταξινόμηση μονοδιάστατου πίνακα εγγραφών (ή παράλληλων πινάκων).
Αυτό πρέπει να το έχω πει καμιά 10αριά φορές  ;D

Παράθεση από: alkisg στις 16 Μαρ 2008, 03:47:42 ΜΜ
Σχετικά με το να "σημαίνουν κάτι" οι γραμμές και οι στήλες (γραμμές = φοιτητές, στήλες = μαθήματα, περιεχόμενα = βαθμοί κτλ):

Όπως είπε και ο Στάθης, αυτό είναι υποπερίπτωση των προβλημάτων που μπορούν να αναπαρασταθούν με δισδιάστατο πίνακα. Δεν είναι υποχρέωση. Μπορούν απλά να σημαίνουν τη γραμμή και τη στήλη, όπως και στην ταξινόμηση φυσαλίδας το i εκφράζει απλά τη στήλη και όχι μαθήματα.
Η γραμμή και η στήλη είναι αποτέλεσμα της σημασίας.
Αν δεν σημαίνουν τίποτα γιατί να χρησιμοποίησεις δισδιάστατο-ας τα έχει χύμα - σε μονοδιάστατο.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

sstergou

Παράθεση από: pgrontas στις 16 Μαρ 2008, 04:16:23 ΜΜ
Αν δεν σημαίνουν τίποτα γιατί να χρησιμοποίησεις δισδιάστατο-ας τα έχει χύμα - σε μονοδιάστατο.

Γιατί να χρησιμοποιήσεις 50 μονοδιάστατους 10 στοιχείων (φοιτητές - μαθήματα) και όχι δισδιάστατο με 50 γραμμές και 10 στήλες. Γιατί να βάλεις αυτόν το περιορισμό;

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

Άμα είναι έτσι ο μονοδιάστατος πίνακας ο οποίος εκφράζει τους βαθμούς ενός φοιτητή σε 10 μαθήματα δεν πρέπει να ταξινομείται γιατί αλλάζει η σειρά των μαθημάτων. :)

Στο παράδειγμα του ʼλκη με τον παιχνίδι  οι γραμμές και οι στήλες σημαίνουν κάτι
Η 1η γραμμή του πίνακα ανιστοιχεί στην 1η γραμμή του παιχνιδιού, η 1η στήλη στην 1η στήλη του παιχνιδιού κοκ.

Χρειαζόμαστε κάτι παραπάνω από αυτό για να χρησιμοποιήσουμε δισδιάστατο;

pgrontas

Παράθεση από: sstergou στις 16 Μαρ 2008, 04:46:51 ΜΜ
Γιατί η ταξινόμηση των βαθμών στον μονοδιάστατο έχει νόημα και δεν έχει στον δισδιάστατο; Ποια είναι η διαφορά; Αν μπορώ να αντιμεταθέσω στοιχεία στον μονοδιάστατο γιατί να μην μπορώ να αντιμεταθέσω στοιχεία της ίδιας γραμμής στον δισδιάστατο; Και στην συνέχεια να αντιμεταθέσω και ολόκληρες γραμμές αν θέλω. Αυτή η αναδιάταξη δεν είναι μια ταξινόμηση;
Άμα είναι έτσι ο μονοδιάστατος πίνακας ο οποίος εκφράζει τους βαθμούς ενός φοιτητή σε 10 μαθήματα δεν πρέπει να ταξινομείται γιατί αλλάζει η σειρά των μαθημάτων

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

Νομίζω ότι έχουμε μπει σε endless loop.
Δυστυχώς ούτε έχω πειστεί, αλλά ούτε σας έχω πείσει. Δεν πειράζει - δεν χρειάζεται να συμφωνούμε σε όλα - παρόλα αυτά η συζήτηση ήταν άκρως ενδιαφέρουσα.
Πάντως νομίζω ότι το καλύτερο παράδειγμα για το πού ορίζεται η ταξινόμηση, το δίνουν τα περισσότερα βιβλία αλγορίθμων και δομών δεδομένων, που στην ταξινόμηση αναφέρονται σε μονοδιάστατες δομές (πίνακες, λίστες).
Αυτό δεν νομίζω ότι είναι τυχαίο, ούτε παράλειψη.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

alkisg

#40
Παναγιώτη αν έχεις όρεξη επίτρεψέ μου να επιμείνω λίγο, γιατί νομίζω ότι υπάρχουν περιπτώσεις που δεν συζητήσαμε και θα ήθελα να ακούσω τη γνώμη σου γι' αυτές.

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

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

Η μονοδιάστατη version:
Φτιάξτε μια λίστα με τους μαθητές μιας τάξης, ταξινομημένη ανά βαθμολογία. Θεωρούμε ότι υπάρχουν Ν μαθητές, όπου 1 <= Ν <= 30, και το Ν θα μας το δώσει ο χρήστης.

Λύση: δηλώνουμε ένα πίνακα με 30 βαθμούς και έναν παράλληλο ακόμα με 30 ονόματα. Διαβάζουμε το Ν από το χρήστη, διαβάζουμε τα δεδομένα και κάνουμε κλασσική ταξινόμηση με παράλληλο πίνακα.

Η δισδιάστατη version:
Ένα σχολείο έχει Μ τμήματα, 1 <= Μ <= 10, με Ν μαθητές το καθένα, 1 <= Ν <= 30.
α) Για κάθε τμήμα κάντε λίστα ταξινομημένη ανά βαθμολογία
β) (εδώ ζητάμε κι άλλα πράγματα, π.χ. τους 3 καλύτερους κάθε τμήματος, απλά και μόνο για να υποχρεώσουμε τον προγραμματιστή να θυμάται τους βαθμούς και να μην μπορεί να χρησιμοποιήσει έναν μόνο πίνακα Ν στοιχείων)...

Λύση: Δηλώνουμε δύο δισδιάστατους ΜxN, έναν για τους βαθμούς και έναν παράλληλο για τα ονόματα.
Διαβάζουμε τον αριθμό τμημάτων Μ,
Για j από 1 μέχρι Μ
  Διαβάζουμε το Ν
  Διαβάζουμε τα ονόματα και τους βαθμούς και τα βάζουμε στη στήλη Μ των δισδιάστατων πινάκων,
  Ταξινομούμε τη στήλη Μ
κτλ κτλ



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

Η ερώτηση είναι, θεωρείς το παραπάνω παράδειγμα ταξινόμηση δισδιάστατου ή όχι; Κι αν όχι, γιατί; Πώς αλλιώς θα μπορούσε να λυθεί σε ΓΛΩΣΣΑ; (με χακιά γίνεται, χρησιμοποιείς ένα μόνο μονοδιάστατο με ΝxM στοιχεία και κάνεις αλλαγή συντεταγμένων από συντεταγμένες δισδιάστατου, αλλά νομίζω συμφωνούμε ότι γι' αυτό βγήκαν οι δισδιάστατοι, για να μην κάνουμε τέτοιες χακιές).


Υ.Γ. η ταξινόμηση και στο σχολικό βιβλίο της ΑΕΠΠ και στη wikipedia δεν ορίζεται σε πίνακες, αλλά σε sets ή σε λίστες, δηλαδή απλά σε διατεταγμένα στοιχεία.

pgrontas

Παράθεση από: alkisg στις 17 Μαρ 2008, 08:54:08 ΠΜ
Η τρίτη ...υποπερίπτωση ταξινόμησης δισδιάστατου όπως την είπα παραπάνω είναι να μετακινούνται τα στοιχεία οπουδήποτε στον πίνακα. Σ' αυτό δεν βρήκα καλό παράδειγμα με "σημασία" στις γραμμές και στις στήλες (π.χ. μαθητές/βαθμοί), αν βρω θα ποστάρω. Δεν κατάλαβα όμως αν στα παραδείγματα χωρίς "σημασία" που έδωσα, θα έκανες τελικά ταξινόμηση δισδιάστατου ή όχι.
Στις περιπτώσεις που τα δεδομένα δεν έχουν σημασία, ουσιαστικά πρόκειται απλά για ένα σύνολο στοιχείων, το οποίο μπορεί να ταξινομηθεί.
Η δισδιάστατη δομή έχει μόνο χωρική έννοια.


Παράθεση από: alkisg στις 17 Μαρ 2008, 08:54:08 ΠΜ
Εδώ ακριβώς είναι που θέλω να δώσω ένα παράδειγμα, στο οποίο να μην ξέρουμε εκ των προτέρων πόσους μονοδιάστατους θα χρειαστούμε, οπότε να αναγκαστούμε να χρησιμοποιήσουμε και να ταξινομήσουμε δισδιάστατο.
Εφόσον δεν ξέρεις πόσες στήλες θα βάλεις ο δισδιάστατος κάπου χαλάει νομίζω.


Παράθεση από: alkisg στις 17 Μαρ 2008, 08:54:08 ΠΜ
Η ερώτηση είναι, θεωρείς το παραπάνω παράδειγμα ταξινόμηση δισδιάστατου ή όχι;
Για μένα είναι M ταξινομήσεις μονοδιάστατων.

Παράθεση από: alkisg στις 17 Μαρ 2008, 08:54:08 ΠΜ
Υ.Γ. η ταξινόμηση και στο σχολικό βιβλίο της ΑΕΠΠ και στη wikipedia δεν ορίζεται σε πίνακες, αλλά σε sets ή σε λίστες, δηλαδή απλά σε διατεταγμένα στοιχεία.
Ο μονοδιάστατος πίνακας είναι ο πιο κοντινός συγγενής αυτών στην ΑΕΠΠ.

Για μένα είναι περισσότερο αποδεκτό να 'στερήσεις την ερμηνεία' των δεδομένων από μονοδιάστατο (βλέποντας τα δηλαδή ως λίστα upd:με προσπέλαση Ο(1)) παρά από δισδιάστατο (Ο δισδιάστατος θεωρώ πρέπει να έχει κάποιον ειδικό λόγο ύπαρξης - την επιπλέον πληροφορία που προσφέρουν οι δύο διαστάσεις)
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

alkisg

Παράθεση από: pgrontas στις 17 Μαρ 2008, 09:57:51 ΠΜ
Στις περιπτώσεις που τα δεδομένα δεν έχουν σημασία, ουσιαστικά πρόκειται απλά για ένα σύνολο στοιχείων, το οποίο μπορεί να ταξινομηθεί.
Η δισδιάστατη δομή έχει μόνο χωρική έννοια.
Επιφυλάσσομαι μέχρι να βρω σχετικό παράδειγμα, αλλά και μόνο χωρική έννοια να έχουν, αυτό δεν αναιρεί το γεγονός ότι χρειαζόμαστε ταξινόμηση δισδιάστατου.

Παράθεση από: pgrontas στις 17 Μαρ 2008, 09:57:51 ΠΜ
Εφόσον δεν ξέρεις πόσες στήλες θα βάλεις ο δισδιάστατος κάπου χαλάει νομίζω.
Όχι, αυτό είναι λάθος.
Σε μονοδιάστατο πάλι βάζουμε άνω όριο: μέχρι 30 μαθητές.
Σε δισδιάστατο πάλι βάζουμε άνω όριο: μέχρι 10 τμήματα.
Είναι ακριβώς το ίδιο πράγμα, απλά σε μία δεύτερη διάσταση.

Παράθεση από: pgrontas στις 17 Μαρ 2008, 09:57:51 ΠΜ
Για μένα είναι M ταξινομήσεις μονοδιάστατων.
ΟΚ, δώσε μια λύση της παραπάνω άσκησης σε ΓΛΩΣΣΑ. Δε νομίζω ότι γίνεται!
(πέρα από τη χακιά του να χρησιμοποιήσεις ΕΝΑΝ μόνο μονοδιάστατο με ΝxΜ στοιχεία).

Παράθεση από: pgrontas στις 17 Μαρ 2008, 09:57:51 ΠΜ
(Ο δισδιάστατος θεωρώ πρέπει να έχει κάποιον ειδικό λόγο ύπαρξης - την επιπλέον πληροφορία που προσφέρουν οι δύο διαστάσεις)
Η επιπλέον πληροφορία στο παραπάνω παράδειγμα είναι τα τμήματα.

pgrontas

Παράθεση από: alkisg στις 17 Μαρ 2008, 10:05:44 ΠΜ
ΟΚ, δώσε μια λύση της παραπάνω άσκησης σε ΓΛΩΣΣΑ. Δε νομίζω ότι γίνεται!
(πέρα από τη χακιά του να χρησιμοποιήσεις ΕΝΑΝ μόνο μονοδιάστατο με ΝxΜ στοιχεία).
Εφόσον κάνεις το ίδιο πράγμα Μ φορές, δεν καταλαβαίνω γιατί δεν μπορεί να γίνει.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

alkisg

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

Έτσι θα αναγκαστείς να δηλώσεις Μ μονοδιάστατους πίνακες. Δεν μπορείς όμως να δηλώσεις Μ, πρέπει να δηλώσεις συγκεκριμένο αριθμό.
Έτσι δηλώνεις 10 μονοδιάστατους πίνακες, τον Α1, τον Α2, τον Α3 κτλ. Δεν θα τους χρησιμοποιήσεις όμως όλους, αλλά τους Μ πρώτους από αυτούς.

Πώς μπορείς όμως να κάνεις επανάληψη με διαφορετικά ονόματα μεταβλητών; Δεν μπορείς. Χρειάζεσαι δισδιάστατο πίνακα.

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