Τρίτη 18 Νοεμβρίου 2008

Απλά προβλήματα (Γυμνασιακού επιπέδου)

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

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


Πρόβλημα 02 : Μοιράζουμε δυό γαϊδουριών άχυρο;

Έχουμε δέκα κιλά άχυρο να το μοιράσουμε σε δυό γαϊδούρια που το ένα πρέπει να φάει ένα κιλό περισσότερο από το άλλο. Πόσα κιλά άχυρο θα δώσουμε στο καθένα γαϊδούρι;

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

Σωστή επίλυση : Δίνουμε ένα κιλό άχυρο στο γαϊδούρι που πρέπει να φάει περισσότερο.
Χωρίζουμε τα υπόλοιπα 10-1=9 κιλά στην μέση και δίνουμε από 9/2=4.5 κιλά άχυρο στα δυό γαϊδούρια. Έτσι, το ένα γαϊδούρι θα φάει συνολικά 1+4.5=5.5 κιλά άχυρο και το άλλο 4.5 κιλά άχυρο.


Πρόβλημα 03 : Το θέλετε με σαλιγκάρι ή με ναυαγό;

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

Απρόσεκτη σκέψη : Ανεβαίνει 3-2=1 μέτρο ανά 24ωρο, άρα θα χρειαστεί 10/1=10 εικοσιτετράωρα.

Σωστή επίλυση : Αφαιρούμε τα 3 μέτρα της τελευταίας νύχτας από τα 10. Μένουν 10-3=7 μέτρα.
Κάθε 24ωρο ανεβαίνει 1 μέτρο. Θα χρειαστεί 7/1=7 εικοσιτετράωρα για να καλύψει την απόσταση των 7 μέτρων. Την επόμενη νύχτα θα ανέβει 3 μέτρα, όπως κάθε νύχτα, θα φτάσει (7+3=10) στην κορυφή και θα είναι εκεί το πρωί της όγδοης μέρας (και βέβαια δεν θα γλιστρήσει!).

Β) Ένας ναυαγός βρίσκεται είκοσι μίλια από την στεριά. Την ημέρα κολυμπάει έξι μίλια προς την σωτηρία σέρνοντας ένα κομμάτι ξύλο που επιπλέει με λιγοστά τρόφιμα και την νύχτα κοιμάται πάνω σε αυτό, αλλά τότε τα θαλάσσια ρεύματα τον τραβάνε τέσσερα μίλια προς τα ανοιχτά. Σε πόσες μέρες θα φτάσει στην ακτή;

Απρόσεκτη σκέψη : Κολυμπάει 6-4=2 μίλια το 24ωρο, άρα θα χρειαστεί 20/2=10 εικοσιτετράωρα.

Σωστή επίλυση : Αφαιρούμε τα 6 μίλια της τελευταίας μέρας από τα 20. Μένουν 20-6=14 μίλια.
Κάθε 24ωρο πλησιάζει 2 μίλια στην ακτή. Θα χρειαστεί 14/2=7 εικοσιτετράωρα για να καλύψει την απόσταση των 14 μιλίων. Την επόμενη μέρα θα κολυμπήσει έξι μίλια και θα φτάσει στην ακτή, άρα θα είναι εκεί το βράδι της 8ης ημέρας (και βέβαια δεν θα ξαναπέσει στην θάλασσα!).


Πρόβλημα 04 : Πότε γεμίζει η δεξαμενή;

Έχουμε δυό βρύσες σε μια δεξαμενή νερού. Η βρύση Α την γεμίζει σε έξι ώρες. Η βρύση Β έχει μεγαλύτερη παροχή νερού και την γεμίζει σε τέσσερις ώρες. (Όταν οι βρύσες ανοίγουν εννοείται ότι δίνουν αμέσως και συνεχώς την μέγιστη παροχή νερού).
Ανοίγουμε την βρύση Α στις 09:00 το πρωί.
Στις 10:30 αποφασίζουμε να ανοίξουμε και την βρύση Β.
Ποια ώρα πρέπει να κλείσουμε τις βρύσες, ώστε να είναι γεμάτη κατά 75% η δεξαμενή;
(Το διατύπωσα ώστε να φαίνεται δύσκολο, αλλά σημασία είπαμε ότι έχει η μεθοδική σκέψη!)

Επίλυση : Η βρύση Α γεμίζει την δεξαμενή σε 6 ώρες, άρα σε μία ώρα γεμίζει το 1/6 της δεξαμενής.
Η μία ώρα έχει 60 λεπτά και οι 6 ώρες έχουν 60*6=360 λεπτά.
Ξανά : Η βρύση Α γεμίζει την δεξαμενή σε 360 λεπτά, άρα σε ένα λεπτό γεμίζει το 1/360 της δεξαμενής.
(Με άλλο τρόπο : την ώρα (60 λεπτά) γεμίζει το 1/6, άρα το λεπτό γεμίζει το (1/6)/60=1/(6*60)=1/360 της δεξαμενής).

Τρέχοντας η βρύση Α επί (10:30)-(09:00)=90 λεπτά θα γεμίσει το 90*(1/360)=90/360=1/4 της δεξαμενής. (Επαλήθευση : Σε 6 ώρες ολόκληρη, άρα σε (6/4=1.5) μιάμιση ώρα το 1/4 της δεξαμενής).

Η βρύση Β γεμίζει την δεξαμενή σε 4 ώρες (=240 λεπτά). Σε μία ώρα (=60 λεπτά) γεμίζει το 1/4 της δεξαμενής. Σε ένα λεπτό γεμίζει το 1/240 της δεξαμενής. (Απλούστατο!)

Τρέχοντας μαζί οι δυό βρύσες κάθε λεπτό γεμίζουν το (1/360)+(1/240)=1/144 της δεξαμενής. Ή (αν άνοιγαν μαζί) θα την γέμιζαν σε 144 λεπτά (=2 ώρες και 24 λεπτά).

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

Άρα, θέλουμε να γεμίσουμε το (75/100)-(1/4)=(75/100)-(25/100)=50/100=1/2 της δεξαμενής με τις δύο βρύσες ανοικτές, δηλαδή γεμίζοντας το 1/144 της δεξαμενής ανά λεπτό. Πόσα λεπτά θα μείνουν ανοικτές μαζί οι βρύσες; Θα μείνουν (1/2)/(1/144)=144/2=72 λεπτά (=1 ώρα και 12 λεπτά).
Οι βρύσες πρέπει να κλείσουν ώρα (10:30)+(1:12)=11:42.

Επαλήθευση :
Η βρύση Α έτρεξε 90+72=162 λεπτά και γέμισε τα 162*(1/360)=162/360 της δεξαμενής.
Η βρύση Β έτρεξε 72 λεπτά και γέμισε τα 72*(1/240)=72/240 της δεξαμενής.
Αυτά πρέπει να έχουν άθροισμα 75/100 (=75%). Και έχουν!
(162/360)+(72/240)=(324/720)+(216/720)=(540/720)=3/4=75/100.

Παρόμοια είναι τα προβλήματα με άδειασμα της δεξαμενής.


Πρόβλημα 05 : Δύο ανόμοια δοχεία νερού

Υπάρχουν δύο δοχεία Α και Β, κενά και χωρίς ενδείξεις, χωρητικότητας 7 λίτρων και 3 λίτρων αντίστοιχα, και απεριόριστη ποσότητα νερού από μια βρύση για να τα γεμίζουμε. Θέλουμε να βρούμε την συντομότερη σωστή σειρά επιτρεπτών χειρισμών, αποκλειστικά και μόνο των δύο δοχείων, ώστε να έχουμε τελικά στο δοχείο Α ακριβώς 5 λίτρα νερού.
Οι επιτρεπτοί χειρισμοί είναι:
(α) πλήρες γέμισμα ενός δοχείου με νερό από την βρύση,
(β) μετάγγιση ποσότητας νερού από ένα δοχείο μέχρι να γεμίσει το άλλο,
(γ) μετάγγιση όλης της ποσότητας νερού του ενός δοχείου στο άλλο, μόνο αν χωράει εκεί,
(δ) πλήρες άδειασμα ενός δοχείου.

Περίπτωση πρώτη, όπου η βρύση έχει απεριόριστα λίτρα (lt) νερού.
Σχόλιο : Εδώ τα γεμίσματα (14 lt) μείον τα αδειάσματα (6 lt) αφήνουν στα δοχεία 8 lt, (το Α έχει 5 lt, το Β έχει 3 lt). Τα 8 βήματα είναι τα ελάχιστα.
ΠρινΠράξηΜετά
(Α=0, Β=0)Βήμα 1. Γεμίζουμε από την βρύση το άδειο Α με 7 lt(Α=7, Β=0)
(Α=7, Β=0)Βήμα 2. Μεταγγίζοντας 3 lt από το Α γεμίζουμε το Β(Α=4, Β=3)
(Α=4, Β=3)Βήμα 3. Αδειάζουμε το Β(Α=4, Β=0)
(Α=4, Β=0)Βήμα 4. Μεταγγίζοντας 3 lt από το Α γεμίζουμε το Β(Α=1, Β=3)
(Α=1, Β=3)Βήμα 5. Αδειάζουμε το Β(Α=1, Β=0)
(Α=1, Β=0)Βήμα 6. Μεταγγίζουμε το 1 λίτρο του Α στο άδειο Β(Α=0, Β=1)
(Α=0, Β=1)Βήμα 7. Γεμίζουμε από την βρύση το άδειο Α με 7 lt(Α=7, Β=1)
(Α=7, Β=1)Βήμα 8. Μεταγγίζοντας 2 lt από το Α γεμίζουμε το Β(Α=5, Β=3)

Περίπτωση όπου η βρύση έχει μόνο 12 lt νερού.
Σχόλιο : Εδώ τα γεμίσματα (12 lt) μείον τα αδειάσματα (7 lt) αφήνουν στα δοχεία 5 lt, (το Α έχει 5 lt, το Β είναι άδειο). Τα βήματα είναι περισσότερα, είναι 10.
ΠρινΠράξηΜετά
(Α=0, Β=0)Βήμα 1. Γεμίζουμε από την βρύση το άδειο Β με 3 lt(Α=0, Β=3)
(Α=0, Β=3)Βήμα 2. Μεταγγίζουμε τα 3 lt του Β μέσα στο Α(Α=3, Β=0)
(Α=3, Β=0)Βήμα 3. Γεμίζουμε από την βρύση το άδειο Β με 3 lt(Α=3, Β=3)
(Α=3, Β=3)Βήμα 4. Μεταγγίζουμε τα 3 lt του Β μέσα στο Α(Α=6, Β=0)
(Α=6, Β=0)Βήμα 5. Γεμίζουμε από την βρύση το άδειο Β με 3 lt(Α=6, Β=3)
(Α=6, Β=3)Βήμα 6. Μεταγγίζοντας 1 λίτρο από το Β γεμίζουμε το Α(Α=7, Β=2)
(Α=7, Β=2)Βήμα 7. Αδειάζουμε το Α(Α=0, Β=2)
(Α=0, Β=2)Βήμα 8. Μεταγγίζουμε τα 2 lt του Β στο άδειο Α(Α=2, Β=0)
(Α=2, Β=0)Βήμα 9. Γεμίζουμε από την βρύση το άδειο Β με 3 lt(Α=2, Β=3)
(Α=2, Β=3)Βήμα 10. Μεταγγίζουμε τα 3 lt του Β μέσα στο Α(Α=5, Β=0)



Πρόβλημα 06 : Ακριβολογίες
Πήγατε στο περίπτερο και αγοράσατε με ένα δίευρο μια απλή εφημερίδα που κόστιζε 1 ευρώ και 30 λεπτά.
Ο περιπτεράς σάς έδωσε ρέστα δύο σύγχρονα μεταλλικά νομίσματα, κανονικές υποδιαιρέσεις του Ευρώ (όχι κάλπικα) συνολικής αξίας 70 λεπτών, αλλά το ένα δεν είναι πενηντάλεπτο. Υπάρχει εξήγηση;

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

Και όμως, υπάρχει εξήγηση : [Είναι το άλλο!]
Μπορεί να το είχατε βρει, ένα πενηντάλεπτο και ένα εικοσάλεπτο είναι η μοναδική λύση. Όμως, αν σας δυσκόλεψε, το πρόβλημα έλεγε [το ένα δεν είναι πενηντάλεπτο], δεν έλεγε [κανένα από τα δύο δεν είναι πενηντάλεπτο].
Τώρα, γιατί το μυαλό μας βάζει παραπανίσια στοιχεία στο πρόβλημα, είναι κάτι που αγνοώ.

Το ίδιο κάνουμε στην Γεωμετρία όταν μας δίνουν απλά [ένα τρίγωνο] και εμείς σχεδιάζουμε ένα [σχεδόν ισοσκελές] ή [σχεδόν ορθογώνιο] τρίγωνο.

Το ίδιο κάνουμε όταν μας δώσουν ένα κύκλο να τον κόψουμε [στα δύο με μια γραμμή] και εμείς τον κόβουμε [σε δύο ίσα κομμάτια με μια κατακόρυφη γραμμή]. (Το έχω δοκιμάσει σε πολλές τάξεις, και έχει πλάκα. Μόνο ο Οβελίξ έκοψε άνισα τα τρία κομμάτια στην τούρτα της Κλεοπάτρας!).

Πρέπει να έχουμε το μυαλό μας καθαρό.

Τρίτη 11 Νοεμβρίου 2008

Πράξεις και τελεστές πράξεων και RPN

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

Έχουμε ένα σύνολο R με πραγματικούς αριθμούς.
Παίρνουμε πρώτα έναν αριθμό α από το σύνολο R.
Παίρνουμε ακόμη έναν αριθμό β από το σύνολο R.
Οι δυό αριθμοί κρατάνε τη σειρά τους, (πρώτα ο α και μετά ο β), κρατάνε την διάταξή τους, είναι ένα διατεταγμένο ζεύγος (α, β).
Η πράξη που θέλουμε να κάνουμε στο ζευγάρι αριθμών (α, β) συμβολίζεται με ένα τελεστή, ας πούμε Τ, και δίνει ένα αποτέλεσμα γ.
[Πιθανή γραφή : γ = ( α Τ β ) ]

Αν είναι αριθμητική πράξη ([πρόσθεση, αφαίρεση, πολλαπλασιασμός, διαίρεση, ύψωση σε δύναμη] όταν δηλαδή ο τελεστής είναι [+, -, *, /, ^]) τότε το γ είναι αριθμός που ανήκει επίσης στο σύνολο R. (Υπάρχουν κι άλλες πράξεις, όπως η ακέραια διαίρεση (με τελεστή \, όπου [7 \ 3] δίνει πηλίκο 2 και υπόλοιπο 1), που διαφέρει από την κανονική διαίρεση ([7 / 3] δίνει πηλίκο 2.3333..., ή μικτό 2 1/3). Για την ακέραια διαίρεση έχουμε ορίσει συναρτήσεις, όπως είναι η DIV και η MOD).

Αν είναι συγκριτική πράξη ([μεγαλύτερο από, μεγαλύτερο ή ίσο, ίσο, μικρότερο ή ίσο, μικρότερο, διάφορο από] όταν δηλαδή ο τελεστής είναι [>, >=, =, <=, <, <>]) τότε το γ είναι μία από τις δύο λογικές τιμές : Αληθής ή Ψευδής. (Υπάρχουν ακόμα οι λογικές πράξεις, (ο τελεστής είναι ΚΑΙ, Ή, ΌΧΙ), που γίνονται σε μεταβλητές (ή εκφράσεις) που έχουν λογικές τιμές, και πάλι το αποτέλεσμα είναι μία από τις δύο λογικές τιμές : Αληθής ή Ψευδής).

Υπάρχουν τρεις τρόποι να γράψουμε τον τελεστή της πράξης και το ζευγάρι (α, β).
(Τ α β), συμβολισμός prefix, ο τελεστής μπροστά. (Προτάθηκε το 1920 από τον Πολωνό μαθηματικό Jan Lukasiewicz).
(α Τ β), συμβολισμός infix, ο τελεστής ανάμεσα.
(α β Τ), συμβολισμός postfix, ο τελεστής ακολουθεί. (Προτάθηκε το 1960 από τους F. L. Bauer και E. W. Dijkstra).

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

Προηγείται η ύψωση σε δύναμη (α^β).
Δεύτερες πράξεις σε ιεραρχία είναι ο πολλαπλασιασμός (α*β) και η διαίρεση (α/β).
Ακολουθούν τρίτες σε ιεραρχία η πρόσθεση (α+β) και η αφαίρεση (α-β).
Αν σε μία έκφραση υπάρχουν παρενθέσεις, βρίσκεται πρώτα η τιμή της έκφρασης της πιο εσωτερικής παρένθεσης.
Αν σε μία έκφραση υπάρχουν πράξεις ίσης ιεραρχίας, εκτελούνται από αριστερά προς τα δεξιά.
Οι συγκριτικοί τελεστές έχουν μικρότερη ιεραρχία.
Οι λογικοί τελεστές έχουν μικρότερη από όλους, αλλά μεταξύ τους (αν θυμάμαι καλά!) προηγείται ο ΌΧΙ, μετά ο ΚΑΙ, μετά ο Ή. Το σωστό είναι να βάζουμε παρενθέσεις, για να μην υπάρχει αμφιβολία.

Ας δούμε ένα παράδειγμα εκτέλεσης πράξεων (Συμβολίζουμε τα ενδιάμεσα αποτελέσματα (results) με R1, R2, κλπ) :
(α - β * (γ + δ * ε)) - ζ / η
(α - β * (γ + R1)) - ζ / η
(α - β * (R2)) - ζ / η
(α - R3) - ζ / η
(R4) - ζ / η
R4 - R5
R6

Μια ενδιαφέρουσα παρατήρηση είναι ότι ο συμβολισμός του Πολωνού (Polish notation) Lukasiewicz και ο συμβολισμός με τον τελεστή να ακολουθεί (ανάστροφος συμβολισμός του Πολωνού, Reverse Polish Notation, RPN) δεν χρειάζονται παρενθέσεις!

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

Ας ξαναγράψουμε (δια "μαγικού τρόπου") την έκφραση του προηγούμενου παραδείγματος σε RPN μορφή :
α β γ δ ε * + * - ζ η / -
α β γ R1 + * - ζ η / -
α β R2 * - ζ η / -
α R3 - ζ η / -
R4 ζ η / -
R4 R5 -
R6

Όπως βλέπετε, γίνονται οι ίδιες πράξεις. Κάθε τελεστής εφαρμόζεται σε δύο παράγοντες/προσθετέους/κλπ αριστερά του.

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

Δείτε τον "μαγικό τρόπο" σε λειτουργία (αριστερά τα στοιχεία της έκφρασης, στη μέση [ο σωρός των τελεστών] και δεξιά [η έκφραση RPN]) :
στοιχεία της έκφρασηςο σωρός των τελεστώνη έκφραση RPNσχόλιο
( (

α ( α
- (- α
β (- αβ
* (-* αβ
( (-*( αβ
γ (-*( αβγ
+ (-*(+ αβγ
δ (-*(+ αβγδ
* (-*(+* αβγδ
ε (-*(+* αβγδε
) (-*(+*) αβγδε και αφού έκλεισε παρένθεση

(-* αβγδε*+
) (-*) αβγδε*+ και αφού έκλεισε παρένθεση


αβγδε*+*-
- - αβγδε*+*-
ζ - αβγδε*+*-ζ
/ -/ αβγδε*+*-ζ
η -/ αβγδε*+*-ζη
τέλος στοιχείων
αβγδε*+*-ζη/-

Ένα αρχαίο Fortran πρόγραμμα που έκανε στοιχειώδη μετατροπή έκφρασης σε Polish μορφή δίνεται παρακάτω :


______PROGRAM ALGPOL
C_________CASE STUDY 15 - (MAC CRACKEN ?)
C_________TRANSLATING ALGEBRAIC EXPRESSIONS TO POLISH NOTATION
______INTEGER BLANK,LPAREN,RPAREN,PLUS,MINUS,ASTRSK,SLASH,SOURCE(80),
_____1OPSTCK(80),POLISH(80),SHIER(80),OHIER(80)
______DATA BLANK,LPAREN,RPAREN,PLUS,MINUS,ASTRSK,SLASH/' ','(',')','+',
_____1'-','*','/'/
C_________
C_________INITIALIZE ARRAYS TO ZERO OR BLANK
_1001 DO 1002 L = 1, 80
______SHIER(L) = 0
______OHIER(L) = 0
______OPSTCK(L) = BLANK
______POLISH(L) = BLANK
_1002 CONTINUE
C_________READ A DATA CARD
______READ (10, 2001) SOURCE
C_________WRITE ALGEBRAIC STRING,(IN FORTRAN STYLE)
______WRITE(12, 2002) SOURCE
C_________L POINTS TO THE CURRENT CARD COLUMN
______L = 1
C_________ASSIGN HIERARCHY NUMBERS AND TEST FOR FIRST BLANK
_1003 IF(SOURCE(L) .EQ. BLANK) GO TO 1009
______IF(SOURCE(L) .EQ. LPAREN) GO TO 1004
______IF(SOURCE(L) .EQ. RPAREN) GO TO 1005
______IF(SOURCE(L) .EQ. PLUS .OR. SOURCE(L) .EQ. MINUS) GO TO 1006
______IF(SOURCE(L) .EQ. ASTRSK .OR. SOURCE(L) .EQ. SLASH) GO TO 1007
______GO TO 1008
_1004 SHIER(L) = 1
______GO TO 1008
_1005 SHIER(L) = 2
______GO TO 1008
_1006 SHIER(L) = 3
______GO TO 1008
_1007 SHIER(L) = 4
_1008 L = L + 1
______IF(L .GT. 80) GO TO 1009
______GO TO 1003
_1009 N = L - 1
C_________IF N IS NOW ZERO, CARD WAS BLANK, GO TO EXIT
______IF(N .EQ. 0) GO TO 1016
C_________INITIALIZE HIERARCHY NUMBERS
______OHIER(1) = - 1
C_________INITIALIZE POINTERS
______I = 1
______J = 2
______K = 1
C_________CHECK FOR OPERAND
_1010 IF(SHIER(I) .EQ. 0) GO TO 1012
C_________CHECK FOR RIGHT PARENTHESIS
______IF(SHIER(I) .EQ. 2) GO TO 1011
C_________OTHER OPERATOR IF HERE %% MOVE TO OPERATOR STACK
______OPSTCK(J) = SOURCE(I)
______OHIER(J) = SHIER(I)
______I = 1 + I
______J = J + 1
______GO TO 1010
C_________DELETE CORRESPONDING LEFT PARENTHESIS
_1011 I = 1 + I
______J = J - 1
______GO TO 1013
C_________MOVE OPERAND TO POLISH STRING
_1012 POLISH(K) = SOURCE(I)
______I = 1 + I
______K = K + 1
C_________CHECK HIERARCHY RANKINGS
_1013 IF (OHIER(J-1) .GE. SHIER(I)) GOTO 1014
C_________CHECK FOR END OF SOURCE STRING
______IF(I .GE. L) GO TO 1015
______GO TO 1010
C_________MOVE OPERATOR TO POLISH STRING
_1014 POLISH(K) = OPSTCK(J-1)
______K = K + 1
______J = J - 1
______GO TO 1013
C_________WRITE POLISH STRING
_1015 WRITE(12, 2003) POLISH
______GO TO 1001
C_________EXIT POINT
______STOP 1001
C_________I/O FORMATS
_2001 FORMAT(80A1)
_2002 FORMAT(* ALGEBRAIC NOTATION *,80A1)
_2003 FORMAT(* POLISH NOTATION *,80A1/)
______END


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

A+(B/C)/(D+(E+F)/(G*H-I/(J/K+L)))-M*N
A*(B+C)
(A+B)*C
A+B*C+D
(A+B)*(C+D)
A-B/C
(A-B)/C
A/B/C
(A/B)/C
A*B/C*D/E
A*B-C+D
A*B-(C+D)
A*(B-C)+D
A*(B-C+D)
A
(((A)))
((A)+((B)))
A+B+C+D
(A+B)+(C+D)
A+B/C+D/(E+F+G-H/I)*J
(((A+B)*C+D)*E+F)*G
A+B*(C+D*(E+F*(G+H)))
AB*CD+EF-*/
AB*3.C-/BB+*

Καλή διασκέδαση!

Παρασκευή 24 Οκτωβρίου 2008

Τι βιβλία έχω γράψει για πληροφορική

Κατά καιρούς έχω γράψει διάφορα κείμενα σχετικά με την πληροφορική.
Όταν άρχισα να γράφω, γύρω στο χίλια εννιακόσια εβδομήντα τόσο, δεν υπήρχε διαδίκτυο και ο προγραμματισμός γινόταν σε γλώσσα assembly και ενίοτε σε γλώσσα μηχανής. Κάποια από αυτά τα κείμενα ([Δίκτυα Υπολογιστών], [Δυαδικές Αριθμητικές Μονάδες Η/Υ], [Αξιοπιστία Λογισμικού Υπολογιστών]) είναι σήμερα αρχαία ιστορία, που ελπίζω να δημοσιεύσω κάποτε, έστω και μόνο για ιστορικούς λόγους.

Τα παρακάτω κείμενα (σήμερα σε μορφή .pdf) έχουν χρησιμοποιηθεί για παρουσιάσεις σεμιναρίων ή για διδασκαλία μαθημάτων. Βασική προϋπόθεση για τα διδακτικά εγχειρίδια είναι η απλή και κατανοητή μορφή του κειμένου, αλλά δεν είναι πάντοτε εφικτή. Πιστεύω όμως ότι αν διαβάσετε τα κείμενά μου θα ανακαλύψετε αρκετές χρήσιμες λεπτομέρειες, και όλοι γνωρίζουμε ότι στην πληροφορική είναι μεγάλη η σημασία της λεπτομέρειας!

Σημειώστε ότι η λίστα μπορεί να ανανεώνεται χωρίς προειδοποίηση!

01-02.
[Άλγεβρα Μπουλ] και
[Συναρτήσεις Αληθείας (Λογικές Συναρτήσεις)].
Σημειώσεις επαναλαμβανόμενου (18/01/1977, 16/01/1978, 15/01/1980) σεμινάριου που έδινα στο Πανεπιστήμιο Πατρών.

03.
[Δομημένος Προγραμματισμός, με αναλυτικά παραδείγματα σε Fortran 77], βιβλίο που περιέχει και ένα διαγώνισμα.
Το έγραψα σε πρώτη μορφή το 1984 για πρωτοετείς της Πολυτεχνικής Σχολής Πανεπιστημίου Πατρών, τμήμα [Ηλεκτρολόγων Μηχανικών και Τεχνολογίας Υπολογιστών].

04-05.
[Λειτουργικά Συστήματα], βιβλίο και
[Λειτουργικά Συστήματα, τεύχος ασκήσεων].
Το έγραψα το 2005 για εργαζόμενους σπουδαστές ειδικότητας [Τεχνικός Η/Υ, Επικοινωνιών και Δικτύων] ΙΕΚ Σιβιτανιδείου.

06-07.
[Δομημένος Προγραμματισμός, με αναλυτικά παραδείγματα σε ΓΛΩΣΣΑ], βιβλίο (γράφτηκε το 2006) και
[Δομημένος Προγραμματισμός, τεύχος ασκήσεων] (γράφτηκε το 2007 - μετά την τελευταία αναθεώρηση 22/05/2009 περιέχει 4 διαγωνίσματα).
Για μαθητές Λυκείου που δίνουν ΑΕΠΠ δηλ. [Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον].

Τετάρτη 22 Οκτωβρίου 2008

Συμπληρώματα σε άλλη βάση

Από μια ερώτηση που μου έθεσαν, θέλω να διευκρινίσω τα παρακάτω:

Ερώτηση 1:
Ενας υπολογιστής χρησιμοποιεί λέξη των 6 bits.
Για τους αρνητικούς χρησιμοποιεί [Συμπλήρωμα του 2].
Ασχολούμαστε με τον -2310.
Από το +2310 = 0 101112 παίρνουμε ότι
[Στ1, Συμπλήρωμα του 1] είναι το 1 010002 και
[Στ2, Συμπλήρωμα του 2] είναι το 1 010012 = -2310.
Πώς γράφεται το συμπλήρωμά του στο οκταδικό σύστημα;

Απάντηση 1:
Ο υπολογιστής κάνει πράξεις στο δυαδικό και μόνο εκεί χρειαζόμαστε τα Στ1 και Στ2.
Για να παραστήσουμε αρνητικούς αριθμούς στο οκταδικό
θα χρησιμοποιούσαμε [Στ7, Συμπλήρωμα του 7] και [Στ8, Συμπλήρωμα του 8].
Ο αριθμός +2310 γράφεται 0278 (πρόσημο θετικό, 2*8 + 7 = 2310 η τιμή).
Το Στ7 του 0 2 78 είναι 1 5 08 (το 0 έγινε 1, το 2 έγινε 7-2=5, το 7 έγινε 7-7=0).
Άρα το Στ8 είναι 1508 + 1 = 1518 (αυτός είναι ο -2310 στο οκταδικό με σύστημα Στ8).
Επαλήθευση : 0278 + 1518 δίνει 0008 = +08 (το κρατούμενο από την θέση του προσήμου χάνεται).

Ερώτηση 2:
Λέτε ότι -2310 = 1518.
Έδωσα στο calculator των windows τον δεκαδικό -23,
ζήτησα να το δείξει οκταδικά με μήκος word 6 και έδωσε 177751. Ποιό είναι το σωστό;

Απάντηση 2:
Ο υπολογιστής, για τον οποίο ορίσαμε λέξη 6 bits, κάνει πράξεις στο δυαδικό.
Στο οκταδικό μόνο εμφανίζει, άρα γίνονται κάποιοι συμβιβασμοί.

Αν η λέξη έχει μόνο 6 δυαδικά ψηφία, ο μέγιστος θετικός θα είναι 0 11 1112 = 0 378 = +3110,
(συμβιβαστικά, το οκταδικό 3 φτιάχτηκε από τα δύο ψηφία 11
με την υπόθεση ότι μπροστά τους είχαν κι άλλο ψηφίο=0, 0112 = 38).
Αυτό σημαίνει ότι η λέξη δεν χωράει τους αμέσως μεγαλύτερους οκταδικούς 0 408, 0 418, κλπ..

Ο -2310 στο δυαδικό είναι 1 010012. Αυτά είναι 6 bits.
Όταν η αριθμομηχανή δείχνει 1777518, χρησιμοποιεί 16 bits (1 πρόσημο + 5 οκταδικά * 3 bits/οκταδικό).

Για τα 6 bits λοιπόν, το -2310 = 101 0012 = 518
(όπου υπονοείται ότι το πρώτο bit από τα τρία bits του 5 είναι το πρόσημο).
(Η αριθμομηχανή με βαθμιαία μεγαλύτερη λέξη θα τον δείχνει 151, 351, 751, 1751, 3751, 7751, 17751 κλπ).

Σε δεκαεξαδική μορφή -2310 = 10 10012 = 2916.
(Η αριθμομηχανή με βαθμιαία μεγαλύτερη λέξη θα τον δείχνει 69, E9, 1E9, 3E9, 7E9, FE9, 1FE9 κλπ).

Εδώ μπορείτε να αρχίσετε να φτιάχνετε μια ιδιαίτερη κατηγορία προβλημάτων:
"Έδωσα στον υπολογιστή τον δεκαδικό -23 και όταν τον ζήτησα οκταδικό μου τον έδειξε 177751. Με πόσα bits κάνει πράξεις ο υπολογιστής;"
Βρήκαμε παραπάνω την απάντηση : 16.

Πέμπτη 16 Οκτωβρίου 2008

Βασικές πράξεις στον υπολογιστή

1.0 Εισαγωγή

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

Ποιές πράξεις γνωρίζουμε ότι μπορούμε να κάνουμε με δυό αριθμούς χ και ψ;
Απάντηση : Πρόσθεση χ+ψ, Αφαίρεση χ-ψ ή ψ-χ, Πολλαπλασιασμό χ*ψ, Διαίρεση χ/ψ ή ψ/χ, Ύψωση σε δύναμη χ^ψ ή ψ^χ, Εύρεση λογάριθμου του χ με βάση το ψ ή ...

Καλά, φτάνει! Έπρεπε να ρωτήσω ποιές απλές αριθμητικές πράξεις μπορούμε να κάνουμε με το ζεύγος αριθμών {χ, ψ} χωρίς να τους αλλάζουμε σειρά;
Απάντηση : Πρόσθεση χ+ψ, Αφαίρεση χ-ψ, Πολλαπλασιασμό χ*ψ, Διαίρεση χ/ψ (αν το ψ δεν είναι μηδενικό).

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

Από τις τέσσερις πράξεις, ο υπολογιστής έχει κύκλωμα μόνο για πρόσθεση!

2.0 Συμπληρώματα

Ας υποθέσουμε ότι η λέξη του υπολογιστή μας για αποθήκευση αριθμών έχει τρία μόνο δυαδικά ψηφία. Μπορούμε λοιπόν να αποθηκεύσουμε εκεί 8 διαφορετικές δυαδικές τριάδες ψηφίων :
[ 000 ], [ 001 ], [ 010 ], [ 011 ], [ 100 ], [ 101 ], [ 110 ], [ 111 ].

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

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

2.1 Σύστημα [Πρόσημο και μέγεθος]

Πρώτο ψηφίο είναι το πρόσημο, τα υπόλοιπα είναι το μέγεθος. Οι οκτώ τριάδες αντιστοιχούν στους εξής αριθμούς :
[000 +0], [001 +1], [010 +2], [011 +3], [100 -0], [101 -1], [110 -2], [111 -3].
Μεγαλύτερο μέγεθος είναι το +3, μικρότερο είναι το -3 και υπάρχουν δύο διαφορετικά μηδενικά +0 και -0. Οι πράξεις δεν είναι εύκολες.

2.2 Σύστημα [Συμπλήρωμα του 1]

Το συμπλήρωμα ενός δυαδικού ψηφίου ως προς 1 είναι η ποσότητα που απομένει για να γίνει 1. Άρα συμπλήρωμα του [0] είναι το [1] και συμπλήρωμα του [1] είναι το [0].
(Παίρνω το +1 που είναι το 001, το αλλάζω 110, και αυτό είναι το -1).

Με το αριστερό ψηφίο πρόσημο, οι οκτώ τριάδες αντιστοιχούν στους εξής αριθμούς :
[000 +0], [001 +1], [010 +2], [011 +3], [100 -3], [101 -2], [110 -1], [111 -0].
Μεγαλύτερο μέγεθος είναι το +3, μικρότερο είναι το -3 και υπάρχουν δύο διαφορετικά μηδενικά +0 και -0.

Ας προσθέσουμε το +2 με το -2 :
__010
__101 +
__---
__111 (Αυτό είναι το -0. Σωστό αποτέλεσμα).

Ας προσθέσουμε το +2 με το -1 :
__010
__110 +
__---
1 000 (Αν βγεί αριστερά κρατούμενο, προστίθεται στην θέση 1)
___1 +
__---
__001 (Αυτό είναι το +1. Σωστό αποτέλεσμα).

Υπάρχουν μερικές περιπτώσεις που είναι λάθος το αποτέλεσμα (επειδή δεν μπορεί να χωρέσει στην μικρή λέξη του υπολογιστή), αλλά υπάρχει εύκολος τρόπος να το ελέγξει ο υπολογιστής.
Αν προσθέσει θετικό με θετικό και βγεί αρνητικό αποτέλεσμα, είναι λάθος :
[ 001 +1 ] + [ 011 +3 ] (δεν χωράει το 4) δίνει [ 100 -3 ]
[ 010 +2 ] + [ 010 +2 ] (δεν χωράει το 4) δίνει [ 100 -3 ]
[ 010 +2 ] + [ 011 +3 ] (δεν χωράει το 5) δίνει [ 101 -2 ]
[ 011 +3 ] + [ 011 +3 ] (δεν χωράει το 6) δίνει [ 110 -1 ]

Αν προσθέσει αρνητικό με αρνητικό και βγεί θετικό αποτέλεσμα, είναι λάθος :
[ 100 -3 ] + [ 100 -3 ] (δεν χωράει το -6) δίνει [ 1 000 ] δίνει [ 001 +1 ]
[ 100 -3 ] + [ 101 -2 ] (δεν χωράει το -5) δίνει [ 1 001 ] δίνει [ 010 +2 ]
[ 100 -3 ] + [ 110 -1 ] (δεν χωράει το -4) δίνει [ 1 010 ] δίνει [ 011 +3 ]
[ 101 -2 ] + [ 101 -2 ] (δεν χωράει το -4) δίνει [ 1 010 ] δίνει [ 011 +3 ]

Ο υπολογιστής στο σύστημα [Συμπλήρωμα του 1] κάνει μόνο σωστές πράξεις (αφού έχει τρόπο να αποκλείει τις λαθεμένες) αλλά μας ενοχλούν τα δύο μηδενικά. Αν κάποια μεταβλητή έχει τιμή [ 111 -0 ] και κάποια άλλη έχει τιμή [ 000 +0 ], όταν θα τις συγκρίνει ο υπολογιστής θα τις βρει διαφορετικές!

2.3 Σύστημα Συμπλήρωμα του 2

Για να σχηματίσουμε το συμπλήρωμα ενός αριθμού εδώ, βρίσκουμε το συμπλήρωμά του ως προς 1 (αλλάζουμε τα [1] σε [0] και τα [0] σε [1]) και μετά του προσθέτουμε μια μονάδα.
(Παίρνω το +1 που είναι το 001, το αλλάζω 110, του προσθέτω 1 και γίνεται 111, και αυτό είναι το -1).
Με το αριστερό ψηφίο πρόσημο, οι οκτώ τριάδες αντιστοιχούν στους εξής αριθμούς :
[000 +0], [001 +1], [010 +2], [011 +3], [100 -4], [101 -3], [110 -2], [111 -1].
Μεγαλύτερο μέγεθος είναι το +3, μικρότερο είναι το -4 και υπάρχει μόνο το +0.

Ας προσθέσουμε το +2 με το -2 :
__010
__110 +
__---
1_000 (Το κρατούμενο αριστερά χάνεται).
__000 (Αυτό είναι το +0. Σωστό αποτέλεσμα).

Ας προσθέσουμε το +2 με το -1 :
__010
__111 +
__---
1_001 (Το κρατούμενο αριστερά χάνεται).
__001 (Αυτό είναι το +1. Σωστό αποτέλεσμα).

Υπάρχουν μερικές περιπτώσεις που είναι λάθος το αποτέλεσμα (επειδή δεν μπορεί να χωρέσει στην μικρή λέξη του υπολογιστή), αλλά υπάρχει εύκολος τρόπος να το ελέγξει ο υπολογιστής.
Αν προσθέσει θετικό με θετικό και βγεί αρνητικό αποτέλεσμα, είναι λάθος :
[ 001 +1 ] + [ 011 +3 ] (δεν χωράει το 4) δίνει [ 100 -4 ]
[ 010 +2 ] + [ 010 +2 ] (δεν χωράει το 4) δίνει [ 100 -4 ]
[ 010 +2 ] + [ 011 +3 ] (δεν χωράει το 5) δίνει [ 101 -3 ]
[ 011 +3 ] + [ 011 +3 ] (δεν χωράει το 6) δίνει [ 110 -2 ]

Αν προσθέσει αρνητικό με αρνητικό και βγεί θετικό αποτέλεσμα, είναι λάθος :
[ 100 -4 ] + [ 100 -4 ] (δεν χωράει το -8) δίνει [ 1 000 ] δίνει [ 000 +0 ]
[ 100 -4 ] + [ 101 -3 ] (δεν χωράει το -7) δίνει [ 1 001 ] δίνει [ 001 +1 ]
[ 100 -4 ] + [ 110 -2 ] (δεν χωράει το -6) δίνει [ 1 010 ] δίνει [ 010 +2 ]
[ 100 -4 ] + [ 111 -1 ] (δεν χωράει το -5) δίνει [ 1 011 ] δίνει [ 011 +3 ]
[ 101 -3 ] + [ 101 -3 ] (δεν χωράει το -6) δίνει [ 1 010 ] δίνει [ 010 +2 ]
[ 101 -3 ] + [ 110 -2 ] (δεν χωράει το -5) δίνει [ 1 011 ] δίνει [ 011 +3 ]

Ο υπολογιστής στο [Συμπλήρωμα του 2] κάνει μόνο σωστές πράξεις (αφού έχει τρόπο να αποκλείει τις λαθεμένες). Έχει μόνο ένα μηδενικό, το +0, οπότε δεν υπάρχουν ασάφειες. Επειδή παραλείπει τα κρατούμενα, η διαδικασία είναι ελαφρώς ταχύτερη, γιαυτό οι περισσότεροι σύγχρονοι υπολογιστές αναπαριστούν τους αρνητικούς αριθμούς με το Σύστημα [Συμπλήρωμα του 2].

3.0 Ολισθήσεις

Έχουμε τον αριθμό 4510 (σαρανταπέντε στο δεκαδικό σύστημα). Αν ολισθήσει μια θέση αριστερά, γίνεται 45010 (τετρακόσια πενήντα στο δεκαδικό σύστημα). Ο αριθμός πολλαπλασιάστηκε με το 10. Σωστότερο είναι να πούμε ότι πολλαπλασιάστηκε με την βάση 10 του αριθμητικού συστήματος.

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

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

Ο υπολογιστής κάνει πολλαπλασιασμό δύο αριθμών με προσθέσεις και ολισθήσεις, όπως ακριβώς κάνουμε κι εμείς! Επειδή δεν με πιστεύετε, ας δούμε ένα παράδειγμα :
Θέλω να βρώ το γινόμενο (12 x 34). Γράφω
_12
_34 x
_--- (Το [4 επί 12 ίσον σαρανταοκτώ] το γράφω από κάτω)
_48 (Τώρα λέω [3 επί 12 ίσον τριανταέξι] και ετοιμάζομαι να το γράψω)
36 (Γιατί το έγραψα λίγο αριστερά;)
Γιατί εκείνο το 3 στον πολλαπλασιαστή ήταν στην πραγματικότητα τριάντα, 30 = 3x10, άρα πολλαπλασιάζω μεν επί 3 αλλά το σπρώχνω και μία θέση αριστερά επειδή πολλαπλασιάζω και επί 10.
(Αδιαφορώ για το τελείωμα του παραδείγματος).

Ας δούμε έναν πολλαπλασιασμό με δυαδικούς, πέντε επί έξι.
___110 (=610)
___101 x (=510)
___---
___110 (μία φορά το έξι, ναι, 6)
__000 (δύο φορές το έξι, όχι, 0)
_110 (τέσσερις φορές το έξι, ναι, 24)
_------
_11110 (=3010)

4.0 Συμπέρασμα

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

Υποψιάζεστε ότι η διαίρεση γίνεται με ολισθήσεις δεξιά και αφαιρέσεις;
Σωστό!
(Αλλά είναι θέμα για άλλη ανάρτηση).

Δευτέρα 6 Οκτωβρίου 2008

Μετατροπές αριθμών

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

Κατά συνθήκη, χρησιμοποιούμε τα ίδια ψηφία με ίδια αξία και σε συστήματα με μεγαλύτερη βάση. Π.χ. Το τέσσερα του οκταδικού συστήματος είναι ίδια ποσότητα με το τέσσερα του δεκαδικού συστήματος κλπ. Συνοπτικά : 48 = 410 = 416

1.0 Μετατροπή από το δυαδικό σύστημα στο δεκαδικό σύστημα :

1.1 Έχουμε τον αριθμό 101102 και θέλουμε να βρούμε την τιμή του στο δεκαδικό σύστημα. Αν χρησιμοποιήσουμε τις δυνάμεις της βάσης (σύμβολο ^ για την ύψωση σε δύναμη), η τιμή αυτή θα είναι
101102 = 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0
= 1 * 16 + 0 * 8 + 1 * 4 + 1 * 2 + 0 * 1
= 16 + 4 + 2
= 22 .

Είναι εύκολο να μάθουμε τις αρχικές δυνάμεις του δύο : 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536.

1.2 Ας θυμηθούμε το σχήμα Horner για τον υπολογισμό της τιμής των πολυωνύμων χωρίς υψώσεις σε δύναμη, (αρχίζουμε από τον αριστερότερο συντελεστή, πολλαπλασιάζουμε επί την μεταβλητή και προσθέτουμε τον δίπλα-δεξιά συντελεστή, και επαναλαμβάνουμε αν υπάρχουν άλλα μονώνυμα).
a * x3 + b * x2 + c * x + d = ( ( a * x + b ) * x + c ) * x + d

Χρησιμοποιώντας το σχήμα Horner, (αρχίζουμε από το αριστερότερο ψηφίο, πολλαπλασιάζουμε επί την βάση και προσθέτουμε το δίπλα-δεξιά ψηφίο, και επαναλαμβάνουμε αν υπάρχουν άλλα ψηφία), η τιμή για το 101102 του προηγούμενου παραδείγματος βρίσκεται και έτσι :
101102 = (((1 * 2 + 0) * 2 + 1) * 2 + 1) * 2 + 0
= ((2 * 2 + 1) * 2 + 1) * 2 + 0
= (5 * 2 + 1) * 2 + 0
= 11 * 2 + 0
= 22 .

2.0 Μετατροπή από το δυαδικό σύστημα σε σύστημα με βάση [δύναμη του δύο] :

2.1 Έχουμε τους αριθμούς 101102, 101010.01012 και θέλουμε να βρούμε την τιμή τους στο οκταδικό σύστημα.

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

101102 = 010 1102
= 2 68
= 2 * 8 + 6
= 22

101010.01012 = 101 010 . 010 1002
= 5 2 . 2 48
= 5 * 8^1 + 2 * 8^0 + 2 * 8^(-1) + 4 * 8^(-2)
= 5 * 8 + 2 + 2 * (1/8) + 4 * (1/64)
= 40 + 2 + 0.25 + 0.0625
= 42.3125

2.2 Αν θέλουμε να μετατρέψουμε τους ίδιους δυαδικούς του προηγούμενου παραδείγματος σε δεκαεξαδικούς, επειδή το δεκαέξι είναι το [δύο στην τετάρτη δύναμη], θα χωρίσουμε τα ψηφία τους σε τετράδες.

101102 = 0001 01102
= 1 616
= 1 * 16^1 + 6 * 16^0
= 1 * 16 + 6
= 22

101010.01012 = 0010 1010 . 01012
= 2 A . 516
= 2 * 16^1 + 10 * 16^0 + 5 * 16^(-1)
= 2 * 16 + 10 + 5 * (1/16)
= 32 + 10 + 0.3125
= 42.3125

3.0 Μετατροπή από το δεκαδικό σύστημα σε άλλο:

3.1 Ας μετατρέψουμε τον 42.3125 σε οκταδικό. Οι δυνάμεις του οκτώ είναι (σε φθίνουσα σειρά):

8^2 = 64,
8^1 = 8,
8^0 = 1,
8^(-1) = 0.125,
8^(-2) = 0.015625,
8^(-3) = 0.001953125, ...

Εξηντατεσσάρια [64] ο αριθμός μας, 42.3125, δεν περιέχει.
Πόσα οκτάρια [8] περιέχει; Πέντε [5] και μένει υπόλοιπο 2.3125 .
Πόσους άσους [1] περιέχει αυτό; Δύο [2] και μένει υπόλοιπο 0.3125 . Εδώ περνάμε στο κλασματικό μέρος (θέση υποδιαστολής).
Πόσα [0.125] περιέχει αυτό; Δύο [2] και μένει υπόλοιπο 0.0625 .
Πόσα [0.015625] περιέχει αυτό; Τέσσερα [4] και μένει υπόλοιπο μηδέν.
Σταματάμε εδώ έχοντας βρει αποτέλεσμα 52.248.

3.2.1 Ας μετατρέψουμε τον 22 σε δυαδικό. Δυνάμεις του δύο σε φθίνουσα σειρά είναι
2^5 = 32,
2^4 = 16,
2^3 = 8,
2^2 = 4,
2^1 = 2,
2^0 = 1.

Τριανταδυάρια [32] ο αριθμός μας, 22, δεν περιέχει.
Πόσα δεκαεξάρια [16] περιέχει; Ένα [1] και μένει υπόλοιπο 6.
Πόσα οκτάρια [8] περιέχει αυτό; Μηδέν [0] και μένει υπόλοιπο 6.
Πόσα τεσσάρια [4] περιέχει αυτό; Ένα [1] και μένει υπόλοιπο 2.
Πόσα δυάρια [2] περιέχει αυτό; Ένα [1] και μένει υπόλοιπο μηδέν.
Πόσους άσους [1] περιέχει αυτό; Μηδέν [0] και τελειώσαμε με το ακέραιο μέρος.
Σταματάμε εδώ έχοντας βρει 101102.

3.2.2 Με διαφορετικό τρόπο τώρα θα μετατρέψουμε τον δεκαδικό 22 σε δυαδικό :

Το δύο διαιρεί τον αριθμό 22, με πηλίκο 11 και υπόλοιπο [0].
Το δύο διαιρεί το πηλίκο 11, με πηλίκο 5 και υπόλοιπο [1].
Το δύο διαιρεί το πηλίκο 5, με πηλίκο 2 και υπόλοιπο [1].
Το δύο διαιρεί το πηλίκο 2, με πηλίκο 1 και υπόλοιπο [0].
Το δύο διαιρεί το πηλίκο 1, με πηλίκο 0 και υπόλοιπο [1].
Σταματάμε όταν φθάσουμε σε μηδενικό πηλίκο και ο αριθμός που ζητούμε είναι τα υπόλοιπα με ανάποδη σειρά: 101102.

4.0 Μετατροπή από το δεκαεξαδικό σύστημα σε άλλο:

4.1 Για να βρούμε στο δεκαδικό σύστημα ποιός αριθμός ισούται με τον δεκαεξαδικό F1616, χρησιμοποιούμε το σχήμα Horner.

F 1 616 = ((F * 16 + 1) * 16 + 6
= ((15 * 16 + 1) * 16 + 6
= 241 * 16 + 6
= 3862.

4.2 Για να βρούμε στο οκταδικό σύστημα ποιός αριθμός ισούται με τον δεκαεξαδικό F1616, τον κάνουμε πρώτα δυαδικό αριθμό μετατρέποντας κάθε ψηφίο του σε ομάδα τεσσάρων δυαδικών, και μετατρέπουμε στην συνέχεια τον δυαδικό σε οκταδικό ομαδοποιώντας τα ψηφία ανά τρία.

F 1 616 = 1111 0001 01102
= 1111000101102
= 111 100 010 1102
= 7 4 2 68.

Πόρισμα : Όσο μικρότερη είναι η βάση του συστήματος αρίθμησης, τόσο περισσότερα ψηφία χρειάζονται για να εκφραστεί η ίδια αριθμητική ποσότητα. Π.χ. F1616 = 74268 = 1111000101102

Πέμπτη 25 Σεπτεμβρίου 2008

Συστήματα αρίθμησης

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

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

Α' = 1,
Β' = 2,
Γ' = 3,
Δ' = 4,
Ε' = 5,
F' = 6, (το σύμβολο ονομαζόταν δίγαμμα, δηλαδή δυο γάμμα το ένα πάνω στο άλλο ή F=2*Γ, (6=2*3). Σήμερα γράφουμε στην θέση του ένα στίγμα: ς' ή στ'),
Ζ' = 7,
Η' = 8,
Θ' = 9,

Ι' = 10, ΙΑ' = 11, ΙΒ' = 12, κλπ. ,
Κ' = 20, ΚΑ' = 21, ΚΒ' = 22, κλπ. ,
Λ' = 30,
Μ' = 40,
Ν' = 50,
Ξ' = 60,
Ο' = 70,
Π' = 80,
Q' = 90, (ειδικό σύμβολο που ονομαζόταν κόππα),

Ρ' = 100, ΡΑ' = 101, ΡΒ' = 102, ..., ΡΛΖ?'= 137, κλπ. ,
Σ' = 200, ΣΝ' = 250, κλπ. ,
Τ' = 300,
Υ' = 400,
Φ' = 500,
Χ' = 600,
Ψ' = 700,
Ω' = 800,
π' = 900, (ειδικό σύμβολο που ονομαζόταν σαμπί),

,Α = 1000 και ,ΑΩΚΑ' = 1821 και ,ΑΥΝΓ' = 1453 κλπ. ,
,Β = 2000, κλπ.

Το αρχαίο ρωμαϊκό σύστημα αρίθμησης ήταν αλλιώτικο. Είχε ορισμένα σύμβολα διαφορετικών αξιών:

I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000

και αν ένα σύμβολο ήταν δεξιά από ίσο ή μεγαλύτερό του γινόταν πρόσθεση

XI = 11, XII = 12, MDCCLΙΙ = 1752, MM = 2000, κλπ.

ενώ αν ένα σύμβολο ήταν αριστερά από μεγαλύτερό του, γινόταν αφαίρεση

IX = 9, XL = 40, XC = 90, MCM = 1900, κλπ.

με μια προσπάθεια να γράφεται ο αριθμός με τα λιγότερα σύμβολα, δηλαδή

1400 = MCD (όχι MCCCC).

Δεν ισχυρίζομαι ότι δεν ήξεραν να κάνουν πρόσθεση οι αρχαίοι, (είχαν μεθόδους με χρήση πινάκων), αλλά ο τρόπος που κάνουμε σήμερα την πρόσθεση δεν εξυπηρετείται ούτε από το ελληνικό ούτε από το ρωμαϊκό σύστημα αρίθμησης.

Τα σημερινά συστήματα αρίθμησης έχουν κάποιες έννοιες, που πρέπει να τις δούμε προσεκτικά:

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

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

Αν η βάση είναι το 8, το σύστημα λέγεται οκταδικό (octal) και χρησιμοποιεί οκτώ σύμβολα (0, 1, 2, 3, 4, 5, 6, 7), που λέγονται οκταδικά ψηφία (octal digits).

Αν η βάση είναι το 10, το σύστημα λέγεται δεκαδικό (decimal) και χρησιμοποιεί δέκα σύμβολα (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), που λέγονται δεκαδικά ψηφία (decimal digits).

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

Αν η βάση είναι το 16, το σύστημα λέγεται δεκαεξαδικό (hexadecimal) και χρησιμοποιεί δεκαέξι σύμβολα (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F), που λέγονται δεκαεξαδικά ψηφία (Hex digits).

Υπάρχουν συστήματα με άλλες βάσεις, όπως το εξηκονταδικό των Ασσυρίων. (Η ώρα έχει εξήντα πρώτα λεπτά. Το πρώτο λεπτό έχει εξήντα δεύτερα λεπτά. Όμοια χωρίζουμε τις μοίρες των γωνιών).

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

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

Παράδειγμα : Ο αριθμός [987.45], έχει ακέραιο μέρος το [987] και κλασματικό μέρος το [.45].

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

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

Ο αριθμός του προηγούμενου παραδείγματος [987.45], αν είναι γραμμένος στο δεκαδικό σύστημα αρίθμησης, (οπότε, δηλώνοντας την βάση του με μικρό δείκτη δεξιά του, τον γράφουμε [987.4510]), ισοδυναμεί με τις πράξεις [9 * 10^2 + 8 * 10^1 + 7 * 10^0 + 4 * 10^-1 + 5 * 10^-2] = [9 * 100 + 8 * 10 + 7 * 1 + 4 * 0.1 + 5 * 0.01] = [900 + 80 + 7 + 0.4 + 0.05].

Ας δούμε την μέθοδο με την οποία σχηματίζουμε τους (ακέραιους) αριθμούς :

Βήμα-Α : Βάζουμε το μηδέν [0] στην θέση όπου η βάση έχει εκθέτη μηδέν.
Βήμα-Β : Προσθέτουμε στον αριθμό μια ακέραια μονάδα, (οπότε χρησιμοποιούμε στην θέση με εκθέτη μηδέν το επόμενο ψηφίο του συστήματος αρίθμησης).
Βήμα-Γ : Αν δεν υπάρχει επόμενο ψηφίο, βάζουμε το μηδέν [0] στην θέση αυτή και προσθέτουμε [1] στην αριστερή διπλανή θέση.

Δυαδικό _Τετραδικό Οκταδικό Δεκαδικό Δεκαεξαδικό
______0 ______0 ______0 ______0 ______0
______1 ______1 ______1 ______1 ______1
_____10 ______2 ______2 ______2 ______2
_____11 ______3 ______3 ______3 ______3
____100 _____10 ______4 ______4 ______4
____101 _____11 ______5 ______5 ______5
____110 _____12 ______6 ______6 ______6
____111 _____13 ______7 ______7 ______7
___1000 _____20 _____10 ______8 ______8
___1001 _____21 _____11 ______9 ______9
___1010 _____22 _____12 _____10 ______A
___1011 _____23 _____13 _____11 ______B
___1100 _____30 _____14 _____12 ______C
___1101 _____31 _____15 _____13 ______D
___1110 _____32 _____16 _____14 ______E
___1111 _____33 _____17 _____15 ______F
__10000 ____100 _____20 _____16 _____10
__10001 ____101 _____21 _____17 _____11
__10010 ____102 _____22 _____18 _____12
__10011 ____103 _____23 _____19 _____13
__10100 ____110 _____24 _____20 _____14

Είναι αξιοπερίεργο να δείτε ότι σε όλα τα αριθμητικά συστήματα η βάση γράφεται [10], (1 * βάση^1 + 0 * βάση^0). (Ετοιμαζόμαστε να γράψουμε την βάση μόλις μας τελειώσουν τα ψηφία, άρα βάζουμε [0] στην θέση των μονάδων και [1] ακριβώς αριστερά του).
* Στο δυαδικό, [10] είναι το δύο.
* Στο τετραδικό, [10] είναι το τέσσερα.
* Στο οκταδικό, [10] είναι το οκτώ.
* Στο δεκαδικό, [10] είναι το δέκα.
* Στο δεκαεξαδικό, [10] είναι το δεκαέξι.

Φυσικά κάτι αντίστοιχο ισχύει για όλες τις δυνάμεις της βάσης. Το τετράγωνο της βάσης, που γράφεται πάντοτε [100], ισοδυναμεί
* για το δυαδικό σύστημα με 2^2 + 0 + 0 = 4,
* για το τετραδικό σύστημα με 4^2 + 0 + 0 = 16,
* για το οκταδικό σύστημα με 8^2 + 0 + 0 = 64,
* για το δεκαδικό σύστημα με 10^2 + 0 + 0 = 100,
* για το δεκαεξαδικό σύστημα με 16^2 + 0 + 0 = 256.

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

Άσκηση: Θα μπορούσε να ισχύει ποτέ ... 6 * 9 = 42 ;
Απάντηση: Ναι, αν οι αριθμοί είναι εκφρασμένοι στο δεκατριαδικό σύστημα! (Βρίσκουμε την άγνωστη βάση παρατηρώντας ότι 54=4*βάση+2 άρα βάση=13).

613 * 913 = 4213
(6 * 13^0) * (9 * 13^0) = (4 * 13^1 + 2 * 13^0)
(6 * 1) * (9 * 1) = (4 * 13 + 2 * 1)
610 * 910 = 5210 + 210
5410 = 5410

Κυριακή 31 Αυγούστου 2008

Το πρόβλημα με τον ταχυδρόμο

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

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

Η Πληροφορική είναι η επιστήμη που μας δίνει τις μεθόδους και τα εργαλεία για να συλλέγουμε /αποθηκεύουμε /αποστέλλουμε δεδομένα.

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

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

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

Και τώρα,

Πρόβλημα 01 : [Το πρόβλημα του ταχυδρόμου] :

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

Ο ταχυδρόμος θέλει να πιάσει γνωριμία με όλους τους κατοίκους και πλησιάζοντας ρωτάει την κυρία :

[Είσαστε η νέα νοικάρισα του σπιτιού; Ωραία γειτονιά!]

[Μάλιστα] απαντά η κυρία [και την διαλέξαμε επειδή μας αρέσει].

Η κυρία δεν φαίνεται ότι έχει όρεξη για κουβέντα.

Ο ταχυδρόμος είναι περίεργος και δεν τα παρατάει εύκολα. Ξαφνικά βλέπει για μια στιγμή στον διάδρομο μέσα στο σπίτι ένα κοριτσάκι που περνάει τρέχοντας από το ένα δωμάτιο σε ένα άλλο. Λέει λοιπόν

[Βλέπω έχετε μια κορούλα!]

[Δεν έχω μία. Έχω τρεις κόρες] απαντάει η κυρία.

[Να σας ζήσουν! Πόσων χρόνων είναι;]. Προφανώς ο ταχυδρόμος είναι περίεργος και η κυρία θέλει να τον ξεφορτωθεί με τρόπο, οπότε του λέει

[Οι ηλικίες τους, που είναι ακέραιοι αριθμοί, έχουν γινόμενο τριανταέξι. Το άθροισμα των ηλικιών είναι ίσο με τον αριθμό του απέναντι σπιτιού].

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

[Έχω κολλήσει. Μήπως μπορείτε να με βοηθήσετε λιγάκι;]

[Ευχαρίστως!] του λέει η κυρία. [Η μεγαλύτερη κόρη μου είναι ξανθιά!]

[Α! τότε εντάξει!] λέει χαρούμενος ο ταχυδρόμος, [οι ηλικίες είναι τάδε, τάδε και τάδε!].

Μπορείτε τώρα, με βάση τα στοιχεία του προβλήματος να προσδιορίσετε τις τρεις ηλικίες;

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



Ακολουθεί η λύση του προβλήματος του ταχυδρόμου

Ακέραιοι είναι αριθμοί, όπως -2, -1, 0, 1, 2…
Θα μπορούσε μια ηλικία να είναι αρνητική; [Όχι].
Θα μπορούσε κάποια ηλικία να είναι μηδέν; [Όχι, αφού το γινόμενό τους είναι 36].
Φτιάχνουμε όλες τις τριάδες ακεραίων που έχουν γινόμενο 36, και δίπλα βάζουμε το άθροισμά τους (ο αριθμός του απέναντι σπιτιού, που τον είδε ο ταχυδρόμος) :
1 + 1 + 36 = 38
1 + 2 + 18 = 21
1 + 3 + 12 = 16
1 + 4 + 9 = 14
1 + 6 + 6 = 13
2 + 2 + 9 = 13
2 + 3 + 6 = 11
3 + 3 + 4 = 10
Αν ο ταχυδρόμος έβλεπε στο απέναντι σπίτι αριθμό 16 θα έλεγε [ηλικίες 1, 3, 12].
Αν έβλεπε αριθμό 15, θα έλεγε [το πρόβλημα δεν λύνεται].
Τι είπε; Είπε ότι κόλλησε.
Γιατί κόλλησε; Επειδή ο απέναντι αριθμός ήταν 13, (ο μόνος που αντιστοιχεί ως άθροισμα δύο τριάδων).
Είπε ότι θέλει μικρή βοήθεια και η κυρία είπε [Η μεγαλύτερη…], δηλαδή ότι υπάρχει μία μεγαλύτερη. (Θυμηθείτε! Μας ενδιαφέρουν μόνο τα στοιχεία που έχουν σχέση με τις ηλικίες που ψάχνουμε!)
Άρα η σωστή απάντηση για τις ηλικίες είναι 2, 2 και 9.

Συγχαρητήρια σε όσους το λύσατε μόνοι σας!

Σάββατο 12 Ιουλίου 2008

Επιτρεπόμενα σχόλια στον χώρο μου

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

Υπάρχουν πολλά θέματα που δεν με ενδιαφέρουν
και δεν θα έχουν χώρο έκφρασης
ανάμεσα στις αναρτήσεις μου ή ανάμεσα στα σχόλιά τους.

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

Επιπλέον, σχόλια υβριστικά προς τον οποιοδήποτε δεν είναι αποδεκτά.

Ελπίζω να είναι και για σας ενδιαφέροντα όσα θέματα θα παραμείνουν δημοσιευμένα.