Γενικό Λύκειο > Μονοδιάστατοι πίνακες

Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?

(1/4) > >>

parantop:
Μπορεί κανείς να γράψει ένα κώδικα που να το υλοποιεί. Το πρόβλημα είναι από τα διαγωνίσματα. Ευχαριστώ.

Wizard:

--- Κώδικας: ΓΛΩΣΣΑ ---πλήθος <-- 0  k <-- 0  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν     ! Ν το πλήθος των στοιχείων του Α    done <-- ψευδής    j <-- 1    ΟΣΟ done=ψευδής ΚΑΙ j<=k ΕΠΑΝΑΛΑΒΕ      ΑΝ B[j]=Α[i] ΤΟΤΕ        done <-- αληθής      ΑΛΛΙΩΣ        j <-- j + 1      ΤΕΛΟΣ_ΑΝ    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ    ΑΝ done=ψευδής ΤΟΤΕ      k <-- k + 1      B[k] <-- A[i]      πλήθος <-- πλήθος + 1    ΤΕΛΟΣ_ΑΝ  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ  ΓΡΑΨΕ πλήθος

nikosx:
Νομίζω ότι και το παρακάτω τμήμα υπολογίζει το πλήθος των διαφορετικών αριθμών σε έναν πίνακα Α Ν θέσεων χωρίς όμως να χρησιμοποιεί τον δεύτερο βοηθητικό πίνακα Β

π <-- 1
ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν
   d <-- ΨΕΥΔΗΣ
   j <-- 1
   ΟΣΟ d=ΨΕΥΔΗΣ ΚΑΙ j<i ΕΠΑΝΑΛΑΒΕ
     ΑΝ A[j]=Α ΤΟΤΕ
       done <-- ΑΛΗΘΗΣ
     ΤΕΛΟΣ_ΑΝ
       j <-- j + 1
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
   ΑΝ d=ΨΕΥΔΗΣ ΤΟΤΕ
     π <--  π + 1
   ΤΕΛΟΣ_ΑΝ
 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
 ΓΡΑΨΕ π

Wizard:
Πολύ σωστά nikosx  ;) Καλύτερα να βάζουμε τον κώδικα μέσα σε code tags γιατί αν θες να γράψεις τη μεταβλητή i μέσα σε αγκύλες, το forum θεωρεί ότι θες να γράψεις με πλάγια γραφή, γι'αυτό σου εμφάνισε έτσι τον κώδικα.

Το προηγούμενο μου παράδειγμα χωρίς τη χρήση του πίνακα Β:


--- Κώδικας: ΓΛΩΣΣΑ ---πλήθος <-- 0  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν   ! Ν ο αριθμός των στοιχείων του Α    done <-- ψευδής    j <-- 1    ΟΣΟ done=ψευδής ΚΑΙ j<i ΕΠΑΝΑΛΑΒΕ      ΑΝ A[j]=A[i] ΤΟΤΕ        done <-- αληθής      ΑΛΛΙΩΣ        j <-- j + 1      ΤΕΛΟΣ_ΑΝ    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ    ΑΝ done=ψευδής ΤΟΤΕ      πλήθος <-- πλήθος + 1    ΤΕΛΟΣ_ΑΝ  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ  ΓΡΑΨΕ πλήθος

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

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

Μια άλλη προσέγγιση είναι να ταξινομήσης τον πίνακα. Έτσι τα ίδια στοιχεία θα έρθουν δίπλα και τότε θα μπορείς να ελέγξεις για επανεμφανίσεις κοιτώντας απλά τη «γειτονιά» κάθε στοιχείου.
Αφού ταξινομήσεις τον πίνακα, καταρχήν εμφανίζεις το πρώτο στοιχείο (όπως και να ’χει το πρώτο στοιχείο θα εμφανιστεί). Μετά κάνεις μια σάρωση του πινακα από τη δεύτερη θέση και κάτω. Αν το στοιχείο που προσπελάζεις είναι διαφορετικό από το αμέσως προηγούμενο το εμφανίζεις, αλλιώς δεν το εμφανίζεις. Πρόκειται δηλαδή για μια εφαρμογή του αλγορίθμου ταξινόμησης.

Οι 2 λύσεις από πλευράς απόδοσης είναι περίπου στα ίδια στα σχολικά πλαίσια. Και οι 2 έχουν εμφωλευση εντολών επανάληψης δηλαδή έχουμε συγκρίσεις πλήθους τάξεως ν^2. Η μέθοδος που στηρίζεται στην αναζήτηση δείχνει εκ πρώτης όψεως κάπως γρηγορότερη αφού ο μέσα βρόχος αναζήτησης είναι με Όσο και αν βρει επανεμφάνιση σταματά τον περεταίρω έλεγχο. Αλλά και η μέθοδος που στηρίζεται στην ταξινόμηση μπορεί να επιταχυνθεί κάνοντας ταξινόμηση έξυπνης φυσαλλίδας (τετράδιο μαθητή κεφάλαιο 3 ΔΤ 2). Επίσης στο μέλλον μπορεί να ενισχυθεί κι άλλο με ταχύτερες ακόμα ταξινομήσεις που είναι εκτός ύλης. Θέλω να πω ότι δεν τίθεται θέμα ποιότητας.

Αυτό που με απασχολεί είναι το ποια είναι ευκολότερη με το μαθητή.

Έχω την εντύπωση ότι αυτή που στηρίζεται στην ταξινόμηση ίσως είναι ευκολότερη γιατί η ταξινόμηση είναι πλέον δομικός λίθος στην κατασκευή αλγορίθμων και δε χρειάζεται σκέψη από το μαθητή. Η δυσκολία είναι να σκεφτείς μετά πως θα πετύχεις τη γειτονική σύγκριση. Στη μέθοδο που στηρίζεται στην ταξινόμηση θα πρέπει μόνος σου να υλοποίσης την εμφώλευση των επαναληπτικών εντολών. Και οι μαθητές δυσκολεύονται όταν βλέπουν εμφώλευση. Οι «δικοί μου» από ότι κατάλαβα προτιμούν τη μέθοδο με ταξινόμηση. Υπάρχουν άλλες εμπειρίες από τάξη;
 

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση