Θέμα: Σειριακή Αναζήτηση με τη δομή Για...από...μέχρι

[evry]

  Λοιπόν έπεσα σε ένα θέμα στο όποιο έλεγε "να βρείτε το επώνυμο του ... με τον αλγόριθμο της σειριακής αναζήτησης"
Ο αλγόριθμος της σειριακής αναζήτησης περιγράφεται στο βιβλίο με χρήση της Όσο και με λογική μεταβλητή έτσι ώστε να σταματάει
όταν βρει αυτό που ψάχνουμε. Ωστόσο αφού στο μάθημα δεν παίζει ρόλο η απόδοση του αλγορίθμου αν κάποιος μαθητής απάντούσε με τον παρακάτω αλγόριθμο θα σκεφτόσασταν να του κόψετε κάτι?
(Θα ήθελα να δω στατιστικά αν υπάρχει κανείς που δεν θα του άρεσε η παρακάτω λύση)

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

1. θέση <- 0
2. Για i από 1 μέχρι Ν
3.    Αν table[i] = key τότε
4.        θέση <- i
5.    Τέλος_Αν
6. Τέλος_Επανάληψης
7. Αν θέση = 0  τότε
8.    Εμφάνισε 'Δεν υπάρχει'
9. Αλλιώς
10.    Εμφάνισε 'Βρέθηκε στη θέση', θέση
11. Τέλος_Αν

Εννοείται ότι γνωρίζουμε από την εκφώνηση ότι το Key εμφανίζεται στον πίνακα table το πολύ μια φορά.

[P.Tsiotakis]

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

[vistrian]

Εφόσον και ο αλγόριθμος αυτός επιτυγχάνει το σκοπό του, τότε θα τον δεχόμουν και δεν θα τον έπαιρνα ως λάθος.

[Καρκαμάνης Γεώργιος]

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

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

Και μια παραλλαγή που χρησιμοποιούν κάποιοι μαθητές είναι και  η :

θέση <- 0
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
   ΑΝ table = key ΤΟΤΕ
       Εμφάνισε 'Βρέθηκε στη θέση', ι
       θέση <- i
   ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ θέση = 0  ΤΟΤΕ
   Εμφάνισε 'Δεν υπάρχει'
ΤΕΛΟΣ_ΑΝ

[nikosx]

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

[papet]

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

[petrosp13]

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

[andreas_p]

Προφανώς.

Παράδειγμα . 

Αν ξέρεις ότι  1000 άτομα είναι εφ' ενός ζυγού  και σου αναθέτουν το παρακάτω : 

Γνωρίζεις ότι ΕΝΑΣ από τους 1000 έχει στη τσέπη του μια χρυσή λίρα παλαιάς κοπής (Β. Ελισάβετ) [ και μπορείς να ψάξεις στην τσέπη του]  και τη βρεις στον  π.χ. 3ο στη σειρά  ,  υπάρχει λόγος να συνεχίσεις  να ψαχουλεύεις τσέπες  από τον 4ο μέχρι και τον 1000ο ; 

[evry]

 κι'όμως η πολυπλοκότητα των δύο αναζητήσεων είναι η ίδια!!!!   Ο(Ν),
δεν έχουν δηλαδή και καμιά τρομερή διαφορά στην απόδοση, είναι της ίδιας τάξης

[gpapargi]

Υπάρχουν 2 θέματα. Το πρώτο είναι η χρήση της «Για» που πάει μέχρι το τέλος και δεν σταματάει μόλις βρει το στοιχείο. Το δεύτερο είναι η μη χρήση της λογικής μεταβλητής.

Στο θέμα της Για η πάγια θέση μου είναι ότι θα έπρεπε να κόβουμε βαθμούς όταν γίνονται εμφανώς περιττές επαναλήψεις. Είναι εμφανές ότι ο μαθητής αποφεύγει να χρησιμοποιήσει την Όσο. Κάνει λάθος επιλογή στη δομής επανάληψης. Βέβαια με βάση τα δεδομένα δεν τίθεται θέμα απώλειας βαθμών. Βαθμολογείται η ορθότητα (αν και κατά τη γνώμη μου θα έπρεπε να μετράει και η ποιότητα). Υπάρχουν μάλιστα και πολύ χειρότερα, δηλαδή αλγόριθμοι που αλλάζουν την τάξη.

Για μια αναλυτική συζήτηση στο παραπάνω θέμα υπάρχει το παρακάτω θέμα:
https://alkisg.mysch.gr/steki/index.php?topic=988.0

Τώρα το δεύτερο θέμα δηλαδή στη χρήση θέσης και όχι λογικής μεταβλητής.

Θεωρώ θαυμάσια τη λύση για πολλούς λόγους. Να μερικοί:

Όπου δεν υπάρχουν λογικές μεταβλητές η δουλειά γίνεται με ακεραίους. Πχ 0 για ψευδής και 1 για αληθής. Το βασικό concept είναι ότι αν συμβεί κάτι (συνθήκη αν) τότε αλλάζει κάτι για να το καταλάβουμε στον επόμενο έλεγχο επανάληψης, είτε είναι μετάβαση από ψευδής σε αληθής είτε 0 σε ένα είτε οτιδήποτε.

Επίσης η συγκεκριμένη έκδοση με τη θέση δίνει περισσότερη πληροφορία. Όχι μόνο αν υπάρχει κάτι αλλά και που υπάρχει.

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

Τέλος η χρήση ακεραίων αντί για λογικές τιμές μπορεί να κάνει κάτι που δεν το κάνει η μια λογική τιμή: Όταν κάνεις αναζήτηση σε ταξινομημένο και θέλεις να σταματήσεις μόλις περάσεις τη θέση και δε βρεις το στοιχείο, τότε γίνεται εύκολα με ακεραίους. Πχ αρχικά έχεις τιμή 0 που σημαίνει «Δεν έχει βρεθεί». 1 σημαίνει «βρέθηκε» και 2 σημαίνει «πέρασε». Έτσι μπορείς να καταλάβεις για πιο λόγο σταμάτησε η επανάληψη.

Με 2 λόγια μια αναζήτηση με Όσο και εύρεση θέσης είναι η καλύτερη λύση.

[alex599]

Πέρυσι φοίτησα και εγώ στην Γ λυκείου και ένας κώδικας όπως ο παρακάτω δεν ήταν αποδεκτός:

διάβασε κλειδι
Για Ι από 1 μέχρι Ν
    Αν πίνακας[Ι]=κλειδί τότε
        θέση<-Ι
        Ι<-Ν+1      !βίαιη έξοδος από το βρόχο.
    τέλος_αν
τέλος_επανάληψης
.....

Σε εφαρμογή όμως ο κώδικας "τρέχει" μια χαρά οπότε η αναζήτηση μπορεί να γίνει και με χρήση της για όπως γίνεται και στην όσο.
Γιατί όμως θεωρείται λάθος?Αν κάποιος μαθητής το έγραφε αυτό θα ήταν λάθος/

[andreas_p]

Ψάξε το ΤΜ.

[evry]

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

Πέρυσι φοίτησα και εγώ στην Γ λυκείου και ένας κώδικας όπως ο παρακάτω δεν ήταν αποδεκτός:

διάβασε κλειδι
Για Ι από 1 μέχρι Ν
    Αν πίνακας[Ι]=κλειδί τότε
        θέση<-Ι
        Ι<-Ν+1      !βίαιη έξοδος από το βρόχο.
    τέλος_αν
τέλος_επανάληψης
.....

Σε εφαρμογή όμως ο κώδικας "τρέχει" μια χαρά οπότε η αναζήτηση μπορεί να γίνει και με χρήση της για όπως γίνεται και στην όσο.
Γιατί όμως θεωρείται λάθος?Αν κάποιος μαθητής το έγραφε αυτό θα ήταν λάθος/

[P.Tsiotakis]

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

[Σούλας Βασίλης]

Να δώσω λίγο τροφή για συζήτηση; Στα θέματα των Πανελληνίων στο τέλος αναφέρονται οδηγίες προς εξεταζομένους. Μια οδηγία λοιπόν λέει:

Κάθε απάντηση επιστημονικά τεκμηριωμένη είναι αποδεκτή.