Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Μονοδιάστατοι πίνακες => Μήνυμα ξεκίνησε από: parantop στις 10 Φεβ 2007, 01:32:26 πμ

Τίτλος: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: parantop στις 10 Φεβ 2007, 01:32:26 πμ

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: Wizard στις 10 Φεβ 2007, 11:36:51 πμ

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

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 στις 10 Φεβ 2007, 07:19:33 μμ

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

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: Wizard στις 11 Φεβ 2007, 09:53:56 πμ

Πολύ σωστά 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 στις 11 Φεβ 2007, 04:33:11 μμ

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

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

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

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

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

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: evry στις 11 Φεβ 2007, 06:40:06 μμ

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: gpapargi στις 12 Φεβ 2007, 09:06:45 πμ

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: evry στις 12 Φεβ 2007, 02:25:23 μμ

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: gpapargi στις 12 Φεβ 2007, 02:51:56 μμ

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

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

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: ppan στις 13 Φεβ 2007, 10:35:26 πμ

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

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: gpapargi στις 13 Φεβ 2007, 01:52:17 μμ

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

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

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

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: EleniK στις 13 Φεβ 2007, 02:15:25 μμ

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: Wizard στις 13 Φεβ 2007, 04:34:21 μμ

Παράθεση από: ppan στις 13 Φεβ 2007, 10:35:26 πμ

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

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: ppan στις 13 Φεβ 2007, 10:17:59 μμ

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

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: Wizard στις 13 Φεβ 2007, 10:40:58 μμ

Παράθεση από: ppan στις 13 Φεβ 2007, 10:17:59 μμ

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

Κανένα πρόβλημα  ;)

offtopic: Μήπως θα'πρεπε η Γλωσσομάθεια να αφαιρέσει τη μία παύλα από την εντολή της εκχώρησης;

Τίτλος: Απ: Πλήθος διαφορετικών αριθμών, που υπάρχουν σε ένα πίνακα?
Αποστολή από: Βρακόπουλος Αθανάσιος Λ. στις 14 Φεβ 2007, 05:41:13 μμ

Θα δώσω και εγώ μια απάντηση στο θέμα που μας απασχολεί.

Εισάγω στον πίνακα Β, ένα στοιχείο του πίνακα Α, μόνον αν αυτό δεν υπάρχει στον πίνακα Β. Το πλήθος των στοιχείων του πίνακα Β είναι το πλήθος των διαφορετικών στοιχείων του Α.
===============================================================
Ο αλγόριθμος είναι ο παρακάτω

Κ<--1 !πλήθος διαφορετικών στοιχείων
B[K]<--A[1]
Για Ι από 2 μέχρι Ν
   J <-- 1
   Όσο Α[Ι]<>Β[J] και J<Ν Επανάλαβε
      J <-- J+1
   Τέλος_Επανάληψης

   Αν Α[Ι]<>Β[J] τότε ! αν το Α[Ι] δεν υπάρχει στον πίνακα Β, τότε καταχώρησέ το στον πίνακα Β
      Κ<--Κ+1       
      Β[Κ]<--Α[Ι]
   Τέλος_Αν
Τέλος_Επανάληψης

Έτσι αν ο πίνακας Α έχει του αριθμούς 2,3,4,3,4,2,5,6 ο πίνακας Β θα έχει τους 2,3,4,5,6

Με εκτίμηση
Βρακόπουλος Λ. Αθανάσιος