Θέμα: 3ο κεφ-παράδειγμα με αλγόριθμο

[bookitsa]

Γεια σας ..είμαι καινούρια στο site και στο χώρο της εκπαίδευσης. Θα ήθελα να σας ρωτήσω κάτι που με ρώτησε ένας μαθητής μου και δεν ήξερα τι ν'απαντήσω γιατί μπερδεύτηκα κι εγώ..

Στο 3ο κεφάλαιο του βιβλίου του μαθητή έχει το εξής στη σελίδα 56.
Έστω ότι πρέπει να γραφεί ένας αλγόριθμος που να δέχεται ως  είσοδο το όνομα ενός συνδρομητή του ΟΤΕ και  να δίνει ως έξοδο το τηλέφωνό του.

1η λύση

Δομή δεδομένων

Δημιουργείται μια ακολουθία (Ο1,Τ1), (Ο2, Τ2),…,(Ον,Τν), όπου οι μεταβλητές Οi και Τi αναφέρονται στο όνομα και στο τηλέφωνο του i-οστού συνδρομητή, για i=1,2,..ν

Αλγόριθμος

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

2η λύση

Δομή δεδομένων
Χρησιμοποιείται και πάλι η ακολουθία της πρώτης λύσης, αλλά αυτή τη φορά οι συνδρομητές είναι ταξινομημένοι λεξικογραφικά. Επιπλέον δημιουργείται μια δεύτερη ακολουθία με τα στοιχεία (Α,ν1), (Β,ν2),…,(Ω,ν24). Κάθε στοιχείο της δεύτερης αυτής ακολουθίας δίνει για κάθε γράμμα του αλφαβήτου τη θέση νi  (για i=1,2,…,24) στην πρώτη ακολουθία με το πρώτο όνομα συνδρομητή που αρχίζει από το γράμμα αυτό.

Αλγόριθμος
Αφήνεται για άσκηση στο μαθητή.

Μήπως έχει κανείς φτιάξει αυτόν τον αλγόριθμο της δεύτερης λύσης? Θα σας ήμουν ευγνώμων….

[Laertis]

Δες εδώ ...

http://users.otenet.gr/~genic/test_pin8.doc

[gpapargi]

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

Η συγκεκριμένη άσκηση (την κάνω με παράλληλους μονοδιάστατους) είναι ουσιαστικά το ψάξιμο που κάνει ο άνθρωπος όταν πχ ψάχνει να βρει κάτι σε ένα βιβλίο… κοιτάει τα περιεχόμενα. Ο πίνακας με τα γράμματα είναι ουσιαστικά το ευρετήριο. Ο μαθητής καταλαβαίνει την ανάγκη για χρήση πιο γρήγορης αναζήτησης. Ποιος ψάχνει ένα τηλεφωνικό κατάλογο όνομα-όνομα σειριακά; Και φυσικά τίθεται εντελώς φυσιολογικά το ερώτημα πόσο γρήγορη αναζήτηση μπορούμε να κάνουμε; Η ερώτηση αυτή μας οδηγεί στη δυαδική αναζήτηση.

Αν δεν υπήρχε η δυαδική αναζήτηση η ταξινόμηση δε θα είχε λόγω ύπαρξης. Γιατί άραγε είναι εντός ύλης η ταξινόμηση και εκτός η δυαδική αναζήτηση;    Αν ο μαθητής δε δει πως δένουν τα πράγματα μεταξύ τους πως θα βρει ενδιαφέρον το μάθημα; Δεν είναι δύσκολος αλγόριθμος και διαφημίζει την πληροφορική αφού εξηγεί το αντικείμενό της πολύ παραστατικά (σε μέγεθος πίνακα ίσο με τον πληθυσμό της γης (7 δις) η σειριακή κάνει 7 δισεκατομμύρια βήματα ενώ η δυαδική μόνο 33).

Η άσκηση αυτή προσφέρεται για ωραία κουβέντα. Ελπίζω κάποια στιγμή και αυτοί που καθορίζουν την ύλη να λειτουργήσουν περισσότερο επιστημονικά και παιδαγωγικά και να πετάξουν έξω κεφάλαια που προάγουν την παπαγαλία (4 & 6) και να βάλουν μέσα 1-2 πράγματα που διαφημίζουν την αλγοριθμική σκέψη. 

ΥΓ
Μικρή λεπτομέρεια. Στην παραπάνω λύση νομίζω πως υπάρχει πρόβλημα αν το όνομα ξεκινάει από «Ω» αφού δεν περνάμε το όνομα ποτέ. Υπάρχουν διάφορες προσεγγίσεις, πχ να μπει μια 25 γραμμή στο ευρετήριο με περιεχόμενο «ΩΩΩΩΩ» που είναι μετά από κάθε όνομα ή να γίνει ανάποδα σάρωση του ευρετηρίου αφού το «Α» είναι σίγουρα μικρότερο από όλα. Επίσης στον μεγάλο πίνακα μπορεί να χρησιμοποιηθεί ακέραια αντί για λογική μεταβλητή, που ξεκινάει με 0 και γίνεται 1 αν  βρούμε το όνομα ή 2 αν το περάσουμε.

[Laertis]

Έχεις δίκιο Γιώργη,  το διόρθωσα με απλούστερο τρόπο.
Αν έχεις όρεξη ξαναδέστο Plz.

[coletsos]

Νομίζω ότι στη σειρά 14 του αλγορίθμου σου θές να πείς "Αν Index[i,1] > Επώνυμο τότε" ενώ έχεις γράψει εκπαραδρομής φαντάζομαι "Αν Π[i,1] > Επώνυμο τότε"

Επίσης στη σειρά 13 πιστεύω ότι πρέπει να γίνει "Όσο i <= 24 και Γράμμα = Ψευδής επανάλαβε"
και στη σειρά 21 "Θέση_ index <-- Index[Γράμμα_index – 1 ,2]", για να συμπεριλαμβάνετε και το Index[23,2]

Φιλικά,
Θοδωρής Κολέτσος

[bookitsa]

Απορίες
   1)
               Αρχή_επανάληψης
                   Διάβασε Επώνυμο, Όνομα            
              Μέχρις_ότου Επώνυμο > “A” και Επώνυμο < “ΩΩ”
Καταλαβαίνω ότι εδώ θα διαβάσουμε μόνο δύο αλφαριθμητικά: ένα επώνυμο και ένα όνομα. Και ότι θα πρέπει αυτά να  ξεκινούν με ένα από τα γράμματα της ΑΒ και γι’αυτό κάνουμε τον έλεγχο. Γιατί όμως πρέπει να βάλουμε 2 ω?Δεν αρκεί ένα?
 
2) Αμέσως λοιπόν μετά από την προηγούμενη επανάληψη ακολουθεί το
            Διάβασε  Όνομα
Γιατί? Αφού το διαβάσαμε το όνομα και το επώνυμο. Ποιος ο λόγος να διαβάσουμε πάλι το όνομα?

3)Εφόσον δε θέλουμε να χάσουμε τα επώνυμα που ξεκινούν από Ω γιατί βάζουμε
Αν  Επώνυμο>Ω τότε
   Γράμμα _index <- 25
Και όχι

Αν  Επώνυμο=Ω τότε
   Γράμμα _index <- 25



4)
Αν  Επώνυμο>Ω τότε
   Γράμμα _index <- 25
αλλιώς
            Γράμμα _index <- 0
            Γράμμα <- Ψευδής
            i <-1
Όσο i <= 23 και Γράμμα = Ψευδής επανάλαβε
      Αν Π[i,1] > Επώνυμο τότε      
         Γράμμα <- Αληθής      
         Γράμμα _index <- i      
      αλλιώς
         i <- i + 1
      Τέλος_αν
Τέλος_επανάληψης

Η Αν αυτή, εδώ δεν πρέπει να κλείσει ή όχι?


5)Επίσης έχω μπερδευτεί στα υπόλοιπα όσον αφορά την αναφορά στους δύο πίνακες. Ο πρώτος πίνακας είναι ο Π, ο δεύτερος ποιος είναι στη λύση? Ποιο είναι το όνομά του? Επίσης για να αναφερθούμε σε κάθε στοιχείο του πρώτου λέμε Π(i,j), για να αναφερθούμε σε κάθε στοιχείο του δεύτερου τι λέμε?

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

[coletsos]

Θα κάνω μια προπάθεια να απντήσω όσο καλύτερα γίνεται στις απορίες, ότι κάνω λάθος μπορείτε να με διορθώσετε.
1) Χρειάζονται τα δύο ΩΩ για τον εξής λόγο:
το "Ωρολογάς" που υπάρχει στο παράδειγμα είναι μεγαλύτερο από το σκέτο "Ω" και έτσι δε θα γινόταν αποδεκτό σαν είσοδος απο τον έλεγχο εγκυρότητας. Έτσι λοιπόν μπήκε το "ΩΩ" μιάς και δεν ξέρουμε κάποιο όνομα που να αρχίζει από ΩΩ 
2) Το δεύτερο "Διάβασε Όνομα" Πιστεύω και εγώ πως δε χρειάζετε
3)Γιατί δεν υπάρχει επώνυμο που να ισούτε με "Ω".  Τουλάχιστον εγώ δε ξέρω κανέναν κύριο "Ω". Από την άλλη επίθετα όπως "Ωρολογάς","Ωχαμαν","Ωαασδγ"(δε μου έρχετε βασικά κανένα επίθετο με Ω...) είναι μεγαλύτερα από το "Ω" αν τα συγκρίνουμε αλφαριθμιτικά.

4) Ναι εκεί πρέπει να κλείσει
5) δες το ποστ που έκανα από πάνω απτό δικό σου. Ο ένας πίνακας είναι ο Π[i,j] και ο άλλος ο Index[i,j]

Πέρα από τις ερωτήσεις θα πρότεινα η δομή επανάληψης όσο στη σειρά 25 να γίνει
"Όσο i <= Index[Γράμμα_index,2] και Βρέθηκε = Ψευδής επανάλαβε"
ώστε να μη γίνονται περιτές επαναλήψεις αφού αν φτάσει στο δείκτη του επόμενου γράμματος δεν υπάρχει σίγουρα αυτό το όνομα. Μόλις είδα ότι έχει γίνει αυτό ως εξής:
αλλιώς_αν Π[i,1] > Επώνυμο τότε
      Βρέθηκε <-- Αληθής
οπότε είναι ΟΚ και έτσι όπως είναι

Αυτά ελπίζω να βοήθησα...

[bookitsa]

    Αρχή_επανάληψης
             Διάβασε Επώνυμο, Όνομα            
    Μέχρις_ότου Επώνυμο > “A” και Επώνυμο < “ΩΩ”

Για ποιο λόγο τελικά χρειάζεται αυτός ο έλεγχος ? Με έχει μπερδέψει…Γιατί να μη βάλουμε σκέτα να διαβάσει το όνομα και το επώνυμο?

2)Η πρώτη στήλη του index έχει σε κάθε γραμμή από ένα γράμμα της ΑΒ. Η στήλη επώνυμο έχει επίθετα.Οπότε πως γίνεται ο έλεγχος? Ελέγχουμε δηλαδή αν ένα γράμμα είναι μεγαλύτερο από ένα ολόκληρο επίθετο?Γίνεται αυτό?
 Αν Index[i,1] > Επώνυμο τότε κλπ

 3)Στην επανάληψη αυτή
Όσο i <= Ν και Βρέθηκε = Ψευδής επανάλαβε
        Αν Π[i,1] = Επώνυμο και Π[i,2] = Όνομα τότε
      Βρέθηκε <- Αληθής
      Θέση_στον _Κατάλογο <- i
   αλλιώς_αν Π[i,1] > Επώνυμο τότε
      Βρέθηκε <- Αληθής
   αλλιώς
      i <- i + 1
   Τέλος_αν
Τέλος_επανάληψης

χρειάζεται το τμήμα
 αλλιώς_αν Π[i,1] > Επώνυμο τότε
             Βρέθηκε <- Αληθής 

Γιατί δηλαδή να μην το γράψουμε
Όσο i <= Ν και Βρέθηκε = Ψευδής επανάλαβε
     Αν Π[i,1] = Επώνυμο και Π[i,2] = Όνομα τότε
      Βρέθηκε <- Αληθής
      Θέση_στον _Κατάλογο < -i
     αλλιώς
             i <- i + 1   
     Τέλος_αν
Τέλος_επανάληψης


      

[sstergou]

Στη σελίδα 166 αναφέρεται η αλφαβητική διάταξη των γραμμάτων.
Στο παρελθόν έχει πέσει θέμα στο οποίο ζητήθηκε αλφαβητική ταξινόμηση ονομάτων.

Ίσως αυτό το θέμα βοηθήσει :
https://alkisg.mysch.gr/steki/index.php?topic=929.0

Γιατί δηλαδή να μην το γράψουμε
Όσο i <= Ν και Βρέθηκε = Ψευδής επανάλαβε
     Αν Π[i,1] = Επώνυμο και Π[i,2] = Όνομα τότε
      Βρέθηκε <- Αληθής
      Θέση_στον _Κατάλογο < -i
     αλλιώς
             i <- i + 1   
     Τέλος_αν
Τέλος_επανάληψης

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


Φιλικά

 

[bookitsa]

Σας ευχαριστώ όλους για τη πολύτιμη βοήθειά σας.Τον ξανακοίταξα τον αλγόριθμο και έχω τις τελευταίες ελπίζω απορίες μου.
Α) Τελικά τον έλεγχο τι τον χρειαζόμαστε στην αρχή?
    Αρχή_επανάληψης
           Διάβασε Επώνυμο, Όνομα            
    Μέχρις_ότου Επώνυμο > “A” και Επώνυμο < “ΩΩ”

Β)Αμέσως μετά τον έλεγχο ακολουθεί το εξής
Αν  Επώνυμο>Ω τότε
   Γράμμα _index <- 25
Εφόσον ο Ωρολογάς π.χ. είναι > από το Ω γιατί ο δείκτης Γράμμα_index να δείχνει στην 25η θέση του πίνακα index?

Γ) Γιατί να γράφουμε: Αν Index[i,1] > Επώνυμο τότε
Και όχι: Αν Index[i,1] = Επώνυμο τότε..
Δηλαδή γιατί η αναζήτηση να σταματά στο επόμενο γράμμα από αυτό που αρχίζει το επώνυμο και να μη σταματά στο ίδιο αυτό κάθε αυτό στοιχείο που ψάχνουμε?

Δ) Η εμφάνιση τέλος των στοιχείων έχει ως εξής:
Αν Θέση_στον _Κατάλογο = 0 τότε
   Εμφάνισε “ Το όνομα “, Επώνυμο, Όνομα, ”δεν υπάρχει στον κατάλογο”
Αλλιώς
Εμφάνισε “ Το τηλέφωνο του “, Επώνυμο, Όνομα, ”είναι” , Π[Θέση_στον _Κατάλογο ,2]
   Τέλος_αν

Στο αλλιώς δε θα έπρεπε να γράψουμε
Εμφάνισε “ Το τηλέφωνο του “, Επώνυμο, Όνομα, ”είναι” , Π[Θέση_στον _Κατάλογο ,3],
 εφόσον το τηλέφωνο βρίσκεται στην 3η στήλη του πίνακα Π?

[Laertis]

Πολλά λάθη και παραβλέψεις έκανα, μάλλον άρχισα να γερνάω 

Ευχαριστώ Θοδωρή για τις υποδείξεις. Η διόρθωση έγινε.

bookitsa ...
Α)Ο έλεγχος γίνεται για να μην μπουν άλλοι χαρακτήρες εκτός των κεφαλαίων Α ως Ω.
π.χ θα μπορούσε να εισαχθεί #$%@!#, αν δε γινόταν έλεγχος.

Β) Γιατί ο αλγόριθμος εντοπίζει το αμέσως επόμενο γράμμα απο αυτό που ξεκινά το επώνυμο, και έπειτα υπολογίζει το προηγούμενο
             Θέση_ index <-- index [Γράμμα_index – 1 ,2]

Γ) ..... προφανώς δεν έχεις καταλάβει την άσκηση και επομένως και τον αλγόριθμο
Στον Index περιλαμβάνονται μόνο τα 24 γράμματα του αλφαβήτου. Δε μπορεί να ισχύει
Index[i,1] = Επώνυμο

Δ) Σωστά. Το έχω διορθώσει μαζί με όλα τα άλλα λάθη που επισημάνθηκαν προηγουμένως

[bookitsa]

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

[sstergou]

Μήπως ο πίνακας index πρέπει να σπαστεί σε παράλληλους μονοδιάστατους αφού σε αυτόν είναι αποθηκευμένα αλφαριθμητικά και ακέραιοι;

[Laertis]

Χμμ όχι απαραίτητα,

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

[sstergou]

Κώδικας: [Επιλογή]

Θέση_index <- index [Γράμμα_index – 1 ,2]
Θέση_στον _Κατάλογο <- 0
i <- Θέση_index

και μετά :

Κώδικας: [Επιλογή]

Αν Π[i,1] = Επώνυμο και Π[i,2]= Όνομα τότε
δηλαδή αν και αλφαριθμητικό το χρησιμοποιούμε σαν δείκτη σε πίνακα.

edit:Προσωπικά δεν θα είχα κανένα πρόβλημα η ψευδογλώσσα να ήταν loosely typed, αλλά δυστυχώς δεν είναι (ποτέ δεν είμαι σίγουρος για τίποτα βέβαια με τέτοιο βιβλίο). Δεν ξέρω βέβαια αν έχει νόημα να έχουν τύπους οι μεταβλητές σε ένα περιβάλλον που υποτίθεται ότι είναι για να φτιάχνεις ένα σκαρίφημα της λύσης και όχι για την πλήρη περιγραφή της και εκτέλεσή της σε προγραμματιστικό περιβάλλον.