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

[parantop]

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

[Wizard]

Κώδικας: ΓΛΩΣΣΑ

1. πλήθος <-- 0
2.   k <-- 0
3.   ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν     ! Ν το πλήθος των στοιχείων του Α
4.     done <-- ψευδής
5.     j <-- 1
6.     ΟΣΟ done=ψευδής ΚΑΙ j<=k ΕΠΑΝΑΛΑΒΕ
7.       ΑΝ B[j]=Α[i] ΤΟΤΕ
8.         done <-- αληθής
9.       ΑΛΛΙΩΣ
10.         j <-- j + 1
11.       ΤΕΛΟΣ_ΑΝ
12.     ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
13.     ΑΝ done=ψευδής ΤΟΤΕ
14.       k <-- k + 1
15.       B[k] <-- A[i]
16.       πλήθος <-- πλήθος + 1
17.     ΤΕΛΟΣ_ΑΝ
18.   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
19.   ΓΡΑΨΕ πλήθος

[nikosx]

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

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

[Wizard]

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

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

Κώδικας: ΓΛΩΣΣΑ

1. πλήθος <-- 0
2.   ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν   ! Ν ο αριθμός των στοιχείων του Α
3.     done <-- ψευδής
4.     j <-- 1
5.     ΟΣΟ done=ψευδής ΚΑΙ j<i ΕΠΑΝΑΛΑΒΕ
6.       ΑΝ A[j]=A[i] ΤΟΤΕ
7.         done <-- αληθής
8.       ΑΛΛΙΩΣ
9.         j <-- j + 1
10.       ΤΕΛΟΣ_ΑΝ
11.     ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
12.     ΑΝ done=ψευδής ΤΟΤΕ
13.       πλήθος <-- πλήθος + 1
14.     ΤΕΛΟΣ_ΑΝ
15.   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
16.   ΓΡΑΨΕ πλήθος

[gpapargi]

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

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

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

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

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

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

[evry]

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

[gpapargi]

Εκτός ύλης; Και πως λύνουν την ΔΣ3 (τετράδιο μαθητή κεφάλαιο 10) που ζητάει ποιο από τα στοιχεία του πίνακα εμφανίζεται πιο πολλές φορές;

[evry]

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

[gpapargi]

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

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

Ας ξέρουν ότι είναι ΕΝΤΟΣ ΥΛΗΣ και από 'κει και πέρα ας λάβουν τις αποφάσεις τους με δική τους ευθύνη. Μεγάλα παιδιά είναι και μπορούν να αξιολογήσουν τα επιχειρήματα που ακούν.

[ppan]

ΠΑΡΑΚΑΤΩ ΔΙΝΩ ΜΙΑ ΥΛΟΠΟΙΗΣΗ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ ΜΕΣΩ ΤΗΣ ΤΑΞΙΝΟΜΗΣΗΣ (Δεύτερη εναλλακτική προσέγγιση όπως ανέφερε και ο gpapargi)

ΠΡΟΓΡΑΜΜΑ ΕύρεσηΔιαφορετικώνΣτοιχείωνΜέσωΤαξινόμησηςΦυσαλίδας
!Οι τιμές διαβάζονται από την καρτέλα «Αρχείο εισόδου
ΣΤΑΘΕΡΕΣ
  Ν = 10
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ι, κ, pl, pos, j
  ΑΚΕΡΑΙΕΣ: Α[Ν], προσ, B[Ν]
  ΛΟΓΙΚΕΣ: done
ΑΡΧΗ
!Διάβασμα του πίνακα
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΡΑΨΕ 'Δώσε το Α[', ι, ']:  '
    ΔΙΑΒΑΣΕ Α[ι]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!Ταξινόμηση του πίνακα
  ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ Ν
    ΓΙΑ κ ΑΠΟ Ν ΜΕΧΡΙ ι ΜΕ_ΒΗΜΑ -1
      ΑΝ Α[κ] < Α[κ - 1] ΤΟΤΕ
        προσ <- Α[κ]
        Α[κ] <- Α[κ - 1]
        Α[κ - 1] <- προσ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  !Εμφάνιση του πίνακα
  ΓΡΑΨΕ 'Ο ταξινομημένος πίνακας είναι:'
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΡΑΨΕ 'Α[', ι, '] = ', Α[ι]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  !Εύρεση διαφορετικών αριθμών
  B[1] <- Α[1]
  pl <- 1
  pos <- 1
  ΟΣΟ pos < Ν ΕΠΑΝΑΛΑΒΕ
    done <- ΨΕΥΔΗΣ
    j <- pos
    ΟΣΟ done=ΨΕΥΔΗΣ ΚΑΙ j <= Ν ΕΠΑΝΑΛΑΒΕ
      ΑΝ Α[j] <> Α[pos] ΤΟΤΕ
        done <- ΑΛΗΘΗΣ
        pos <- j
      ΑΛΛΙΩΣ
        j <- j+1
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΑΝ done=ΑΛΗΘΗΣ  ΤΟΤΕ
      pl <- pl+1
      B[pl] <- Α[pos]
    ΑΛΛΙΩΣ
      pos <- j
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ 'ΤΟ ΠΛΗΘΟΣ ΤΩΝ ΔΙΑΦΟΡΕΤΙΚΩΝ ΑΡΙΘΜΩΝ ΕΙΝΑΙ:', pl
  !Εμφάνιση των διαφορετικών αριθμών
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ pl
    ΓΡΑΨΕ 'Β[', ι, '] = ', B[ι]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΕΠΙΣΗΣ ΠΑΡΑΤΗΡΗΣΑ ΟΤΙ Ο ΑΛΓΟΡΙΘΜΟΣ ΤΟΥ wizard ΣΤΗΝ ΔΕΥΤΕΡΗ ΕΚΔΟΧΗ ΤΟΥ (ΜΕ ΕΝΑ ΑΠΛΟ ΤΡΕΞΙΜΟ ΠΡΟΚΥΠΤΕΙ) ΔΕΝ ΕΙΝΑΙ ΣΩΣΤΟΣ.

[ppan]

ΕΚ ΠΑΡΑΔΡΟΜΗΣ ΔΕΝ ΑΝΕΦΕΡΑ ΟΤΙ Ο ΠΡΩΤΟΣ ΑΛΓΟΡΙΘΜΟΣ ΤΟΥ wizard ΕΙΝΑΙ ΣΩΣΤΟΣ!!

[gpapargi]

Ίσως να μην περιέγραψα πολύ καλά αυτό που είχα στο νου μου στη δεύτερη λύση. Αυτό που εννούσα  είναι το εξής:

! Προηγείται ταξινόμηση για να έρθουν δίπλα τα ίσα στοιχεία

Εμφάνισε α[1]                  ! Όπως και να έχει θα εμφανιστεί
Για ι από 2 μέχρι ν            ! Για τα υπόλοιπα
    Αν α[ι] <> α[ι-1] τότε   ! Αν κάποιο διαφέρει από το προηγούμενο
        Εμφάνισε α[ι]           ! Εμφάνισέ το
    Τέλος_αν
Τέλος_επανάληψης

Δηλαδή γίνεται εμφάνιση όποτε εντοπίζει αλλαγή.

[EleniK]

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

[Wizard]

ΕΠΙΣΗΣ ΠΑΡΑΤΗΡΗΣΑ ΟΤΙ Ο ΑΛΓΟΡΙΘΜΟΣ ΤΟΥ wizard ΣΤΗΝ ΔΕΥΤΕΡΗ ΕΚΔΟΧΗ ΤΟΥ (ΜΕ ΕΝΑ ΑΠΛΟ ΤΡΕΞΙΜΟ ΠΡΟΚΥΠΤΕΙ) ΔΕΝ ΕΙΝΑΙ ΣΩΣΤΟΣ.

Τι εννοείς; Μια χαρά τρέχει.

[ppan]

Χίλια συγνώμη wizard!! Ο δαίμων του copy - paste έκανε το θαύμα του. Κατά την αντιγραφή του αλγόριθμου και τη μεταφορά του στο περιβάλλον της ΓΛΩΣΣΑΣ η εντολή: πλήθος <-- πλήθος + 1 μεταφέρθηκε ως πλήθος <-  - πλήθος + 1 (δηλαδή με ένα μείον μπροστά από τη μεταβλητή πλήθος και το οποίο δεν είχα παρατηρήσει)