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

[Keep Growing]

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

[olga_ath]

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

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

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

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

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

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

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

ευχαριστώ όλους

[evry]

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

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

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

[olga_ath]

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

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

Παντως με το Horner δεν το συνέδεσα τώρα το συνειδητοποίσα παρότι ήταν ένα από τα θέματα που μου άρεσαν πάλαι ποτέ που ήμουν μαθήτρια....

[Keep Growing]

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

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

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

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

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

[evry]

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

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

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

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


Τι λέτε? θα μπορούσε να μπει άσκηση στο μάθημά μας?
Προσωπικά μου φαίνεται πολύ καλό

[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

[petrosp13]

Ουσιαστικά ζητάς την μέγιστη άνοδο που σημειώθηκε

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

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

[evry]

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

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

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

[odysseas]

Τι λέτε? θα μπορούσε να μπει άσκηση στο μάθημά μας?
Προσωπικά μου φαίνεται πολύ καλό.

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

Ας δούμε το παρακάτω
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]

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

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

[gthal]

Τι λέτε? θα μπορούσε να μπει άσκηση στο μάθημά μας?
Προσωπικά μου φαίνεται πολύ καλό

Υπέροχο θέμα!!!
Όσον αφορά την ΑΕΠΠ όμως, προσωπικά πιστεύω ότι το ποσοστό % των μαθητών που μπορούν να αναλύσουν αυτό το πρόβλημα θα είναι άνετα μονοψήφιο. Άαααανετα. Δυστυχώς. 
(ίσως και να είμαι φύσει απαισιόδοξος - τι να πω)