Τυποποίηση vs Σκέψης

Ξεκίνησε από evry, 05 Απρ 2011, 04:42:16 ΜΜ

« προηγούμενο - επόμενο »

evry

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

Άσκηση
Να γράψετε αλγόριθμο ο οποίος να διαβάζει αριθμούς μέχρι να δοθεί 0 και να εμφανίζει τους Ν μεγαλύτερους, για δεδομένο Ν.

(β έκδοση) : να εμφανίζει τους αριθμούς με τη σειρά που τους διάβασε
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

meteo_xampos

Καμία λύση κανείς? Είναι για μαθητές το πρόβλημα αυτό;

odysseas

Παράθεση από: evry στις 05 Απρ 2011, 04:42:16 ΜΜ
προσπαθούν να το λύσουν ad hoc ή να εφαρμόσουν κάποιους έτοιμους αλγορίθμους?

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

Κατά τ' άλλα, θες να δώσουμε και λύση ή απλά να συζητήσουμε το γενικό ερώτημα;

Παράθεση από: evry στις 05 Απρ 2011, 04:42:16 ΜΜ
(β έκδοση) : να εμφανίζει τους αριθμούς με τη σειρά που τους διάβασε

Εννοείς να εμφανίζει τους Ν μεγαλύτερους αριθμούς με τη σειρά που τους διάβασε;

evry

γιατί όχι και τα δύο, αλλά κατά βάση το δεύτερο. Δηλαδή το πρόβλημα είναι πως θα εξηγήσουμε σε έναν μαθητή, ώστε να τον πείσουμε, ότι η λύση που έκανε μπορεί να βγάζει σωστό αποτέλεσμα αλλά δεν είναι "τόσο σωστή" όσο νομίζει. Για παράδειγμα πόσο επιστημονικά τεκκμηριωμένη είναι η εύρεση μεγίστου με ταξινόμηση ή ακόμα καλύτερα η ταξινόμηση αριθμών με την μέθοδο BogoSort (ή MonkeySort)  http://en.wikipedia.org/wiki/Bogosort.
Θα μπορούσε αυτό να θεωρηθεί λύση? Γενικά το γεγονός ότι η απόδοση είναι εκτός ύλης, δημιουργεί κατά τη γνώμη μου πολλά προβλήματα
Παράθεση από: odysseas στις 06 Απρ 2011, 08:30:22 ΜΜ
Κατά τ' άλλα, θες να δώσουμε και λύση ή απλά να συζητήσουμε το γενικό ερώτημα;

Και για να δείξω τι ακριβώς εννοώ θα αναφέρω τη λύση που μου έχουν δώσει οι περισσότεροι μαθητές για το παραπάνω πρόβλημα:

(Καταρχήν λέμε στους μαθητές ότι θα δοθούν τουλάχιστον 50 αριθμοί. Οπότε η δουλειά είναι από εκεί και πέρα)

Αρχή Αλγορίθμου
0. Τοποθετώ τους πρώτους 50 αριθμούς σε έναν πίνακα Α[50]
1. Διαβάζω τον επόμενο αριθμό
2. Αντιγράφω τους 50 αριθμούς που έχω σε έναν νέο πίνακα Β[51]  και βάζω στην τελευταία θέση τον αριθμό που μόλις διάβασα
3. Ταξινόμηση στον πίνακα Β
4. Αντιγραφή των πρώτων 50 στοιχείων του Β στον Α
5. Συνεχίζω ακάθεκτος
Τέλος Αλγορίθμου

Η παραπάνω λύση είναι απαράδεκτη από επιστημονικής πλευράς? Θα γινόταν ποτέ δεκτή σε οποιοδήποτε πανεπιστήμιο του κόσμου? Αλλά και παιδαγωγικά να το πάρει κανείς. Δεν δείχνει ότι απλά έχουμε εκπαιδεύσει τα παιδιά να προσπαθούν να εφαρμόσουν έτοιμες συνταγές και όχι να επινοούν τις δικές τους? Πως μπορούμε μετά να μιλάμε για αλγοριθμική σκέψη? Δεν είναι υποκρισία?

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

Το καλύτερο όμως είναι ότι όταν την έβαλα σε μαθητές που δεν είχαν διδαχθεί την ταξινόμηση, αρκετοί βρήκαν τη σωστή λύση. Τυχαίο??

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

Κουβέντα να γίνεται :)
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

tom

αλγόριθμος μεγαλύτεροι
 δεδομένα //ν//
 μ ← 0
 κ ← 0
 διάβασε αρ
 μαχ ← αρ
 όσο αρ<>0 επανάλαβε 
   μ ← μ+1
   αν αρ>=μαχ και κ<=ν τότε
     αν κ=ν τότε 
        κ← 0 
     τέλος_αν
     μαχ ← αρ 
     κ ←  κ+1
     θμαχ[κ]← μ
   τέλος_αν
   αριθμοί[μ]← αρ
   διάβασε αρ
 τέλος_επανάληψης
 εμφάνισε "οι", ν, " μεγαλύτεροι:"
 αν ν>μ τότε
  ν← μ
 τέλος_αν
 για ι από 1 μέχρι ν
  εμφάνισε αριθμοί[θμαχ[ι]]
 τέλος_επανάληψης
τέλος μεγαλύτεροι


Αυτή σου φαίνεται πολύπλοκη? Λάβε υπ'οψιν ότι φέτος δεν ασχολούμαι καθόλου με ΑΕΠΠ και είμαι deforme  ;D
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

tom

Κάποιες φορές χάνει έναν αριθμό από τους Ν μεγαλύτερους  η λύση που έδωσα... >:(
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

sstergou

Χρησιμοποιεί και πίνακα με άγνωστο πλήθος στοιχείων ακόμα και κατά την διάρκεια της εκτέλεσης.

Για κάνε και μια επεξήγηση όμως για το πως δουλεύει :)

tom

Παράθεση από: sstergou στις 06 Απρ 2011, 10:12:20 ΜΜ
Χρησιμοποιεί και πίνακα με άγνωστο πλήθος στοιχείων ακόμα και κατά την διάρκεια της εκτέλεσης.
Μη μου περιορίζεις της σκέψη.  :) Έστω ότι το μέγεθος του θμαχ[] είναι ν και του αριθμοί όσο θες  :) .

Σκέφτηκα να κρατάω τις θέσεις των ν μεγαλύτερων στοιχείων μέσα σε ξεχωριστό πίνακα. Όταν γεμίσει με ν μεγαλύτερους και εξακολουθούν να δίδονται στοιχεία, τον μηδενίζω και κρατάω τα αμέσως επόμενα ν μεγαλύτερα...δε ξέρω τι λέτε? 
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

evry

αντιθέτως, αυτό σημαίνει ότι είσαι σε φόρμα  >:D, εγώ που κάνω κάθε χρόνο ΑΕΠΠ, κοιτάω τον κώδικά σου και και μου πήρε ώρα να καταλάβω τι κάνεις (και ακόμα δεν είμαι σίγουρος). Για παράδειγμα ο πίνακας Θμαχ αν κατάλαβα καλά δεν έχει σταθερό μέγεθος, έτσι δεν είναι?
   Ουσιαστικά ο θmax είναι ένας πίνακας δεικτών στους αριθμούς που βρίσκονται στον άλλον πίνακα. Αλλά μου φαίνεται ότι δεν κράτας τους N μεγαλύτερους


Παράθεση από: tom στις 06 Απρ 2011, 09:52:30 ΜΜ
Αυτή σου φαίνεται πολύπλοκη? Λάβε υπ'οψιν ότι φέτος δεν ασχολούμαι καθόλου με ΑΕΠΠ και είμαι deforme  ;D
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

evry

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

και επίσης αυτό που είπε ο Στάθης, ότι δεν ξέρεις πόσοι αριθμοί θα σου δωθούν άρα δεν μπορείς να τους βάλεις όλους σε πίνακα, μόνο τους Ν μεγαλύτερους κάθε φορά
Παράθεση από: tom στις 06 Απρ 2011, 10:19:12 ΜΜ
Σκέφτηκα να κρατάω τις θέσεις των ν μεγαλύτερων στοιχείων μέσα σε ξεχωριστό πίνακα. Όταν γεμίσει με ν μεγαλύτερους και εξακολουθούν να δίδονται στοιχεία, τον μηδενίζω και κρατάω τα αμέσως επόμενα ν μεγαλύτερα...δε ξέρω τι λέτε? 

edit: οκ το κατάλαβα τώρα, αλλά δεν έχω καταλάβει τι ήθελες να κάνεις, έχω την εντύπωση ότι πήγαινες να κάνεις κάτι άλλο και κάτι σου ξέφυγε. Για να δεις τι πάει στραβά σκέψου να σου δώσω για ν=5 τους αριθμούς 80, 90, 1, 2,3,4,5, 100 ποιους αριθμούς θα εμφανίσει. Λογικά θα χάσει το 80.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

tom

Παράθεση από: evry στις 06 Απρ 2011, 10:29:33 ΜΜ
Για παράδειγμα ο πίνακας Θμαχ αν κατάλαβα καλά δεν έχει σταθερό μέγεθος, έτσι δεν είναι?
Έχει και είναι ν.
Παράθεση από: evry στις 06 Απρ 2011, 10:29:33 ΜΜ
Ουσιαστικά ο θmax είναι ένας πίνακας δεικτών στους αριθμούς που βρίσκονται στον άλλον πίνακα....
Σωστά.

Παράθεση από: evry στις 06 Απρ 2011, 10:33:41 ΜΜ
Ένα λεπτό, όταν τον μηδενίζεις δεν χάνεις όλα τα στοιχεία που έχεις ήδη βάλει μέσα? δηλαδή αν εγώ δώσω ν+5 αριθμούς
και τύχει οι πρώτοι 5 να είναι οι μεγαλύτεροι όλων, δεν θα τους χάσεις στο τέλος?
ή κάτι δεν έχω καταλάβει καλά
Μα αν εσύ θέλεις για παράδειγμα να εμφανίζεις τους 3 μεγαλύτερους και γεμίσει ο πίνακας με 3 θέσεις και στη συνέχεια ο χρήστης δώσει 3 άλλους μεγαλύτερους δεν πρέπει οι τελευταίοι να πάρουν τη θέση των πρώτων?

Παράθεση από: evry στις 06 Απρ 2011, 10:33:41 ΜΜ
και επίσης αυτό που είπε ο Στάθης, ότι δεν ξέρεις πόσοι αριθμοί θα σου δωθούν άρα δεν μπορείς να τους βάλεις όλους σε πίνακα, μόνο τους Ν μεγαλύτερους κάθε φορά
Αυτό ας το αφήσουμε τελευταίο. Είπες "να γραφεί αλγόριθμος..." και επειδή ξέρω ότι τα παραδείγματά σου ξεφεύγουν λίγο από το βιβλίο πήρα την πρωτοβουλία να θεωρήσω οτι εννοούσες "να γραφεί αλγόριθμος που μπορεί να υλοποιηθεί σε κάποια γλώσσα προγραμματισμού και όχι απαραίτητα σε ΓΛΩΣΣΑ".  :D
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

sstergou

Μισό λεπτό, έχω μπερδευτεί... Θωμά αν κάποιος δώσει τους αριθμούς
90
80
1
2
3
4
5
70
0

ο αλγόριθμος που έδωσες δεν βρίσκει τους (π.χ. 3) μεγαλύτερους αλλά μέσα στον πίνακα θμαχ βάζει μόνο τον πρώτο. Αυτό συμβαίνει γιατί όλοι οι υπόλοιποι "μεγαλύτεροι" είναι μικρότεροι από τον 90.

Ευριπίδη είμαι περίεργος να δω την λύση σου και αν υπάρχει τρόπος να λυθεί αυτό μόνο με μία επανάληψη...
2 λύσεις απλές στην σύλληψη είναι :

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

evry

Παράθεση από: tom στις 06 Απρ 2011, 10:45:36 ΜΜ
Μα αν εσύ θέλεις για παράδειγμα να εμφανίζεις τους 3 μεγαλύτερους και γεμίσει ο πίνακας με 3 θέσεις και στη συνέχεια ο χρήστης δώσει 3 άλλους μεγαλύτερους δεν πρέπει οι τελευταίοι να πάρουν τη θέση των πρώτων?
Ακριβώς. Στον δικό σου κώδικα όμως δεν την παίρνουν. για παράδειγμα αν δώσεις   100 90 6 5 200, τότε το 200 δεν θα πάρει τη θέση του 100? Θα έπρεπε να πάρει τη θέση του 6 όμως.
Επίσης αλλάζεις την τιμή του ν. Αυτό είναι το δεδομένο Ν που είναι σταθερό εξαρχής. Δηλαδή αν κάποιος δώσει τους αριθμούς 100 99 98 .....  1 τότε θα τους πάρει όλους και όχι π.χ. τους Ν=10 μόνο.

Παράθεση
Αυτό ας το αφήσουμε τελευταίο. Είπες "να γραφεί αλγόριθμος..." και επειδή ξέρω ότι τα παραδείγματά σου ξεφεύγουν λίγο από το βιβλίο πήρα την πρωτοβουλία να θεωρήσω οτι εννοούσες "να γραφεί αλγόριθμος που μπορεί να υλοποιηθεί σε κάποια γλώσσα προγραμματισμού και όχι απαραίτητα σε ΓΛΩΣΣΑ".  :D
ναι οκ, αλλά για φαντάσου ένα πρόβλημα στο οποίο έχεις συνεχή ροή αριθμών όπως για παράδειγμα ένας αλγόριθμος που επεξεργάζεται ένα data stream το οποίο μπορεί να μην τελειώνει ποτέ. Δεν μπορεί να το βάλει όλο σε έναν πίνακα. Τι θα πρέπει να κάνει αν θέλει να φυλάει κάθε φορά τα Ν καλύτερα. Αυτό εννοούσα. Ίσως να μην είχα διατυπώσει καλά το πρόβλημα και να κατάλαβες άλλο
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

evry

    Παράθεση από: sstergou στις 06 Απρ 2011, 11:00:10 ΜΜ
    Ευριπίδη είμαι περίεργος να δω την λύση σου και αν υπάρχει τρόπος να λυθεί αυτό μόνο με μία επανάληψη...
    καλά δεν είπα και με μια, αν και τώρα που σκέφτομαι υπάρχει αλλά ουσιαστικά θα κάνεις κάποιο τέχνασμα με μια δομή επιλογής μέσα (ουσιαστικά θα κάνεις τη διπλή μονή, θα το δω νομίζω πως γίνεται)

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

    Η πιο απλή λύση όμως είναι η παρακάτω

    Βρες κάθε φορά τον χειρότερο και δες αν αυτός που ήρθε είναι καλύτερός του.
    Αν ναι βαλτόν στην θέση του.

    Τόσο απλό!!!
    όταν λέμε Ν μεγαλύτεροι δεν θέλουμε να είναι και ταξινομημένοι, απλά να είναι οι καλύτεροι, τώρα σε ποια σειρά θα είναι δεν μας ενδιαφέρει ;)

    Δεν είναι απλό ?? και όμως δεν το σκέφτεται κανένας, όλοι πάνε στην ταξινόμηση[/list]
    What I cannot create I do not understand -- Richard Feynman
    http://evripides.mysch.gr

    meteo_xampos

    Για δείτε και τη δική μου λύση... Αφού γνωρίζουμε ότι είναι Ν οι μεγαλύτεροι αριθμοί, μπορώ να χρησιμοποιήσω έναν πίνακα ΠΙΝ[Ν] για να βάλω τους Ν μεγαλύτερους...  Διαβάζω τους αριθμούς και τους πρώτους Ν αριθμούς, τους τοποθετώ στον πίνακα ΠΙΝ[Ν], και για κάθε επόμενο που διαβάζω, ελέγχω αν είναι μεγαλύτερος από τον μικρότερο του πίνακα, και αν είναι τον βάζω στη θέση του μικρότερου
    αριθμού...

    Αλγόριθμος τάδε
    Δεδομένα //Ν//
    Διάβασε αρ
    π← 0
    Όσο αρ>0 επανάλαβε
       π← π+1
       Αν π<=Ν τότε
          ΠΙΝ[π]← αρ
       Αλλιώς
          μικ← ΠΙΝ[1]
          θ← 1
          Για ι από 2 μέχρι Ν
             Αν ΠΙΝ[ι]<μικ τότε
                μικ← ΠΙΝ[ι]
                θ← ι
             Τέλος_Αν
          Τέλος_Επανάληψης
          Αν αρ>μικ τότε
             ΠΙΝ[θ]← αρ
          Τέλος_Αν
       Τέλος_Αν
       Διάβασε αρ
    Τέλος_επανάληψης
    Για ι από 1 μέχρι Ν
       Εμφάνισε ΠΙΝ[ι]
    Τέλος_επανάληψης
    Τέλος τάδε