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

parantop

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

Wizard

  • Επισκέπτης
Κώδικας: Text
  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.   ΓΡΑΨΕ πλήθος
  20.  

nikosx

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

π <-- 1
ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν
   d <-- ΨΕΥΔΗΣ
   j <-- 1
   ΟΣΟ d=ΨΕΥΔΗΣ ΚΑΙ j<i ΕΠΑΝΑΛΑΒΕ
     ΑΝ A[j]=Α ΤΟΤΕ
       done <-- ΑΛΗΘΗΣ
     ΤΕΛΟΣ_ΑΝ
       j <-- j + 1
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
   ΑΝ d=ΨΕΥΔΗΣ ΤΟΤΕ
     π <--  π + 1
   ΤΕΛΟΣ_ΑΝ
 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
 ΓΡΑΨΕ π
Νίκος Ξένος
nkxenos@yahoo.gr

Wizard

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

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

Κώδικας: Text
  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.   ΓΡΑΨΕ πλήθος
  17.  

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2442
  • I 'm not young enough to know everything
Πέρα από το συγκεκριμένο θέμα στο διαγώνισμα, η εύρεση των διαφορετικών στοιχείων ενός πίνακα είναι ένα ενδιαφέρον ζήτημα και αξίζει να γίνει μια κουβέντα πάνω στις διάφορες προσεγγίσεις που υπάρχουν.

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

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

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

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

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3049
  • to Iterate is human to Recurse divine

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2442
  • I 'm not young enough to know everything
Εκτός ύλης; Και πως λύνουν την ΔΣ3 (τετράδιο μαθητή κεφάλαιο 10) που ζητάει ποιο από τα στοιχεία του πίνακα εμφανίζεται πιο πολλές φορές;


evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3049
  • to Iterate is human to Recurse divine

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2442
  • I 'm not young enough to know everything
Καταλαβαίνω καλά τι λες Ευριπίδη.
Είναι βέβαια δικαίωμά τους να πιστεύουν ότι κάτι είναι τραβηγμένο, ή εξωπραγματικό αφού ο καθένας ορίζεις αυτές τις έννοιες όπως τον βολεύει.

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

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

ppan

  • Οπαδός
  • **
  • Μηνύματα: 12
ΠΑΡΑΚΑΤΩ ΔΙΝΩ ΜΙΑ ΥΛΟΠΟΙΗΣΗ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ ΜΕΣΩ ΤΗΣ ΤΑΞΙΝΟΜΗΣΗΣ (Δεύτερη εναλλακτική προσέγγιση όπως ανέφερε και ο 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

  • Οπαδός
  • **
  • Μηνύματα: 12
ΕΚ ΠΑΡΑΔΡΟΜΗΣ ΔΕΝ ΑΝΕΦΕΡΑ ΟΤΙ Ο ΠΡΩΤΟΣ ΑΛΓΟΡΙΘΜΟΣ ΤΟΥ wizard ΕΙΝΑΙ ΣΩΣΤΟΣ!!

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2442
  • I 'm not young enough to know everything
Ίσως να μην περιέγραψα πολύ καλά αυτό που είχα στο νου μου στη δεύτερη λύση. Αυτό που εννούσα  είναι το εξής:

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

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

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

EleniK

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 708
Νομίζω ότι ο τρόπος του Γιώργου με την ταξινόμηση είνα πιο κατανοητός στα παιδιά καθότι μπορούν να έχουν και "οπτική" άποψη περί του τι συμβαίνει και αυτό τα βοηθά να κατανοήσουν καλύτερα την άσκηση, χωρίς πολλές διαμαρτυρίες...
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

Wizard

  • Επισκέπτης
ΕΠΙΣΗΣ ΠΑΡΑΤΗΡΗΣΑ ΟΤΙ Ο ΑΛΓΟΡΙΘΜΟΣ ΤΟΥ wizard ΣΤΗΝ ΔΕΥΤΕΡΗ ΕΚΔΟΧΗ ΤΟΥ (ΜΕ ΕΝΑ ΑΠΛΟ ΤΡΕΞΙΜΟ ΠΡΟΚΥΠΤΕΙ) ΔΕΝ ΕΙΝΑΙ ΣΩΣΤΟΣ.

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

ppan

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