Δύσκολες Ασκήσεις στις Δομές Επανάληψης

Ξεκίνησε από olga_ath, 13 Οκτ 2010, 02:47:27 ΜΜ

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

Keep Growing

Μια πρόταση λύσης παρουσιάζω στο συνημμένο.
Αλλά οι μαθητές πριν το δουν, καλά θα ήταν να προσπαθήσουν μόνοι τους.
Ο Έρωτας (του Εκπ/κου Πληροφορικού) στ' αλώνια της καλδέρας (του υπνωτισμού).

olga_ath

Παράθεση από: Keep Growing στις 15 Ιαν 2011, 03:29:17 ΜΜ
Μια πρόταση λύσης παρουσιάζω στο συνημμένο.
Αλλά οι μαθητές πριν το δουν, καλά θα ήταν να προσπαθήσουν μόνοι τους.

οκ τώρα το καταλαβα διακρίνεις και περίπτωσει αν ο αριθμός είναι μονοψήφιος. Ωραία η λύση σου !!!

Στην τελευταία άσκηση του κ. Ευριπίδη με το κατοπτρο εγώ θα εδινα αυτή τη λύση.

Αλγόριθμος κάτοπτρο

Διάβασε χ
νέος ← 0
digit ← 0
Οσο χ >0 επανάλαβε
   
   digit← χ Mod 10
   νέος ← νέος *10 + digit
   χ← χ div 10
Τέλος_Επανάληψης

Γράψε νέος
Τέλος κάτοπτρο

Μηπως καταλαβα λάθος την εκφώνηση;

ευχαριστώ όλους
Doubt everyone and first of all yourself

evry

Η λύση του Παναγιώτη είναι το πρώτο πράγμα που θα σκεφτόταν ένας μαθητής.  Πρώτα να βρει πόσα ψηφία έχει ο αριθμός και στη συνέχεια να τα υπολογίσει με τη σειρά. Ο αλγόριθμος αυτός έχει πολυπλοκότητα O(n2) (n ο αριθμός των ψηφίων)

Στη συνέχεια μπορούμε να ρωτήσουμε τους μαθητές πως μπορεί να γίνει αυτό με ένα μόνο πέρασμα, δηλαδή τη στιγμή που παίρνεις τα ψηφία ένα-ένα να υπολογίζεις τον κατοπτρικό χωρίς εκείνη τη στιγμή να ξέρεις πόσα ψηφία έχει τελικά. Αυτή είναι και η βέλτιστη λύση με γραμμική πολυπλοκότητα Ο(n).
Αυτή τη λύση έδωσε η Όλγα.
Φυσικά για να οδηγήσουμε τους μαθητές σε αυτόν τον δρόμο πρέπει να τους δώσουμε κάποιες υποδείξεις, αλλιώς είναι πολύ δύσκολο να το σκεφτούν μόνοι τους.
Η υπόδειξη που θα δοθεί στους μαθητές καλό θα ήταν να δοθεί με τη μορφή παραδείγματος π.χ.  1234 = 4 + 10*(3 +10*(2 + 10*1))
και να γίνει αντιπαραβολή με το πλήθος των πράξεων που θα γίνουν αν το υπολογίσουμε κανονικά

Όλγα δεν ξέρω αν το κατάλαβες αλλά μόλις έδωσες μια γρήγορη υλοποίηση του βέλτιστου υπολογισμού της τιμής ενός πολυωνύμου με το σχήμα Horner (κάτι σου θυμίζει ε; >:D)
Το ενδιαφέρον είναι ότι οι μαθητές έχουν κάνει το σχήμα Horner στην Β' λυκείου οπότε το ξέρουν

What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

olga_ath

Καλησπέρα και από μένα ξανά :-)

Λοιπόν αυτη την άσκηση την δίνω ως δωράκι για το σπίτι σε όσους καταφέρνουν να λύσουν αυτή που θεωρείται πιο εύκολη και έτσι η δυσκολία αυξάνει σταδιακά. Να γίνει αλγόριθμος ο οποίος να βρίσκει και να εκτυπώνει τα ψηφία ενός αριθμού.
Ετσι συνηθίζουν στην ιδέα στο πως αποκόπτουμε ένα ψηφίο από έναν ακεραιο πχ 3456 και μετά τους δίνω την υπόδειξη : Και τώρα αν ήθελα να δημιουργήσω τον αναποδο τι θα έκανα. Θα αλλαζα την σειρά οι παλιές μονάδες θα ήταν οι παλιές χιλιάδες οι δεκάδες οι παλίες εκατοντάδες κτλ.. και έτσι το σκέφtoνται πιο εύκολα τα παιδιά κατά την γνώμη μου..

Παντως με το Horner δεν το συνέδεσα τώρα το συνειδητοποίσα παρότι ήταν ένα από τα θέματα που μου άρεσαν πάλαι ποτέ που ήμουν μαθήτρια.... :laugh:
Doubt everyone and first of all yourself

Keep Growing

Βέβαια, εγώ ξεκίνησα από την ιδέα του  υπολογισμού της δύναμης του 10, του πιο σημαντικού ψηφίου του αριθμού, ώστε στη συνέχεια να υπολογίσω το ανάπτυγμα του νέου αριθμού, αλλά η ουσία είναι αυτή που είπε ο Ευριπίδης, ότι χρησιμοποιήθηκαν 2 δομές ΟΣΟ για n επαναλήψεις η κάθε μία. 
Ο Έρωτας (του Εκπ/κου Πληροφορικού) στ' αλώνια της καλδέρας (του υπνωτισμού).

Νίκος Αδαμόπουλος

Παράθεση από: evry στις 15 Ιαν 2011, 04:18:51 ΜΜ
Φυσικά για να οδηγήσουμε τους μαθητές σε αυτόν τον δρόμο πρέπει να τους δώσουμε κάποιες υποδείξεις, αλλιώς είναι πολύ δύσκολο να το σκεφτούν μόνοι τους.

Το:
   νέος ← νέος *10  ...
και το:
   χ← χ div 10

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

evry

Το θέμα της 1ης φάσης του Πανελλήνιου Διαγωνισμού Πληροφορικής φέτος,

ΜΕΓΙΣΤΟΠΟΙΗΣΗ ΚΕΡΔΟΥΣ

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

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


Τι λέτε? θα μπορούσε να μπει άσκηση στο μάθημά μας?
Προσωπικά μου φαίνεται πολύ καλό
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

petrosp13

Μπορείς να το εξηγήσεις λίγο γιατί η απλοϊκή λύση που καταλαβαίνω αφορά την εύρεση min και max
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

evry

Εεε, έχεις κάποιο δίκιο, έπρεπε να δώσω και ένα παράδειγμα για να φανεί τι ζητάει

Ας δούμε το παρακάτω

10 9 8 4 6 5 7 6 6 5 4 3 3

πότε πρέπει να αγοράσεις τη μετοχή? όταν έχει τιμή 4, αλλά θα την πουλήσεις όταν πάει 7 ώστε να έχεις κέρδος 7-4= 3
όμως ούτε το 4 είναι το min ούτε το 7 είναι το max >:(

παίζει ρόλο η σειρά που σου έρχονται δηλαδή.

Για περισσότερες πληροφορίες δίνω και το λινκ από όπου το κατέβασα
http://www.pdp.gr/files/23a/PDP_23_A.doc
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

petrosp13

Ουσιαστικά ζητάς την μέγιστη άνοδο που σημειώθηκε
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

Νίκος Αδαμόπουλος

Συνάδελφοι προσοχή: η υποβολή λύσεων για την Α φάση του διαγωνισμού δεν έχει λήξει ακόμα (έως 23-1-2011) οπότε ας μην σχολιάσουμε και πολλά, πόσο μάλλον να ανεβάσουμε εδώ και λύση!  :police:

evry

Αυτή η μικρή  :) λεπτομέρεια ομολογώ ότι μου ξέφυγε, δεν ήξερα ότι έδωσαν παράταση, αλλά και λύση να ανεβάσουμε τεχνικά δεν είναι η σωστή αφού θα είναι σε ΓΛΩΣΣΑ και δεν μπορεί να γίνει δεκτή στον διαγωνισμό :D

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

Παράθεση από: Νίκος Αδαμόπουλος στις 16 Ιαν 2011, 09:46:54 ΜΜ
Συνάδελφοι προσοχή: η υποβολή λύσεων για την Α φάση του διαγωνισμού δεν έχει λήξει ακόμα (έως 23-1-2011) οπότε ας μην σχολιάσουμε και πολλά, πόσο μάλλον να ανεβάσουμε εδώ και λύση!  :police:
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

odysseas

Παράθεση από: evry στις 16 Ιαν 2011, 08:27:39 ΜΜ
Τι λέτε? θα μπορούσε να μπει άσκηση στο μάθημά μας?
Προσωπικά μου φαίνεται πολύ καλό.

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

Παράθεση από: evry στις 16 Ιαν 2011, 08:58:46 ΜΜ
Ας δούμε το παρακάτω
10 9 8 4 6 5 7 6 6 5 4 3 3
πότε πρέπει να αγοράσεις τη μετοχή? όταν έχει τιμή 4, αλλά θα την πουλήσεις όταν πάει 7 ώστε να έχεις κέρδος 7-4= 3

Θέλει λίγη προσοχή όμως. Το κέρδος είναι 7 / 4 και όχι 7 - 4. Το τονίζω γιατί στο δεύτερο παράδειγμα της εκφώνησης που η ακολουθία είναι: 9 8 15 5 6 9 8 10 3 5, η διαφορά 15 - 8 είναι η μεγαλύτερη, αλλά ο λόγος 10 / 5 είναι που δίνει το μεγαλύτερο "κέρδος".

evry

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

Παράθεση από: odysseas στις 16 Ιαν 2011, 11:22:37 ΜΜ
Θέλει λίγη προσοχή όμως. Το κέρδος είναι 7 / 4 και όχι 7 - 4. Το τονίζω γιατί στο δεύτερο παράδειγμα της εκφώνησης που η ακολουθία είναι: 9 8 15 5 6 9 8 10 3 5, η διαφορά 15 - 8 είναι η μεγαλύτερη, αλλά ο λόγος 10 / 5 είναι που δίνει το μεγαλύτερο "κέρδος".
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gthal

Παράθεση από: evry στις 16 Ιαν 2011, 08:27:39 ΜΜ
Τι λέτε? θα μπορούσε να μπει άσκηση στο μάθημά μας?
Προσωπικά μου φαίνεται πολύ καλό
Υπέροχο θέμα!!!
Όσον αφορά την ΑΕΠΠ όμως, προσωπικά πιστεύω ότι το ποσοστό % των μαθητών που μπορούν να αναλύσουν αυτό το πρόβλημα θα είναι άνετα μονοψήφιο. Άαααανετα. Δυστυχώς.  :'(
(ίσως και να είμαι φύσει απαισιόδοξος - τι να πω)
Φιλικά,
Γιώργος Θαλασσινός