Επίλυση προβλημάτων με υπολογιστή

Τι είναι πρόβλημα

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

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

Γι' αυτό το μεγαλύτερο μέρος της επίλυσης γίνεται πριν από τον κώδικα.

Δεδομένα, ζητούμενα, περιορισμοί

Το πρώτο που κάνεις με ένα πρόβλημα είναι να το διαβάσεις και να το χωρίσεις σε τρία κομμάτια:

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

Τα στάδια της επίλυσης

Η επίλυση ενός προβλήματος με υπολογιστή περνά από πέντε στάδια. Δεν είναι αυστηρά γραμμικά: ο έλεγχος συχνά σε στέλνει πίσω.

Ανάλυση: από πάνω προς τα κάτω

Ένα μεγάλο πρόβλημα σπάνια λύνεται μονομιάς. Η ανάλυση από πάνω προς τα κάτω (top-down) το σπάει σε υποπροβλήματα, και όποιο υποπρόβλημα είναι ακόμα μεγάλο το σπάει ξανά, μέχρι κάθε κομμάτι να είναι τόσο μικρό που η λύση του να φαίνεται αμέσως.

Για την εκδρομή:

Οργάνωση εκδρομής
├── Πόσα λεωφορεία;
│   ├── Πόσοι μαθητές δήλωσαν;
│   └── Πόσες θέσεις έχει κάθε λεωφορείο;
├── Πόσο κοστίζει συνολικά;
│   └── λεωφορεία × κόστος λεωφορείου
└── Πόσο πληρώνει κάθε μαθητής;
    └── συνολικό κόστος ÷ πλήθος μαθητών

Κάθε φύλλο του δέντρου είναι ένα πρόβλημα που λύνεται με μία ή δύο πράξεις. Αυτό είναι το σημάδι ότι η ανάλυση τελείωσε.

Η υπολογιστική σκέψη

Τα στάδια αυτά στηρίζονται σε τέσσερις τρόπους σκέψης, που μαζί λέγονται υπολογιστική σκέψη (computational thinking):

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

Ο έλεγχος: δεδομένα που ξέρεις την απάντηση

Ένα πρόγραμμα που «τρέχει» δεν είναι απαραίτητα σωστό. Το ελέγχεις δίνοντάς του δεδομένα για τα οποία ξέρεις ήδη τη σωστή απάντηση, και συγκρίνεις.

Τα πιο χρήσιμα δεδομένα ελέγχου είναι οι οριακές περιπτώσεις: οι τιμές στα άκρα, όπου τα προγράμματα σπάνε πιο συχνά. Για λεωφορεία των $50$ θέσεων, ενδιαφέρουν ιδιαίτερα οι $50$ και οι $51$ μαθητές, όχι οι $37$.

Να ένα πρόγραμμα σε Python που κάνει ακριβώς αυτό το λάθος. Δεν χρειάζεται να ξέρεις ακόμα Python: το // είναι η ακέραια διαίρεση, που πετάει το δεκαδικό μέρος.

students = 120
buses = students // 50
print(buses)

2

Δύο λεωφορεία των $50$ θέσεων χωράνε $100$ μαθητές, οπότε $20$ μένουν στην άκρη του δρόμου. Με $100$ μαθητές το πρόγραμμα θα έδινε σωστή απάντηση, και ένας έλεγχος μόνο με αυτή την τιμή δεν θα έβρισκε ποτέ το λάθος.

Λυμένα παραδείγματα

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση