Αποστολέας Θέμα: Ερώτηση στους πίνακες (θεωρητική)  (Αναγνώστηκε 6486 φορές)

kiro

  • Βετεράνος
  • ****
  • Μηνύματα: 52
  • Γράψτε το προσωπικό σας σλόγκαν!
Ερώτηση στους πίνακες (θεωρητική)
« στις: 19 Ιαν 2006, 01:16:54 μμ »
Να ρωτήσω κάτι; Μάλλον πολύ απλό απλά επειδή διδάσκω πρώτη φορά θέλω να είμαι σίγουρη .. Η αναζήτηση (σειριακή ή δυαδική), ταξινόμηση , Bubble Sort, στοίβα και ουρά ισχύουν μόνο σε μονοδιάστατους πίνακες? Σε δισδιάστατους τι κάνουμε?
« Τελευταία τροποποίηση: 19 Ιαν 2006, 01:41:05 μμ από alkisg »

pian

  • Νέος
  • *
  • Μηνύματα: 4
  • Γράψτε το προσωπικό σας σλόγκαν!
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #1 στις: 19 Ιαν 2006, 01:26:47 μμ »
Μπορείς να κάνεις αναζήτηση σε δισδιάστατο.
 1. Το βρίσκεις και φεύγεις.  (ΟΣΟ εμφωλευμένη και λογική μεταβήτή )
 2. Πλήρης σάρωση του πίνακα. (ΓΙΑ εμφωλευμένο)
Και ταξινόμηση. (ανά γραμμή ή ανά στήλη)
« Τελευταία τροποποίηση: 19 Ιαν 2006, 01:43:18 μμ από alkisg »

pian

  • Νέος
  • *
  • Μηνύματα: 4
  • Γράψτε το προσωπικό σας σλόγκαν!
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #2 στις: 19 Ιαν 2006, 01:33:53 μμ »
1. Το βρίσκεις και φεύγεις.  (ΟΣΟ εμφωλευμένο και λογική μεταβλητή )
Υ.Γ. Συγχαρητήρια   στους :  Παναγιώτη ,  Σέργιο για την πρωτοβουλία τους. (Για την οργάνωση και τη συντήρηση του παρόντος forum).
     
 
« Τελευταία τροποποίηση: 19 Ιαν 2006, 01:42:38 μμ από alkisg »

P.Tsiotakis

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3305
  • agent romanoff you miss me?
    • P.Tsiotakis
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #3 στις: 19 Ιαν 2006, 05:34:29 μμ »
- Η στοίβα και η ουρά είναι δομές δεδομένων που υλοποιούνται με τη χρήση μονοδιάστατων πινάκων (άρα στατικές)

- Η ταξινόμηση μπορεί να πραγματοποιηθεί μόνο σε μονοδιάστατο πίνακα ή σε κάποια στήλη/γραμμή δισδιάστατου (που ουσιαστικά αποτελεί μονοδιάστατο πίνακα)

- Η αναζήτηση προφανώς μπορεί να πραγματοποιηθεί και σε δισδιάστατο αλλά όχι με την μορφή που έχει στην παράγραφο 3.6 του σχολικού βιβλίου. Πρέπει να χρησιμοποιηθούν δυο δόμές επανάληψης Όσο. (Θα ήταν ένα ωραίο θέμα για τις εξετάσεις ! )  ή όπως επισημαίνει ο/η pian μπορεί να γίνει και με τη χρήση Για.

ΥΓ: 1. pian ευχαριστώ για τα καλά σου λόγια, αλλά το στέκι έχει δημιουργήσει και συντηρεί ο συνάδελφος Άλκης Γεωργόπουλος, το οποίο άνθισε από τη στιγμή που κλείδωσε το πάλαι ποτέ κραταιό www.sch.gr/forums και τα συγχαρητήρια ανήκουν σε αυτόν. Ιδιαίτερη μνεία επίσης όφείλουμε στον διαχειριστή του forum Φανίκο Σέργιο για το χρόνο που αφιερώνει.
Εγώ δεν είμαι παρά ένας απλός δεινόσαυρος με παλαιολιθικές απόψεις και εκλεπτισμένο χιούμορ
2. Μπορείς να σβήσεις κάποιο μήνυμά σου ή να το αλλάξεις χρησιμοποιώντας τις αντίστοιχες επιλογές...

Με εκτίμηση,

kinik

  • Επισκέπτης
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #4 στις: 20 Ιαν 2006, 08:32:23 πμ »
Σε δισδιάστατο πίνακα πιστεύω ότι μπορούν να γίνουν τα εξής σε ότι αφορά την ταξινόμηση και την αναζήτηση.
1) Ταξινόμηση με βάση κάποια γραμμή ή στήλη όπως είπε και ο pian.
2) Αναζήτηση με σάρωση ολόκληρου του πίνακα. (Αναζήτηση με εμφωλευμένη ΓΙΑ).
3) Αναζήτηση σε ολόκληρο το πίνακα για μία τιμή (Εμφωλευμένη ΟΣΟ).
4) Αναζήτηση σε κάθε γραμμή ή σε κάθε στήλη για μία τιμή. Εξωτερική επανάληψη ΓΙΑ και εσωτερικά (δηλαδή σε κάθε γραμμή ή στήλη) αναζήτηση με ΟΣΟ.

P.Tsiotakis

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3305
  • agent romanoff you miss me?
    • P.Tsiotakis
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #5 στις: 20 Ιαν 2006, 09:01:33 πμ »

Ή αναζήτηση σε ΜΙΑ γραμμή ή στήλη, του πίνακα για μία τιμή οπότε χρησιμοποιείται ο αλγόριθμος του βιβλίου με προσοχή στα σημεία που αναφέρεται ο πίνακας

kyramas

  • Οπαδός
  • **
  • Μηνύματα: 10
  • Γράψτε το προσωπικό σας σλόγκαν!
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #6 στις: 20 Ιαν 2006, 02:44:08 μμ »
Σε ότι αφαρά την ταξινόμηση πινάκων θέλω να παρατηρήσω τα εξής:
1)Οι πίνακες 2-διαστάσεων "κάθονται" στη μνήμη (που είναι μονοδιάστατη) σαν μονοδιάστατοι πίνακες δηλ. σε μια σειρά συνεχόμενων θέσεων μνήμης.
2) Οι πίνακες 2-διαστάσεων αποθηκεύονται κατά γραμμή στη μνήμη δηλ. Η 1η γραμμή στις πρώτες θέσεις μνήμης, ακολουθόύν τα στοιχεία της 2ης γραμμής κ.ο.κ
3) Ο συνηθισμένος τρόπος προσπέλασης των στοιχείων πίνακα 2-διαστάσεων είναι κατά γραμμή όπως και η "φυσική" του αποθήκευση και συνεπώς η εμφάνιση των στοιχείων με αυτό τον τρόπο σε ένα "συνολικά" ταξινομημένο πίνακα εμφανίζει όλα τα στοιχεία του πίνακα σε μια αύξουσα ή φθίνουσα σειρά.
3) Έχει λοιπόν νόημα να δούμε την ταξινόμηση πίνακα 2-διαστάσεων συνολικά και όχι μόνο κατά γραμμή ή στήλη.
έστω λοιπόν πίνακας Α[Ν,Μ]

ΠΛΗΘΟΣ<--Ν*Μ
ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ ΠΛΗΘΟΣ
   ΓΙΑ Κ ΑΠΟ ΠΛΗΘΟΣ ΜΕΧΡΙ Ι ΜΕ ΒΗΜΑ -1
 ΤΡ_ΓΡ<-- Κ div Μ + 1
 ΤΡ_ΣΤ<-- Κ mod Μ
 ΑΝ ΤΡ_ΣΤ=0 ΤΟΤΕ
   ΤΡ_ΣΤ<--Μ
   ΤΡ_ΓΡ<-- ΤΡ_ΓΡ-1
 ΤΕΛΟΣ_ΑΝ
 ΠΡ_ΓΡ<-- ΤΡ_ΓΡ
 ΠΡ_ΣΤ<-- ΤΡ_ΣΤ - 1
 ΑΝ ΠΡ_ΣΤ=0 ΤΟΤΕ
     ΠΡ_ΣΤ<--Μ
     ΠΡ_ΓΡ<--ΤΡ_ΓΡ - 1
 ΤΕΛΟΣ_ΑΝ
 ΑΝ Α[ΤΡ_ΓΡ, ΤΡ_ΣΤ] < Α[ΠΡ_ΓΡ,ΠΡ_ΣΤ] ΤΟΤΕ
    Τ<-- Α [ΠΡ_ΓΡ, ΠΡ_ΣΤ]
    Α[ΠΡ_ΓΡ, ΠΡ_ΣΤ]<-- Α[ΤΡ_ΓΡ, ΤΡ_ΣΤ]
    Α[ΤΡ_ΓΡ, ΤΡ_ΣΤ]<-- Τ
 ΤΕΛΟΣ_ΑΝ
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

kyramas

  • Οπαδός
  • **
  • Μηνύματα: 10
  • Γράψτε το προσωπικό σας σλόγκαν!
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #7 στις: 21 Ιαν 2006, 11:13:59 πμ »
Σε ότι αφορά τη σειριακή αναζήτηση σε δισδιάστατο πίνακα προφανώς και μπορούμε να την υλοποιήσουμε χωρίς εμφωλευμένες δομές επανάληψης. Θεωρώ "κοντινό" τρόπος σε σχέση με τον αλγόριθμο του Σχολ. βιβλίου την παρακάτω προσέγγιση
έχουμε πίνακα Α[Ν,Μ]

ΓΡ<- 0
ΣΤ<- 0
DONE <- ΨΕΥΔΗΣ
Ι <- 1
Κ <- 1
ΟΣΟ DONE=ΨΕΥΔΗΣ ΚΑΙ Ι<=Ν
ΑΝ Α[Ι,Κ]=key ΤΟΤΕ
  DONE <- ΑΛΗΘΗΣ
 ΓΡ <- Ι
 ΣΤ<- Κ
ΑΛΛΙΩΣ
 Κ<- Κ+1
 ΑΝ Κ>Μ ΤΟΤΕ
 Κ<- 1
 Ι<- Ι+1
 ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

kyramas

  • Οπαδός
  • **
  • Μηνύματα: 10
  • Γράψτε το προσωπικό σας σλόγκαν!
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #8 στις: 23 Ιαν 2006, 11:23:41 πμ »
Θα ήθελα να καταθέσω ένα προβληματισμό για την ερμηνεία του τρόπου προσπέλασης στοιχείων πίνακα.
Για παράδειγμα έστω ο πίνακας Α[5].  
Για να μπορέσει ο μαθητής να κατανοήσει την έμμεση δήλωση 5 απλών μεταβλητών (των στοιχείων δηλ. του πίνακα) έχω ακούσει τη δήλωση, ότι έμμεσα χρησιμοποιούμε 5 μεταβλητές με ονόματα Α|[1], Α[2], κ.λ.π.
Δεν ξέρω συνάδελφοι αν κάποια στιγμή πρέπει να πούμε και την  "ουσία" οτι δηλ. οι αγκύλες [] δεν είναι χαρακτήρας αποδεκτός στη δόμηση ονόματος μεταβλητής, προφανώς και δεν υπάρχει όνομα Α[1] κ.λ.π. αλλά ότι οι αγκύλες [] είναι τελεστής όπως οι αριθμητικοί τελεστές οι λογικοί, κ.λ.π.
Τί λέτε γι'αυτό το θέμα

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #9 στις: 23 Ιαν 2006, 11:30:03 πμ »
Καλημέρα

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

Στον πίνακα 2 διαστάσεων δεν υπάρχει αυθόρμητα μια τέτοια σειρά. Δηλαδή πιο προηγείται; Το α[1,2] ή το α[2,1];
Μπορούμε να ορίσουμε βέβαια τη διάταξη αλλά δε νομίζω σε καμία περίπτωση ότι μπορεί με κάποιο τρόπο να αναδυθεί  διάταξη αυθόρμητα.

Τέλος πάντων αν ζητηθεί κάποιος αλγόριθμος που έχουμε φτιάξει για μονοδιάστατο πίνακα να γίνει και σε πίνακα 2 διαστάσεων έχω να πω εν συντομία τα εξής:


Στις 29/12/2004 κάποιος χρησιμοποιώντας το όνομα «ΠΕΤΡΟΣ» είναι ανοίξει στέκι ένα θέμα με τίτλο «Βοήθεια!!! Διαβάστε παρακάτω». Αυτή τη στιγμή είναι στη σελίδα 6. Ο Πέτρος ήταν φοιτητής στο ανοικτό πανεπιστήμιο και ζήταγε να γίνει κάτι σε 2-D πίνακα. Είχα φτιάξει τότε λοιπόν τους μετασχηματισμούς που σου επιτρέπουν αν έχεις ένα πίνακα μιας διάστασης να τον βλέπεις σαν πίνακα 2 διαστάσεων και αντίστροφα αν έχεις ένα πίνακα 2 διαστάσεων να τον βλέπεις σαν πίνακα μιας διάστασης. Κάνω copy paste το απόσπασμα που είχα γράψει τότε.

«Γενικά αυτό με τον n X m πίνακα είναι λίγο περίεργο. Ο υπολογιστής τον αποθηκεύει σειριακά. Απλά εμείς τον φανταζόμαστε σαν πίνακα 2 διαστάσεων γιατί μας βολεύει. Όμως επειδή η αναζήτηση είναι πιο εύκολη σε πίνακα μιας διάστασης παρά σε πίνακα 2 διαστάσεων, θα έκανα το εξής:
Θα χρησιμοποιούσα πίνακα μιας διάστασης με δείκτη i. Θα υλοποιούσα την αναζήτηση και την καταχώρηση των στοιχείων σε αυτόν. Μέχρι εδώ όλα είναι απλά. Μετά θα έδινα τη δυνατότητα σε οποιονδήποτε να βλέπει τον πίνακα σαν να έχει 2 διαστάσεις. Αν x,y οι συνεταγμένες του πίνακα τότε με ένα σχήμα εύκολα βρίσκουμε ότι  
i=(x-1)*m+y  (1)
Η σχέση (1) μπορεί να διαβαστεί σαν διαιρετέος (i)=διαιρέτης (m) επί πηλίκο (x-1) συν υπόλοιπο (y). Έτσι εύκολα καταλήγουμε στον μετασχηματισμό
x= i div m + 1     (2)
y=i mod m     (3)

Δηλαδή με τη σχέση (1) φαντάζεσαι ένα πίνακα σαν μονοδιάστατο αν τον έχεις σαν δισδιάστατο. Με τις σχέσεις (2),(3) τον φαντάζεσαι σα δισδιάστατο αν τον έχεις σα μονοδιάστατο. Ανάλογα με το τι θέλεις λειτουργείς. Εννοείτε ότι φτιάχνεις συνάρτηση που παίρνει σαν όρισματα τις 2d συνιστώσες και επιστρέφει την 1d.
Πάντως δε βλέπω το λόγο να μπλέξεις με 2 πίνακες. Θα έλεγα ένας είναι αρκετός και με τον κατάλληλο μετασχηματισμό τον φαντάζεσαι σα να έχει 1 ή 2 διαστάσεις.
Και ο υπολογιστής κάπως έτσι λειτουργεί».

Μπορούμε να πούμε με βεβαιότητα ότι κάθε αλγόριθμος που ξέρουμε για πίνακα μιας ή 2 διαστάσεων μπορεί να μεταφερθεί απλά και χωρίς νέα σκέψη και σε πίνακα δύο ή μιας διάστασης αντίστοιχα με τη βοήθεια του μετασχηματισμού. Σχέσεις (1),(2),(3)

Για το θέμα της στοίβας και της ουράς δεν καταλαβαίνω το ερώτημα. Υλοποιείς στοίβα ή ουρά γιατί θέλεις κάποιες συγκεκριμένες λειτουργίες που προβλέπει η δομή. Για ποιο λόγο να υλοποιήσεις στοίβα ή ουρά σε πίνακα 2 διαστάσεων; Πως μπορεί να προκύψει κάτι τέτοιο; Τι αντιστοίχηση με την πραγματικότητα θα έχει το να υλοποιήσεις στοίβα σε πίνακα 2 διαστάσεων; Δε βρίσκω νόημα

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3532
  • to Iterate is human to Recurse divine
Re: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #10 στις: 23 Ιαν 2006, 08:39:11 μμ »
Οι αγκύλες είναι θέμα συντακτικού. Έχουμε επιλέξει να συμβολίζουμε τα στοιχεία των πινάκων έτσι. Στην VB για παράδειγμα είναι με παρενθέσεις.
Επίσης στην C++ μπορώ να γράψω
int *a = new int[100];

int *p=a;
cout << (++p)* << endl;

Ουσιαστικά έχω ορίσει πίνακα αλλά δε χρησιμοποιώ πουθενά αγκύλες.
Η ουσία πιστεύω είναι ότι έχουμε α[1], α[2], α[3], ... μεταβλητές όπως πολύ σωστά είπες. Και αυτές είναι πραγματικές μεταβλητές όπως όλες αφού η λειτουργία και η συμπεριφορά τους είναι ίδια. Το [] είναι θέμα συντακτικού. Θα μπορούσε να είναι άλλος συμβολισμός.

Φυσικά στο παραπάνω που έγραψα οι "μεταβλητές" αποθηκεύονται στον σωρό και όχι στη στοίβα.

Η μόνη διαφορά απλών μεταβλητών και πινάκων είναι στη δήλωση νομίζω, δε συμφωνείς?

Παράθεση
Θα ήθελα να καταθέσω ένα προβληματισμό για την ερμηνεία του τρόπου προσπέλασης στοιχείων πίνακα.
Για παράδειγμα έστω ο πίνακας Α[5].  
Για να μπορέσει ο μαθητής να κατανοήσει την έμμεση δήλωση 5 απλών μεταβλητών (των στοιχείων δηλ. του πίνακα) έχω ακούσει τη δήλωση, ότι έμμεσα χρησιμοποιούμε 5 μεταβλητές με ονόματα Α|[1], Α[2], κ.λ.π.
Δεν ξέρω συνάδελφοι αν κάποια στιγμή πρέπει να πούμε και την  "ουσία" οτι δηλ. οι αγκύλες [] δεν είναι χαρακτήρας αποδεκτός στη δόμηση ονόματος μεταβλητής, προφανώς και δεν υπάρχει όνομα Α[1] κ.λ.π. αλλά ότι οι αγκύλες [] είναι τελεστής όπως οι αριθμητικοί τελεστές οι λογικοί, κ.λ.π.
Τί λέτε γι'αυτό το θέμα

What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Απ: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #11 στις: 19 Φεβ 2014, 11:18:18 πμ »
Καλημέρα

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

Στον πίνακα 2 διαστάσεων δεν υπάρχει αυθόρμητα μια τέτοια σειρά. Δηλαδή πιο προηγείται; Το α[1,2] ή το α[2,1];
Μπορούμε να ορίσουμε βέβαια τη διάταξη αλλά δε νομίζω σε καμία περίπτωση ότι μπορεί με κάποιο τρόπο να αναδυθεί  διάταξη αυθόρμητα.

Τέλος πάντων αν ζητηθεί κάποιος αλγόριθμος που έχουμε φτιάξει για μονοδιάστατο πίνακα να γίνει και σε πίνακα 2 διαστάσεων έχω να πω εν συντομία τα εξής:


Στις 29/12/2004 κάποιος χρησιμοποιώντας το όνομα «ΠΕΤΡΟΣ» είναι ανοίξει στέκι ένα θέμα με τίτλο «Βοήθεια!!! Διαβάστε παρακάτω». Αυτή τη στιγμή είναι στη σελίδα 6. Ο Πέτρος ήταν φοιτητής στο ανοικτό πανεπιστήμιο και ζήταγε να γίνει κάτι σε 2-D πίνακα. Είχα φτιάξει τότε λοιπόν τους μετασχηματισμούς που σου επιτρέπουν αν έχεις ένα πίνακα μιας διάστασης να τον βλέπεις σαν πίνακα 2 διαστάσεων και αντίστροφα αν έχεις ένα πίνακα 2 διαστάσεων να τον βλέπεις σαν πίνακα μιας διάστασης. Κάνω copy paste το απόσπασμα που είχα γράψει τότε.

«Γενικά αυτό με τον n X m πίνακα είναι λίγο περίεργο. Ο υπολογιστής τον αποθηκεύει σειριακά. Απλά εμείς τον φανταζόμαστε σαν πίνακα 2 διαστάσεων γιατί μας βολεύει. Όμως επειδή η αναζήτηση είναι πιο εύκολη σε πίνακα μιας διάστασης παρά σε πίνακα 2 διαστάσεων, θα έκανα το εξής:
Θα χρησιμοποιούσα πίνακα μιας διάστασης με δείκτη i. Θα υλοποιούσα την αναζήτηση και την καταχώρηση των στοιχείων σε αυτόν. Μέχρι εδώ όλα είναι απλά. Μετά θα έδινα τη δυνατότητα σε οποιονδήποτε να βλέπει τον πίνακα σαν να έχει 2 διαστάσεις. Αν x,y οι συνεταγμένες του πίνακα τότε με ένα σχήμα εύκολα βρίσκουμε ότι 
i=(x-1)*m+y  (1)
Η σχέση (1) μπορεί να διαβαστεί σαν διαιρετέος (i)=διαιρέτης (m) επί πηλίκο (x-1) συν υπόλοιπο (y). Έτσι εύκολα καταλήγουμε στον μετασχηματισμό
x= i div m + 1     (2)
y=i mod m     (3)
 
Δηλαδή με τη σχέση (1) φαντάζεσαι ένα πίνακα σαν μονοδιάστατο αν τον έχεις σαν δισδιάστατο. Με τις σχέσεις (2),(3) τον φαντάζεσαι σα δισδιάστατο αν τον έχεις σα μονοδιάστατο. Ανάλογα με το τι θέλεις λειτουργείς. Εννοείτε ότι φτιάχνεις συνάρτηση που παίρνει σαν όρισματα τις 2d συνιστώσες και επιστρέφει την 1d.
Πάντως δε βλέπω το λόγο να μπλέξεις με 2 πίνακες. Θα έλεγα ένας είναι αρκετός και με τον κατάλληλο μετασχηματισμό τον φαντάζεσαι σα να έχει 1 ή 2 διαστάσεις.
Και ο υπολογιστής κάπως έτσι λειτουργεί».

Μπορούμε να πούμε με βεβαιότητα ότι κάθε αλγόριθμος που ξέρουμε για πίνακα μιας ή 2 διαστάσεων μπορεί να μεταφερθεί απλά και χωρίς νέα σκέψη και σε πίνακα δύο ή μιας διάστασης αντίστοιχα με τη βοήθεια του μετασχηματισμού. Σχέσεις (1),(2),(3)

Φτούουου! Δεν το καταλαβαίνω. :-[ :'(
Δεν θα μπορέσω να το διδάξω αυτό.
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 429
  • Real stupidity beats ΑΙ any time
Απ: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #12 στις: 19 Φεβ 2014, 02:57:09 μμ »
Φτούουου! Δεν το καταλαβαίνω. :-[ :'(
Δεν θα μπορέσω να το διδάξω αυτό.

Αυτό που λέει είναι ότι μπορείς πχ να έχεις ένα μονοδιάστατο πίνακα και με κάποια λογική να τον θεωρείς δισδιάστατο. Η "λογικἠ" ουσιαστικά είναι μια συνάρτηση-απεικόνιση από 2D index σε μονοδιάστατο. Δηλαδή, για ένα index i, j θες να έχεις βρίσκεις ένα index k.

Έστω ότι έχεις αυτόν τον πολύ απλό πίνακα :

 |1 2|
 |3 4|

Ο αριθμός 3 έχει index  (1,0). Αριθμούμε από το μηδέν, ie το 1 είναι στην (0,0).

Eμείς θέλουμε είναι να έχουμε  έναν μονοδιάστατο πίνακα, αυτόν :

|1 2 3 4|

και να μπορούμε να πούμε ότι το (1,0) είναι στην ουσία το  index (2).  Για να το επιτύχουμε αυτό χρησιμοποιούμε μια αναπαράσταση που ονομάζεται row major order.


Μπορείς να παρατηρήσεις ότι το index του 3 στον μονοδιάστατο ουσιαστικά η γραμμή που βρίσκεται στον δισδιάστατο επί των αριθμό των στηλών του δισδιάστατου συν τη στήλη στην οποία βρίσκεται στον μονοδιάστατο. ( i * αριθμός_στηλών + j)

Αφού έχουμε 2 στήλες, ο τύπος με αντικατάσταση γίνεται

0 * 2 + 2 = 2

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

Είναι πιο εμφανές άμα κάτσεις και προσπαθήσεις να το δεις  με πραγματικούς πίνακες από το να διαβάζεις θεωρητικά για το μετασχηματισμό.

Νίκος Αδαμόπουλος

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2823
  • Πύργος Ηλείας
Απ: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #13 στις: 19 Φεβ 2014, 11:29:31 μμ »
Φτούουου! Δεν το καταλαβαίνω. :-[ :'(
Δεν θα μπορέσω να το διδάξω αυτό.

Ένα σχετικό θέμα που είχα ανοίξει πριν από καιρό: https://alkisg.mysch.gr/steki/index.php?topic=3763
σχετίζεται άμεσα με τα προαναφερόμενα...

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Απ: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #14 στις: 20 Φεβ 2014, 10:51:44 πμ »
Σας ευχαριστώ για τις απαντήσεις. Τώρα έχει νόημα!!
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Απ: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #15 στις: 20 Φεβ 2014, 11:06:18 πμ »
Εγώ πάντως στην πράξη δεν κάνω καν προσπάθεια να διδάξω τέτοιο θέμα. Δεν υπάρχει χρόνος. Αν πέσει θέμα που να ζητάει ταξινόμηση σε 2Δ τους λέω να τα βάλουν σε μονοδιάστατο, να τα ταξινομήσουν και να τα βάλουν πίσω. Δεν είναι ότι καλύτερο αλλά δεν είναι και πολύ επιβαρυντικό αφού δεν αλλάξει την τάξη τους αλγορίθμου. Πάλι ν^2 είναι. Οι 2 μεταφορές δεν είναι τόσο τραγικό μπροστά στο ν^2. Είναι και οι χρονικοί περιορισμοί...

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 804
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Ερώτηση στους πίνακες (θεωρητική)
« Απάντηση #16 στις: 29 Μάρ 2017, 01:11:38 μμ »
Το κοντινότερο που μπόρεσα να σκεφτώ σε "ρεαλιστικό" πρόβλημα που να εξυπηρετεί η ταξινόμηση δισδιάστατου:

Πίνακας Ο[23] με τα ονόματα των 23 μαθητών ενός τμήματος.
Πίνακας Τ[14] με τους τίτλους των 10 μαθημάτων στα οποία βαθμολογούνται.
Πίνακας Β[23, 14] με τους βαθμούς των μαθητών στα μαθήματα.
Να εμφανιστούν οι 50 υψηλότεροι από τους 230 βαθμούς και για κάθε βαθμό, το όνομα του μαθητή και ο τίτλος του μαθήματος που αφορά ο βαθμός.
Σε περίπτωση ισοψηφίας επόμενων βαθμών με τον 50ο, να εμφανιστούν τα στοιχεία για όλους τους επόμενους που ισοβαθμούν.

Μια λύση, προϋποθέτει
1) τη δημιουργία 2 παράλληλων δισδιάστατων πινάκων δεικτών:
- ενός για τη φύλαξη της γραμμής
- ενός για τη φύλαξη της στήλης

2) ταξινόμηση του δισδιάστατου (και των παράλληλών του)

3) εμφάνιση των 50 πρώτων βαθμών (και αντίστοιχων ονομάτων και τίτλων με τη βοήθεια των τιμών των δεικ΄των από τους παράλληλοπυς πίνακες )

4) (όμοια) εμφάνιση όσων ισοβαθμούν με τον τελευταίο.

Το επίπεδο δυσκολίας ανεβαίνει αν ζητηθεί και δευτερεύον κριτήριο (ή περισσότερα) σε περίπτωση ισοβαθμίας, π.χ. σε αλφαβητική σειρά μαθητών και για τον ίδιο μαθητή σε αλφαβητική σειρά μαθημάτων..
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)