Υπολογίζοντας το εμβαδό κάτω από την καμπύλη με την Πληροφορική των Πανελλαδικών

Στο μάθημα των Μαθηματικών Προσανατολισμού… Γ’ Λυκείου ο υπολογισμός του εμβαδού ανάμεσα σε μια καμπύλη και τον άξονα των x από μία τιμή α μέχρι μία τιμή β γίνεται κλασικά μέσω του υπολογισμού της έκφρασης του αόριστου ολοκληρώματος: αν αυτή η έκφραση είναι G(x), τότε το ζητούμενο εμβαδό είναι G(β)-G(α). Όμως, ο υπολογισμός της έκφρασης του αόριστου ολοκληρώματος δεν είναι πάντα εύκολη υπόθεση! Δοκιμάστε για παράδειγμα την ολοκλήρωση της παρακάτω συνάρτησης:

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

Το παραπάνω πρόγραμμα βασίζεται άμεσα στον ορισμό του ορισμένου ολοκληρώματος, ως το όριο του αθροίσματος των εμβαδών των ορθογωνίων στα οποία μπορεί να χωριστεί η επιφάνεια κάτω από την καμπύλη, καθώς το πλήθος αυτών των ορθογωνίων τείνει στο άπειρο (ισοδύναμα καθώς η ποσότητα δχ τείνει στο 0) – βλ. ενότητα 3.4, “Ορισμένο ολοκλήρωμα”, Μαθηματικά Γ’ Τάξης ΓΕΛ Ομάδας Προσανατολισμού... Από αυτόν τον ορισμό συνεπάγεται ότι μπορούμε να πετύχουμε όσο καλή προσέγγιση του εμβαδού θέλουμε επιλέγοντας μια ανάλογα μεγάλη τιμή του πλήθους των ορθογωνίων.

Το τελευταίο πλήθος εκφράζεται από την μεταβλητή ν στο παραπάνω πρόγραμμα, ενώ το εμβαδό του ι-οστού ορθογωνίου από την έκφραση f(α+ι*δχ)*δχ, όπου δχ είναι η μία διάσταση του ορθογωνίου και f(α+ι*δχ) η άλλη, όπου f είναι μία συνάρτηση με δεδομένο αναλυτικό τύπο, της οποίας κάποιο ορισμένο ολοκλήρωμα ζητείται– τέτοιες συναρτήσεις μπορούν εύκολα να κωδικοποιηθούν στην ΓλώσσαΗ μεταβλητή Σ κρατάει το άθροισμα των εμβαδών των ορθογωνίων.

Η μεταβλητή δχ είναι αντιστρόφως ανάλογη της μεταβλητής ν: όσο μεγαλύτερη η μία, τόσο μικρότερη η άλλη. Για την παραπάνω εμφανιζόμενη τιμή δχ=0.001 το πρόγραμμα δίνει ικανοποιητική επίλυση σε διάφορες περιπτώσεις, αλλά ανάλογα με το εύρος του διαστήματος [α, β] και την απαιτούμενη τιμή δχ, ο αριθμός ν μπορεί να υπερβαίνει το φράγμα 105. Η συγκεκριμένη τιμή επιλέχτηκε λόγω του ότι η υπολογιστική της αντιμετώπιση είναι εφικτή στους περισσότερους Η/Υ που κυκλοφορούν εκεί έξω. Φυσικά, μπορείτε να θέσετε μεγαλύτερη τιμή, ανάλογα και με τις δυνατότητες του υπολογιστή σας.

Ας δούμε το πρόγραμμά μας στην πράξη. Θα υπολογίσουμε το παρακάτω ολοκλήρωμα (το οποίο δεν μπορεί να υπολογιστεί με την μεθοδολογία που περιγράφεται στα Μαθηματικά Προσανατολισμού… της Γ’ ΓΕΛ ):

Κωδικοποιούμε την συνάρτηση f (και φυσικά θέτουμε α=0 και β=10):

Η εκτέλεση του προγράμματος στον Διερμηνευτή της Γλώσσας δίνει 0.88672693.  Δοκιμάζουμε μια μικρότερη τιμή για το δχ, 0.0001 και παίρνουμε 0.88627693. Παρατηρείστε ότι ο αριθμός αριστερά από την υποδιαστολή και τα τρία πρώτα δεκαδικά ψηφία δεν άλλαξαν, γεγονός που συνιστά μια ένδειξη (όχι όμως  και απόδειξη) ότι ο αριθμός αριστερά από την υποδιαστολή και τα τρία πρώτα δεκαδικά του αποτελέσματος είναι αυτά ακριβώς! Ας τσεκάρουμε το αποτέλεσμά μας με ένα καταξιωμένο λογισμικό όπως το Wolfram|Alpha, το οποίο δίνει 0.886227

(https://www.wolframalpha.com/input/?i=integrate+e%5E%28-x%5E2%29+from+0+to+10)

Ας δούμε ένα άλλο ολοκλήρωμα, το οποίο επίσης δεν φαίνεται και πολύ εύκολο:

Κωδικοποιούμε την συνάρτηση στην Γλώσσα:

Η εκτέλεση του προγράμματος για δχ=0.001 δίνει 3052491665.01952. Δοκιμάζουμε για μικρότερο δχ, 0.0001, και παίρνουμε 3056988940.38689. Παρατηρούμε ότι τα τρία πρώτα ψηφία αριστερά από την υποδιαστολή δεν άλλαξαν. Το Wolfram|Alpha δίνει 3057488912.86528.

(https://www.wolframalpha.com/input/?i=integrate+%CF%87%5E%CF%87+from+0+to+10)

Η ποσοστιαία απόκλιση της δεύτερης τιμής που έδωσε το πρόγραμμά μας από την τιμή του Wolfram|Alpha είναι 0.016%.

Μια άλλη (κάπως πιο εύκολη για τα Μαθηματικά) περίπτωση:

Η επίλυση του αόριστου ολοκληρώματος που δίνει το Wolfram|Alpha μοιάζει κάπως έτσι:

https://www.wolframalpha.com/input/?i=integrate+1%2F%28%28x-3%29%5E4%2B1%2F2%29

Διαμορφώνουμε την f στο πρόγραμμά μας:

Οπότε, με την εκτέλεση για δχ=0.001 παίρνουμε 3.72272538. Δοκιμάζουμε για δχ=0.0001 και παίρνουμε 3.72272005. Παρατηρούμε ότι η τιμή αριστερά από την υποδιαστολή και τα πέντε πρώτα δεκαδικά ψηφία δεν άλλαξαν. To Wolfram|Alpha δίνει 3.72272

(https://www.wolframalpha.com/input/?i=integrate+1%2F%28%28x-3%29%5E4%2B1%2F2%29+from+0+to+10 )

Ας δούμε, τέλος, και μια εύκολη (για τα Μαθηματικά) περίπτωση:

Κωδικοποιούμε την συνάρτηση:

Για δχ=0.001 παίρνουμε 333.283335. Για δχ=0.0001 παίρνουμε 333.32833335.  Από την γνωστή παράγουσα της συνάρτησης παίρνουμε 10^3/3 =333.3333…

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

*Οι εικόνες του κώδικα του προγράμματος είναι screenshots από τον Διερμηνευτή της Γλώσσας

Γιώργος Μπουγιούκας

Επαναληπτική Άσκηση ΑΕΠΠ 2019-α

Photo by Franck V. on Unsplash

Θεωρείστε ως δεδομένη (δεν χρειάζεται να την κατασκευάσετε) την συνάρτηση υποάθροισμα(A, ν) : Λογική, όπου Α μονοδιάστατος πίνακας ακεραίων με 1000 στοιχεία και ν ακέραια μεταβλητή. Η συνάρτηση υποάθροισμα επιστρέφει Αληθής αν από την θέση 1 ως και την θέση ν του Α υπάρχουν κάποια στοιχεία (ένα ή περισσότερα) τα οποία έχουν άθροισμα μηδέν, σε διαφορετική περίπτωση επιστρέφει Ψευδής. Για παράδειγμα, αν ο Α περιέχει τις τιμές 5, -2, -3 από την θέση 1 μέχρι και την θέση ν, τότε η υποάθροισμα θα επιστρέψει Αληθής, αφού 5-2-3=0, ενώ αν ο Α περιέχει μόνο θετικές τιμές από την θέση 1 μέχρι και την θέση ν, θα επιστρέψει, προφανώς, Ψευδής.

Κατασκευάστε ένα πρόγραμμα το οποίο να διαβάζει τις τιμές χιλίων ακεραίων, να τις καταχωρίζει στον πίνακα Α και – με την βοήθεια της συνάρτησης υποάθροισμα – αν υπάρχουν κάποιες τιμές στο πίνακα Α που έχουν άθροισμα μηδέν, να εμφανίζει έναν (οποιονδήποτε) συγκεκριμένο συνδυασμό στοιχείων που έχουν άθροισμα μηδέν, αλλιώς να εμφανίζει το μήνυμα “δεν υπάρχει συνδυασμός στοιχείων με άθροισμα 0”. Για παράδειγμα, στο πρώτο από τα παραπάνω δύο παραδείγματα αρκεί να εμφανίσει τις τιμές 5,-2 και -3, ενώ στο δεύτερο θα πρέπει να εμφανίσει το μήνυμα “δεν υπάρχει συνδυασμός στοιχείων με άθροισμα 0”.

ΕΠΑΝΑΛΗΠΤΙΚΕΣ ΑΣΚΗΣΕΙΣ ΑΕΠΠ 2017 (Ι)

1) Ένας τετραγωνικός δισδιάστατος πίνακας S[ν,ν], όπου ν “τέλειο τετράγωνο” (δηλαδή η τετραγωνική του ρίζα είναι φυσικός αριθμός), είναι “πίνακας sudoku” όταν:

– Κάθε στοιχείο του S ανήκει στο σύνολο T={1,2,3,…,v}

– Κάθε γραμμή του S περιέχει κάθε στοιχείο του T.

– Κάθε στήλη του S περιέχει κάθε στοιχείο του T.

– Κάθε τετραγωνικός “υποπίνακας” με  γραμμές και στήλες του S, έτσι όπως οριοθετείται από τις έντονες διαχωριστικές γραμμές στο παρακάτω σχήμα/παράδειγμα για ν=9, περιέχει κάθε στοιχείο του Τ (σε κάθε πίνακα sudoku ν γραμμών και στηλών υπάρχουν ν τέτοιοι υποπίνακες).

Πίνακας sudoku για ν=9, με εννέα τετραγωνικούς υποπίνακες τριών γραμμών και τριών στηλών

Κατασκευάστε μία συνάρτηση σε “Γλώσσα” η οποία να δέχεται ως παράμετρο έναν δισδιάστατο πίνακα 100 γραμμών και 100 στηλών, και να επιστρέφει Αληθής αν ο πίνακας είναι sudoku, αλλιώς Ψευδής. Μπορείτε να κατασκευάσετε και να χρησιμοποιήσετε όσες επιπλέον συναρτήσεις θέλετε.

2) Ορίζουμε “γειτονιά Moore ακτίνας 1” (στο εξής γειτονιά Moore) ενός στοιχείου ενός δισδιάστατου πίνακα, έναν δισδιάστατο πίνακα 9 στοιχείων, ο οποίος περιέχει τα αμέσως γειτονικά στοιχεία βόρεια, βορειοδυτικά, δυτικά, νοτιοδυτικά, νότια, νοτιοανατολικά, ανατολικά και βορειοανατολικά του αρχικού στοιχείου (του δισδιάστατου πίνακα), καθώς και το ίδιο το αρχικό στοιχείο.

Γειτονιά Moore του C: συνίσταται στα κόκκινα κελιά, καθώς και το ίδιο το κελί C (Πηγή: Wikipedia)

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

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

Το τυχαίο στοιχείο του πίνακα Επόμενος, Επόμενος[i,j], ισούται με Αληθής, όταν το πλήθος των στοιχείων της γειτονιάς Moore του στοιχείου Προηγούμενος[i,j], από την οποία εξαιρούμε το στοιχείο Προηγούμενος[i,j], τα οποία έχουν την τιμή Αληθής είναι περιττός αριθμός.. Σε διαφορετική περίπτωση (αν είναι άρτιος αριθμός) ισούται με Ψευδής. Για τα στοιχεία εκείνα κάποιας γειτονιάς Moore, τα οποία υπερβαίνουν τα όρια του πίνακα, θεωρείστε τιμή ίση με Ψευδής.

3) Ένα χρώμα στον Η/Υ κωδικοποιείται συνήθως με μια τριάδα φυσικών αριθμών (r, g, b), όπου οι φυσικοί αριθμοί r(ed), g(reen), b(lue) ανήκουν συνήθως στο σύνολο {0, 1, 2, 3,…, 255} και ονομάζονται “συνιστώσες” του χρώματος. Για παράδειγμα η τριάδα (0, 0, 0) κωδικοποιεί το μαύρο χρώμα, η (255, 255, 255) το λευκό, η (255, 0, 0) το κόκκινο, κλπ. Μια ψηφιακή εικόνα κωδικοποιείται ως ένας δισδιάστατος πίνακας του οποίου κάθε στοιχείο είναι μια τριάδα (r, g, b) και αντιστοιχεί σε ένα στοιχειώδες τετραγωνίδιο της εικόνας (και της οθόνης του Η/Υ) γνωστό ως pixel (PICTureELement). Οι διαστάσεις αυτού του πίνακα ονομάζονται συνήθως “ανάλυση” της εικόνας (πχ 1024 ✕ 768). Ένας τρόπος για να αναπαρασταθεί στην “Γλώσσα” της ΑΕΠΠ  ένας δισδιάστατος πίνακας από τριάδες ακέραιων είναι ένας…τρισδιάστατος πίνακας ακέραιων. Για παράδειγμα για μια εικόνα με ανάλυση 1024 ✕ 768 μπορεί να χρησιμοποιηθεί ένας πίνακας Image[1024, 768, 3], όπου, για παράδειγμα, η συνιστώσα r του pixel στην 15η γραμμή και 25η στήλη του πίνακα δίνεται από το στοιχείο Image[15, 25, 1], η συνιστώσα g δίνεται από το Image[15, 25, 2], ενώ η συνιστώσα b από το Image[15, 25, 3].

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

Σε κάθε pixel, κάθε συνιστώσα τίθεται ίση με το ακέραιο μέρος του μέσου όρου των συνιστωσών.

Κατασκευάστε μια διαδικασία η οποία δέχεται ως παράμετρο έναν τρισδιάστατο πίνακα διαστάσεων 1024,  768, 3 ο οποίος κωδικοποιεί μια έγχρωμη εικόνα και επιστρέφει έναν άλλον τρισδιάστατο πίνακα των ίδιων διαστάσεων ο οποίος κωδικοποιεί την μετατροπή της προηγούμενης σε ασπρόμαυρη.

4) Δίνεται το παρακάτω τμήμα προγράμματος, όπου η μεταβλητή κ είναι ακέραιου τύπου και στο σημείο έναρξης της δομής επανάληψης ΟΣΟ έχει τιμή μεγαλύτερη από 1:

Άραγε, το παραπάνω τμήμα προγράμματος πληρεί το κριτήριο της “περατότητας” αλγορίθμου για κάθε τιμή μεγαλύτερη του 1 της ακέραιας μεταβλητής κ αμέσως πριν την έναρξη της δομής επανάληψης; Με άλλα λόγια η δομή επανάληψης κατά την εκτέλεσή της τερματίζει μετά από πεπερασμένο πλήθος βημάτων, για κάθε αρχική τιμή του κ μεγαλύτερη από 1; Ο γνωστός μαθηματικός Erdos έχει δηλώσει σχετικά με το προηγούμενο ερώτημα ότι “τα μαθηματικά δεν είναι έτοιμα ακόμα για τέτοια προβλήματα”. Το πρόβλημα αυτό είναι γνωστό ως “εικασία του Collatz” (η εικασία είναι ότι η δομή επανάληψης τερματίζει για κάθε κ>1) και παραμένει άλυτο μέχρι και σήμερα.

Θεωρείστε τον παρακάτω αλγόριθμο σε φυσική γλώσσα με βήματα:

1. Αν το παραπάνω τμήμα προγράμματος πληρεί το κριτήριο της περατότητας για κάθε αρχική τιμή της μεταβλητής κ, πήγαινε στο βήμα 4.

2. Γράψε “ΟΧΙ”.

3. Πήγαινε στο βήμα 5.

4. Γράψε “ΝΑΙ”

5. Τέλος αλγορίθμου.

Ποιο/ποια από τα παρακάτω χαρακτηριστικά του αλγορίθμου παραβιάζει ο προηγούμενος αλγόριθμος (τουλάχιστον την δεδομένη χρονική στιγμή, όπου η εικασία του Collatz δεν έχει αποδειχτεί, ούτε καταρριφθεί) και γιατί;

– Αποτελεσματικότητα

– Περατότητα

– Καθοριστικότητα

Γιώργος Μπουγιούκας

Μπορείς να βρεις τον κρυμμένο αριθμό;

Πρόβλημα 1

Μία/Ένας φίλ-η/ος σας σας προτείνει το ακόλουθο παιχνίδι:

«Έχω γράψει έναν φυσικό αριθμό σ’ ένα χαρτί. Μπορείς να βρεις τον αριθμό κάνοντας όσες ερωτήσεις θέλεις της μορφής «είναι ο αριθμός k;», όπου k οποιοσδήποτε φυσικός αριθμός; Εννοείται θα απαντήσω ειλικρινά σε κάθε ερώτησή σου».

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

Λύση

Είναι ο αριθμός 0;

Είναι ο αριθμός 1;

Είναι ο αριθμός 2;

Πρόβλημα 2

Θεωρείστε το Πρόβλημα 1 με τη διαφορά ότι αντί για φυσικό αριθμό ο κρυμμένος αριθμός είναι ακέραιος.

Λύση

Είναι ο αριθμός 0;

Είναι ο αριθμός 1;

Είναι ο αριθμός -1;

Είναι ο αριθμός 2;

Είναι ο αριθμός -2;

Ασκήσεις για εμβάθυνση

1) Θεωρείστε το Πρόβλημα 1 με τη διαφορά ότι αντί για φυσικό αριθμό ο κρυμμένος αριθμός είναι ρητός. Θεωρείστε ότι ένας ρητός αριθμός είναι ένα κλάσμα όπου ο αριθμητής είναι ακέραιος και ο παρονομαστής μη-μηδενικός ακέραιος. Αφού περιγράψετε τον αλγόριθμο, υλοποιήστε τον σε Γλώσσα, έτσι ώστε ο/η φίλ-ος/η σας να μπορεί να παίξει το παιχνίδι με το πρόγραμμά σας στον υπολογιστή.

2) Αποδεικνύεται ότι ισχύει το παρακάτω θεώρημα:

«Δεν υπάρχει αλγόριθμος παρόμοιος με τους παραπάνω (δηλαδή ο οποίος να απαριθμεί τους αριθμούς του συνόλου στο οποίο ανήκει ο κρυμμένος αριθμός) που να λύνει το αντίστοιχο του προβλήματος 1, εάν ο κρυμμένος αριθμός είναι πραγματικός»

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

Περικοπή στα ν δεκαδικά ψηφία

Πρόβλημα

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

Λύση

perikopi1

(Η απόδειξη ορθότητας παραλείπεται ως άσκηση)

Σχόλιο

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

 Άσκηση για εμβάθυνση

Χρησιμοποιώντας την λογική του αλγορίθμου της παραπάνω λύσης, γράψτε μια συνάρτηση που να στρογγυλοποιεί έναν δεδομένο πραγματικό αριθμό σε δεδομένο πλήθος δεκαδικών ψηφίων σύμφωνα με την μέθοδο «μισό-πάνω» (half -(round)up).

Ταληράκια

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο να επιλύει το ακόλουθο πρόβλημα:

Θεωρείστε δύο (ίσως φανταστικούς) τύπους κερμάτων αξίας α1 και α2 λεπτών, όπου α1 και α2 είναι οποιοιδήποτε θετικοί ακέραιοι με τον περιορισμό α1α2. Θεωρείστε ακόμη έναν μη-αρνητικό ακέραιο c. Υπάρχει τρόπος επιλέγοντας κάποια ποσότητα (ίσως 0) από το ένα κέρμα και κάποια ποσότητα (ίσως 0) από το άλλο, το άθροισμα των αξιών αυτών των κερμάτων να είναι ίσο με c;

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

Παράδειγμα:

Για αξίες κερμάτων 5 και 7 υπάρχει τρόπος να σχηματιστεί το ποσό 17, αλλά δεν υπάρχει τρόπος να σχηματιστεί το ποσό 23.

Λύση

psila

Η απόδειξη ορθότητας παραλείπεται ως άσκηση.

Ιστορικό σημείωμα

Το παραπάνω πρόβλημα στην γενική του μορφή, δηλαδή όχι μόνο για δύο τύπους κερμάτων, αλλά για οποιοδήποτε πεπερασμένο (θετικό ακέραιο) πλήθος κερμάτων (ανά δύο με άνισες αξίες) είναι γνωστό ως εκδοχή εφικτότητας του προβλήματος “κάνω ψιλά” (Change Making Problem – CMP). Ο καλύτερος αλγόριθμος ο οποίος έχει βρεθεί μέχρι τώρα για το τελευταίο αυτό πρόβλημα είναι πολύ αργός για την ανθρώπινη κλίμακα χρόνου για είναι χρήσιμος. Αν καταφέρνατε να βρείτε έναν «γρήγορο» αλγόριθμο γι’ αυτό το πρόβλημα, θα κερδίζατε το βραβείο του ενός εκατομμυρίου δολαρίων του Ινστιτούτου Μαθηματικών Clay, καθώς θα είχατε λύσει το μεγαλύτερο (ίσως) πρόβλημα πληροφορικής/μαθηματικών της εποχής μας και (ίσως) όλων των εποχών: το πρόβλημα “P versus NP”.

Άσκηση για εμβάθυνση

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

Το κόσκινο του Ερατοσθένη

Τελευταία ενημέρωση: 5/10/2016

Πρόβλημα

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

1. Αν n<2 τερμάτισε – δεν υπάρχει πρώτος αριθμός μικρότερος του 2.

2. Γράψε κατά αύξουσα σειρά διάταξης όλους τους φυσικούς αριθμούς οι οποίοι είναι μεγαλύτεροι ή ίσοι του 2 και μικρότεροι ή ίσοι του n.

3. Διάγραψε όλα τα πολλαπλάσια του 2 (πχ επισημαίνοντάς τα με μια διαγώνια μολυβιά) τα οποία είναι μεγαλύτερα από το 2.

4.Βρες τον πρώτο (όσο αφορά την διάταξη) αριθμό που είναι μεγαλύτερος του 2 και δεν έχει διαγραφτεί – αν δεν υπάρχει τέτοιος αριθμός πήγαινε στο βήμα 5. Πήγαινε στο βήμα 3 και εκτέλεσέ το, αυτό και το επόμενο (το 4, δηλαδή το τρέχον), θεωρώντας αντί για τον αριθμό 2, τον αριθμό που βρήκες στην αρχή αυτού του βήματος.

5. Οι πρώτοι αριθμοί οι οποίοι είναι μικρότεροι ή ίσοι από τον n είναι οι αριθμοί που δεν είναι διαγραμμένοι.

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο με εφαρμογή του παραπάνω αλγόριθμου εμφανίζει στην οθόνη όλους τους πρώτους αριθμούς οι οποίοι είναι μικρότεροι ή ίσοι από κάποιον φυσικό αριθμό n ≥ 2.

Λύση

eratosth

Η απόδειξη ορθότητας παραλείπεται ως άσκηση.

Ασκήσεις για εμβάθυνση

1) Γιατί θεωρείτε ότι ο παραπάνω αλγόριθμος ονομάζεται «κόσκινο»;

2) Τροποποιείστε το παραπάνω πρόγραμμα θεωρώντας ως δεδομένο ότι στο βήμα 3 του αλγόριθμου ο οποίος αναφέρεται στην διατύπωση του προβλήματος αρκεί να διαγραφτούν τα πολλαπλάσια του τρέχοντος αριθμού τα οποία είναι μεγαλύτερα ή ίσα από το τετράγωνο του τρέχοντος αριθμού, διότι τα υπόλοιπα έχουν ήδη διαγραφτεί πριν ο αλγόριθμος φτάσει σ’ αυτό το σημείο. Αν το τετράγωνο του τρέχοντος αριθμού είναι μεγαλύτερο από τον αριθμό n, ο αλγόριθμος πρέπει να μεταβαίνει στο βήμα 5.

Βίντεο

Πολλαπλάσια και ημίτονα

Τελευταία ενημέρωση 18/10/2016

Πρόβλημα

Χωρίς να χρησιμοποιήσετε τους τελεστές MOD, DIV και /, αλλά ούτε και την ενσωματωμένη συνάρτηση Α_Μ (Ακέραιο Μέρος), να συμπληρώσετε την εντολή στην παρακάτω συνάρτηση ώστε να επιστρέφει “Αληθές” αν η παράμετρος είναι άρτιος φυσικός αριθμός και “Ψευδές” αν είναι περιττός.

ΣΥΝΑΡΤΗΣΗ is_even(n): ΛΟΓΙΚΗ

ΜΕΤΑΒΛΗΤΕΣ

ΑΚΕΡΑΙΕΣ: n

ΑΡΧΗ

is_even <- …

ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Λύση

is_even <-  ΗΜ(n*90) = 0

Απόδειξη ορθότητας

Αν θεωρήσουμε τον τριγωνομετρικό κύκλο, είναι προφανές ότι τα άρτια πολλαπλάσια των 90 μοιρών (π/2 ακτίνια) έχουν ημίτονο 0, ενώ τα περιττά 1 ή -1.

Άσκηση για εμβάθυνση

Συμπληρώστε την εντολή στην παρακάτω συνάρτηση ώστε να επιστρέφει “Αληθές” αν η παράμετρος n διαιρείται (ακριβώς) με την m και “Ψευδές” αν δεν διαιρείται. Θεωρείστε ότι κατά την κλήση της συνάρτησης τα ορίσματα είναι φυσικοί αριθμοί.

ΣΥΝΑΡΤΗΣΗ div_n_by_m(n, m): ΛΟΓΙΚΗ

ΜΕΤΑΒΛΗΤΕΣ

ΑΚΕΡΑΙΕΣ: n, m

ΑΡΧΗ

div_n_by_m <-  ΗΜ(…) = …

ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Βίντεο

Τρίγωνο Pascal (-Khayyám-Yang Ηui)

Τελευταία ενημέρωση 23/9/2016

Το τρίγωνο Πασκάλ n γραμμών κατασκευάζεται (μεταξύ άλλων) σύμφωνα με τον ακόλουθο αλγόριθμο:

1) Θεώρησε έναν τετραγωνικό πίνακα φυσικών αριθμών n × n – η θέση (κ,λ) στον πίνακα είναι η θέση στην γραμμή κ και στην στήλη λ. Θεώρησε ότι η πρώτη γραμμή και η πρώτη στήλη είναι η 0 (όπως συνηθίζεται γενικότερα στα μαθηματικά).

2) Αρχικοποίησε τον πίνακα θέτοντας την τιμή 0 σε κάθε θέση.

3) Για την γραμμή 0 θέσε την τιμή της θέσης (0,0) ίση με 1.

4) Για κάθε επόμενη γραμμή:

Για κάθε θέση της γραμμής ξεκινώντας από την θέση 0 (και μεταβαίνοντας κάθε φορά στην αμέσως επόμενη):

α) Αν πρόκειται για την πρώτη θέση της γραμμής (στήλη 0) θέσε την τιμή της θέσης ίση με 1.

β) Αν πρόκειται για άλλη θέση και στην προηγούμενη γραμμή και στην τρέχουσα στήλη (δηλαδή στην θέση ακριβώς από πάνω από την τρέχουσα) είναι το 0, θέσε την τιμή της τρέχουσας θέσης σε 1, προχώρησε στην επόμενη γραμμή και πήγαινε στο α).

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

Πρόβλημα

Γράψτε μια διαδικασία με παράμετρο έναν τετραγωνικό πίνακα και έναν ακέραιο που εκφράζει τις διαστάσεις του πίνακα, η οποία κατασκευάζει το τρίγωνο Πασκάλ στον πίνακα της παραμέτρου. Θεωρείστε ότι κατά την κλήση της διαδικασίας η παράμετρος που εκφράζει τις διαστάσεις του πίνακα δεν ξεπερνάει το 500. Κάντε τον απαραίτητο μετασχηματισμό στον παραπάνω αλγόριθμο, λαμβάνοντας υπόψη ότι η πρώτη γραμμή και η πρώτη στήλη ενός πίνακα στην Γλώσσα του μαθήματος ΑΕΠΠ δεν είναι η 0, αλλά η 1.

Λύση

pascalt

Η απόδειξη ορθότητας παραλείπεται ως άσκηση

Ασκήσεις για εμβάθυνση

1)

Σημείωση:

Στην παρακάτω διατύπωση του προβλήματος για όλες τις αναφερόμενες θέσεις πίνακα (κ,λ) θεωρείται ως πρώτη γραμμή και πρώτη στήλη η 0. Κάντε την απαραίτητη μετατροπή για τις θέσεις του πίνακα στην Γλώσσα (όπου πρώτη γραμμή και πρώτη στήλη είναι πάντα η 1).

Θεωρείστε ένα “στιγμιότυπο” του προβλήματος Ζευγάρια με πλήθος μαθητών τάξης 20. Γράψτε ένα πρόγραμμα που εμφανίζει στην οθόνη την λύση του προβλήματος καλώντας την συνάρτηση pairs και αμέσως μετά κατασκευάζει ένα τρίγωνο Πασκάλ 21 γραμμών και εμφανίζει στην οθόνη την τιμή στην θέση (20, 2) του πίνακα του τριγώνου Πασκάλ. Εκτελέστε το πρόγραμμα στον διερμηνευτή. Τι παρατηρείτε; Σκεπτόμενοι επαγωγικά, ποια σημασία εικάζετε ότι έχει η τιμή του πίνακα, για παράδειγμα στις θέσεις (20,3), (19,4), (15,0);

2)

Γράψτε μία συνάρτηση με δύο ακέραιες παραμέτρους, από τις οποίες η πρώτη εκφράζει το πλήθος των γραμμών ενός τριγώνου Πασκάλ και η δεύτερη μια συγκεκριμένη γραμμή του τριγώνου, η οποία επιστρέφει το άθροισμα τιμών της διαγώνιας διάταξης θέσεων η οποία ορίζεται ως εξής:

η πρώτη θέση της διάταξης είναι στην πρώτη στήλη και στην γραμμή που υποδεικνύει η δεύτερη παράμετρος (θεωρείστε σ’ αυτήν την περίπτωση ότι η πρώτη γραμμή του τριγώνου είναι η 1 και κατά την κλήση της συνάρτησης το όρισμα που αντιστοιχεί στην δεύτερη παράμετρο είναι πάντα μεγαλύτερο ή ίσο του 1). Η δεύτερη θέση είναι η πάνω δεξιά της πρώτης, η τρίτη είναι η πάνω δεξιά της δεύτερης κοκ μέχρι την θέση όπου η τιμή της είναι 0 ή η επόμενή της υπερβαίνει τα όρια του πίνακα.

Γράψτε ένα πρόγραμμα το οποίο εμφανίζει τις τιμές που επιστρέφει η προηγούμενη συνάρτηση με όρισμα που αντιστοιχεί στην δεύτερη παράμετρο διαδοχικά 1, 2, 3, … ,20. Στην συνέχεια εμφανίζει τις τιμές που επιστρέφει η συνάρτηση F(ν) (ακολουθία Fibonacci) με όρισμα διαδοχικά 1, 2, 3, … ,20. Τι παρατηρείτε;

3)

Στην γραμμή 2 (θεωρώντας εδώ ως πρώτη γραμμή την 0) του τριγώνου Πασκάλ υπάρχουν τρεις τιμές, οι 1, 2 και 1. Θεωρώντας την γνωστή ταυτότητα (α+β)2 = α2+2αβ+β2 = 1α2+2αβ+1β2, σκεπτόμενοι επαγωγικά ποια σημασία εικάζετε ότι έχει η ακολουθία τιμών κάθε γραμμής στο τρίγωνο Πασκάλ;

Σχετικοί σύνδεσμοι

https://en.wikipedia.org/wiki/Inductive_reasoning

https://en.wikipedia.org/wiki/Deductive_reasoning

https://en.wikipedia.org/wiki/Pascal%27s_triangle

http://mathworld.wolfram.com/PascalsTriangle.html

https://en.wikipedia.org/wiki/Omar_Khayyam

https://en.wikipedia.org/wiki/Yang_Hui

https://en.wikipedia.org/wiki/Blaise_Pascal

Βίντεο

ν παραγοντικό (ν!)

Πρόβλημα

Το ν! παραγοντικό ορίζεται για κάθε φυσικό αριθμό ν ως εξής:

για ν=0: 0! = 1

για ν>0: ν! = 1⋅2⋅3⋅ …⋅ν

Γράψτε μια συνάρτηση με μία ακέραια παράμετρο η οποία επιστρέφει το παραγοντικό που υποδεικνύει η παράμετρος. Για παράδειγμα με όρισμα 0 η συνάρτηση πρέπει να επιστρέφει 0!= 1 ενώ με όρισμα 3 πρέπει να επιστρέφει 3! = 1⋅2⋅3 = 6.

Λύση

parag1

Απόδειξη ορθότητας

Για n=0 η συνάρτηση εκχωρεί στην μεταβλητή π την τιμή 1, ενώ η δομή επανάληψης δεν εκτελεί καμία επανάληψη, αφού η συνθήκη 1<=0 είναι ψευδής (βλ. Ακριβής). Επομένως, τελικά επιστρέφει 1, το οποίο είναι σωστό με βάση τον ορισμό του παραγοντικού.

Για ν>1 είναι εύκολο να δούμε ότι ν! = 1⋅2⋅3⋅ …⋅(ν-1) ⋅ν = (1⋅2⋅3⋅ …⋅(ν-1) )⋅ν = (ν-1)! ⋅ ν, το τελευταίο ισχύει και για ν=1 αφού 0!=1, δηλαδή το παραγοντικό ενός θετικού αριθμού είναι το παραγοντικό του προηγούμενου αριθμού επί τον αριθμό. Αυτή είναι και η λειτουργία της δομής επανάληψης στην παραπάνω συνάρτηση.

Άσκηση για εμβάθυνση

Το πρωτοντικό (primorial), το οποίο συμβολίζουμε με pn#, όπου n θετικός ακέραιος, ορίζεται ως εξής:

pn# = p1⋅ p2⋅ … ⋅pn, όπου, p1 , ο πρώτος “πρώτος” αριθμός (βλ. Πρώτοι αριθμοί), δηλαδή ο 2, p2 ο δεύτερος πρώτος αριθμός, δηλαδή ο 3, p3 ο τρίτος πρώτος αριθμός, δηλαδή ο 5 κοκ. Γράψτε μια συνάρτηση με μία ακέραια παράμετρο που επιστρέφει το πρωτοντικό που υποδεικνύει η παράμετρος.