Η ιδέα των πρώτων αριθμών (prime numbers) είναι απλή.
Πρώτο αριθμό λέμε εκείνον τον θετικό ακέραιο αριθμό που δεν αναλύεται σε θετικούς ακέραιους παράγοντες διαφορετικούς από τον ίδιο.
Για το 6 βρίσκουμε 6=2*3, άρα το 6 δεν είναι πρώτος αριθμός.
Για το 7 το μόνο που μπορούμε να γράψουμε είναι 7=1*7, άρα το 7 είναι πρώτος αριθμός.
Είναι ένας αριθμός πρώτος ή όχι;
Έναν αλγοριθμικό τρόπο να εντοπίζουμε τους πρώτους αριθμούς, γνωρίζουμε ότι επινόησε ο Κυρηναίος μαθηματικός Ερατοσθένης διακόσια χρόνια προ Χριστού, το Κόσκινο του Ερατοσθένη.
Αφού πρώτος αριθμός είναι εκείνος που διαιρείται μόνο με τον εαυτό του και την μονάδα, ελέγχουμε αν διαιρείται με άλλους, το 2, το 3, κλπ, κι αν διαιρείται τότε δεν είναι πρώτος.
(Είχα δημοσιεύσει ένα πρόγραμμα εντοπισμού εδώ).
Ποιος είναι ο μεγαλύτερος πρώτος αριθμός που μπορούμε να βρούμε;
Το πρόβλημα γίνεται όλο και πιο δύσκολο όταν οι αριθμοί γίνονται μεγαλύτεροι. Οι υπολογιστές μας βοηθούν τα τελευταία χρόνια και κάνουμε εκπληκτικές ανακαλύψεις. Μπορείτε να δείτε μια παρουσίαση (στα Αγγλικά) με αρκετό χιούμορ από τον Adam Spencer εδώ.
Στις 25/01/2013 ανακοινώθηκε από Πανεπιστήμιο στο Μισούρι ότι ο αριθμός (2 ^ 57,885,161) - 1
είναι πρώτος αριθμός και έχει 17,425,170 ψηφία. Ο μεγαλύτερος που γνωρίζουμε μέχρι τώρα.
Υπάρχει μεγαλύτερος; Θα ψάξουμε να τον βρούμε!
Ποια είναι η χρησιμότητα της αναζήτησης;
Αποδεικνύει ότι όταν έχουμε μια ιδέα, μπορούμε να φτιάξουμε και μια συσκευή που θα μας βοηθήσει να αποδείξουμε ότι η ιδέα μας είναι σωστή (ή όχι).
Η ανθρώπινη διανόηση με την υποστήριξη της τεχνολογίας προχωράει στην ανίχνευση
του πολύ μεγάλου και μακρινού (εξωπλανήτες κλπ)
και του πολύ μικρού και απρόσιτου (σωματίδιο Higgs κλπ).
Εμφάνιση αναρτήσεων με ετικέτα Μαθηματικά. Εμφάνιση όλων των αναρτήσεων
Εμφάνιση αναρτήσεων με ετικέτα Μαθηματικά. Εμφάνιση όλων των αναρτήσεων
Δευτέρα 9 Σεπτεμβρίου 2013
Τετάρτη 12 Οκτωβρίου 2011
Φράκταλς στην Αφρική
Ο μαθηματικός Ron Eglash παρατήρησε ότι στην Αφρική το χτίσιμο των χωριών, τα κεντήματα στα υφάσματα, ίσως και η κοινωνική ιεραρχία είναι όλα βασισμένα στα φράκταλς, πράγμα που δεν παρατηρείται σε χωριά Ινδιάνων ή ευρωπαίων.
Είδα το θέμα στο www.fridge.gr σε ανάρτηση του Τάσου Παπαλιά, και το βίντεο που μπορείτε να παρακολουθήσετε παρακάτω ανήκει στην διαφωτιστική σειρά TED, που παρουσιάζεται στο www.ted.com .
Δείτε το : http://www.ted.com/talks/ron_eglash_on_african_fractals.html
Υπάρχουν υπότιτλοι.
Είδα το θέμα στο www.fridge.gr σε ανάρτηση του Τάσου Παπαλιά, και το βίντεο που μπορείτε να παρακολουθήσετε παρακάτω ανήκει στην διαφωτιστική σειρά TED, που παρουσιάζεται στο www.ted.com .
Δείτε το : http://www.ted.com/talks/ron_eglash_on_african_fractals.html
Υπάρχουν υπότιτλοι.
Δευτέρα 29 Αυγούστου 2011
Μετά την ένατη διάσταση
Είδα στο ιστολόγιο του Κώστα Καββαθά δυό ενδιαφέροντα βιντεάκια που προσπαθούν να περιγράψουν πώς μπορούμε να αντιληφθούμε τις διαστάσεις του κόσμου μας. Μέχρι την τρίτη είναι σχετικά εύκολο, βάζουμε και τον χρόνο για τέταρτη διάσταση, αλλά πώς προχωρούμε μετά;
Η θεωρία των χορδών δεν έχει ιδιαίτερο πρόβλημα να φτιάξει και εξισώσεις με 17 διαστάσεις, το θέμα είναι όμως πώς τις αντιλαμβανόμαστε εμείς οι απλοί άνθρωποι. Μια πρόταση απλή, όχι ακριβώς όπως θα ήθελε η θεωρία των χορδών με την υπερσυμμετρία της, αλλά αρκετά κατανοητή, μπορείτε να παρακολουθήσετε (στα Αγγλικά) στα βιντεάκια 1 και 2, για διαστάσεις μέχρι και την δέκατη (που είναι σαν την μηδενική;).
Σημείο - Γραμμή - Διακλάδωση - Δίπλωμα - ...
Κι αν έχετε κέφι για ανάγνωση καλής λογοτεχνίας, διαβάστε για άπειρη πολυπλοκότητα στο "Βιβλίο από Άμμο" του Χόρχε Λουίς Μπόρχες, που δημοσίευσε προ καιρού ο Γάτος του Σρέντιγκερ στο σκακιστικό ιστολόγιο, εδώ, (και μου το θύμισε ο συγγραφέας Παναγιώτης Κονιδάρης, εδώ).
Η θεωρία των χορδών δεν έχει ιδιαίτερο πρόβλημα να φτιάξει και εξισώσεις με 17 διαστάσεις, το θέμα είναι όμως πώς τις αντιλαμβανόμαστε εμείς οι απλοί άνθρωποι. Μια πρόταση απλή, όχι ακριβώς όπως θα ήθελε η θεωρία των χορδών με την υπερσυμμετρία της, αλλά αρκετά κατανοητή, μπορείτε να παρακολουθήσετε (στα Αγγλικά) στα βιντεάκια 1 και 2, για διαστάσεις μέχρι και την δέκατη (που είναι σαν την μηδενική;).
Σημείο - Γραμμή - Διακλάδωση - Δίπλωμα - ...
Κι αν έχετε κέφι για ανάγνωση καλής λογοτεχνίας, διαβάστε για άπειρη πολυπλοκότητα στο "Βιβλίο από Άμμο" του Χόρχε Λουίς Μπόρχες, που δημοσίευσε προ καιρού ο Γάτος του Σρέντιγκερ στο σκακιστικό ιστολόγιο, εδώ, (και μου το θύμισε ο συγγραφέας Παναγιώτης Κονιδάρης, εδώ).
Παρασκευή 17 Απριλίου 2009
Αριθμοί Φιμπονάτσι
Ας θυμηθούμε πώς ονομάζει η γραμματική τις λέξεις {πρώτος, δεύτερος, τρίτος, ...}. Λέγονται τακτικά αριθμητικά. Δίνουν την τάξη (την θέση του σε μια σειρά) του ουσιαστικού.
Λοιπόν, σήμερα θα γράψουμε ένα απλό πρόγραμμα (σε ΓΛΩΣΣΑ) που θα υπολογίζει έναν αριθμό Φιμπονάτσι όταν του δίνουμε την τάξη του. Οι αριθμοί Φιμπονάτσι είναι μια σειρά από αριθμούς που δημιουργούνται ως εξής:
Ο πρώτος (τάξη=1) ορίζεται ίσος με 0, δηλαδή f(1)=0.
Ο δεύτερος (τάξη=2) ορίζεται ίσος με 1, δηλαδή f(2)=1.
Κάθε άλλος επόμενος (τάξη=k, κ>2) ισούται με το άθροισμα των δύο προηγουμένων του, f(k)=f(k-1)+f(k-2) .
Από τον τρόπο σχηματισμού των όρων της, η σειρά ονομάζεται αναδρομική.
Οι αρχικοί αριθμοί της σειράς είναι : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, κλπ.
Αν ψάξετε στο διαδίκτυο για Fibonacci, (το όνομα του Ιταλού μαθηματικού που τους περιέγραψε Λεονάρντο της Πίζας), θα εκπλαγείτε από τον πλούτο των ευρημάτων στην φύση, σχετικών με τους αριθμούς αυτούς.
Θα τους βρείτε στους στήμονες των λουλουδιών, στις έλικες των κουκουναριών, στις γεννήσεις των κουνελιών, (δείτε, από περιέργεια, αυτή την σελίδα εδώ).
Καθαρά μαθηματικές έννοιες επίσης υπάρχουν άφθονες, όπως ότι δύο διαδοχικοί αριθμοί Φιμπονάτσι έχουν λόγο που προσεγγίζει την χρυσή τομή (f(k-1)/f(k)=0.618 ή f(k+1)/f(k)=1.618), όσο μεγαλύτερη είναι η τάξη k.
Εδώ θέλουμε μόνο να γράψουμε το πρόγραμμα που θα διαβάζει το k (δεχόμαστε μόνο k>2) και θα γράφει το f(k).
Επειδή δεν γνωρίζουμε την τάξη k που θα μας δοθεί, και επειδή δεν χρειάζεται να αποθηκεύσουμε όλη την σειρά αλλά μπορούμε από δύο διαδοχικούς όρους να βρίσκουμε τον επόμενο, δεν πρέπει να χρησιμοποιήσουμε την δομή του Πίνακα για αποθήκευση (των ενδιάμεσων) αποτελεσμάτων. Αρκεί η χρήση τριών μεταβλητών για τους όρους. Θα βάλουμε στην μεταβλητή fa έναν όρο της σειράς, θα βάλουμε στην μεταβλητή fb τον επόμενο όρο, και στην fc θα βάλουμε το άθροισμα των δύο προηγουμένων.
Αρχικοποιούμε fa=0, fb=1.
Μας δίνουν την τάξη k του όρου που θα βρούμε. Ελέγχουμε να είναι k>2.
Ξεκινάμε μια επαναληπτική διεργασία.
Βρίσκουμε τον τρίτο όρο f(3), (ή όρο τρίτης τάξης) : fc=fa+fb=0+1=1, άρα f(3)=1.
Βάζουμε τώρα στην μεταβλητή fa αυτό που περιέχει η μεταβλητή fb, και μετά
βάζουμε στην μεταβλητή fb αυτό που περιέχει η μεταβλητή fc, (περιέχουν δηλαδή το fa=1, και το fb=1),
και είμαστε έτοιμοι να υπολογίσουμε τον τέταρτο όρο f(4), (ή όρο τέταρτης τάξης) : fc=fa+fb=1+1=2, άρα f(4)=2.
Συνεχίζοντας με παρόμοιο τρόπο βάζουμε στην fa το 1 (της fb), στην fb το 2 (της fc) για να υπολογίσουμε τον πέμπτο όρο f(5), (ή όρο πέμπτης τάξης) : fc=fa+fb=1+2=3, άρα f(5)=3.
Σταματούμε όταν έχουμε υπολογίσει τον όρο f(k), της k τάξης που μας δόθηκε αρχικά.
Για να εξασκηθείτε στο γράψιμο κώδικα (δηλαδή εντολών σε ΓΛΩΣΣΑ), μπορείτε να κατεβάσετε στον υπολογιστή σας δωρεάν τον Διερμηνευτή του Άλκη Γεωργόπουλου, ένα πολύ καλοφτιαγμένο περιβάλλον εκτέλεσης προγραμμάτων σε ΓΛΩΣΣΑ, που συνοδεύεται από συλλογή παραδειγμάτων.
Μπορείτε να κατεβάσετε Διερμηνευτή και παραδείγματα από εδώ .
Λοιπόν, σήμερα θα γράψουμε ένα απλό πρόγραμμα (σε ΓΛΩΣΣΑ) που θα υπολογίζει έναν αριθμό Φιμπονάτσι όταν του δίνουμε την τάξη του. Οι αριθμοί Φιμπονάτσι είναι μια σειρά από αριθμούς που δημιουργούνται ως εξής:
Ο πρώτος (τάξη=1) ορίζεται ίσος με 0, δηλαδή f(1)=0.
Ο δεύτερος (τάξη=2) ορίζεται ίσος με 1, δηλαδή f(2)=1.
Κάθε άλλος επόμενος (τάξη=k, κ>2) ισούται με το άθροισμα των δύο προηγουμένων του, f(k)=f(k-1)+f(k-2) .
Από τον τρόπο σχηματισμού των όρων της, η σειρά ονομάζεται αναδρομική.
Οι αρχικοί αριθμοί της σειράς είναι : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, κλπ.
Αν ψάξετε στο διαδίκτυο για Fibonacci, (το όνομα του Ιταλού μαθηματικού που τους περιέγραψε Λεονάρντο της Πίζας), θα εκπλαγείτε από τον πλούτο των ευρημάτων στην φύση, σχετικών με τους αριθμούς αυτούς.
Θα τους βρείτε στους στήμονες των λουλουδιών, στις έλικες των κουκουναριών, στις γεννήσεις των κουνελιών, (δείτε, από περιέργεια, αυτή την σελίδα εδώ).
Καθαρά μαθηματικές έννοιες επίσης υπάρχουν άφθονες, όπως ότι δύο διαδοχικοί αριθμοί Φιμπονάτσι έχουν λόγο που προσεγγίζει την χρυσή τομή (f(k-1)/f(k)=0.618 ή f(k+1)/f(k)=1.618), όσο μεγαλύτερη είναι η τάξη k.
Εδώ θέλουμε μόνο να γράψουμε το πρόγραμμα που θα διαβάζει το k (δεχόμαστε μόνο k>2) και θα γράφει το f(k).
Επειδή δεν γνωρίζουμε την τάξη k που θα μας δοθεί, και επειδή δεν χρειάζεται να αποθηκεύσουμε όλη την σειρά αλλά μπορούμε από δύο διαδοχικούς όρους να βρίσκουμε τον επόμενο, δεν πρέπει να χρησιμοποιήσουμε την δομή του Πίνακα για αποθήκευση (των ενδιάμεσων) αποτελεσμάτων. Αρκεί η χρήση τριών μεταβλητών για τους όρους. Θα βάλουμε στην μεταβλητή fa έναν όρο της σειράς, θα βάλουμε στην μεταβλητή fb τον επόμενο όρο, και στην fc θα βάλουμε το άθροισμα των δύο προηγουμένων.
Αρχικοποιούμε fa=0, fb=1.
Μας δίνουν την τάξη k του όρου που θα βρούμε. Ελέγχουμε να είναι k>2.
Ξεκινάμε μια επαναληπτική διεργασία.
Βρίσκουμε τον τρίτο όρο f(3), (ή όρο τρίτης τάξης) : fc=fa+fb=0+1=1, άρα f(3)=1.
Βάζουμε τώρα στην μεταβλητή fa αυτό που περιέχει η μεταβλητή fb, και μετά
βάζουμε στην μεταβλητή fb αυτό που περιέχει η μεταβλητή fc, (περιέχουν δηλαδή το fa=1, και το fb=1),
και είμαστε έτοιμοι να υπολογίσουμε τον τέταρτο όρο f(4), (ή όρο τέταρτης τάξης) : fc=fa+fb=1+1=2, άρα f(4)=2.
Συνεχίζοντας με παρόμοιο τρόπο βάζουμε στην fa το 1 (της fb), στην fb το 2 (της fc) για να υπολογίσουμε τον πέμπτο όρο f(5), (ή όρο πέμπτης τάξης) : fc=fa+fb=1+2=3, άρα f(5)=3.
Σταματούμε όταν έχουμε υπολογίσει τον όρο f(k), της k τάξης που μας δόθηκε αρχικά.
ΠΡΟΓΡΑΜΜΑ arfi
ΜΕΤΑΒΛΗΤΕΣ
__ΑΚΕΡΑΙΕΣ: fa, fb, fc, i, k
ΑΡΧΗ
fa <- 0
fb <- 1
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
__ΓΡΑΨΕ 'Δώσε ακέραιο μεγαλύτερο του 2'
__ΔΙΑΒΑΣΕ k
ΜΕΧΡΙΣ_ΟΤΟΥ k > 2
ΓΙΑ i ΑΠΟ 3 ΜΕΧΡΙ k
__fc <- fa + fb
__fa <- fb
__fb <- fc
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Αριθμός Φιμπονάτσι τάξης ', k, ' είναι ο ', fc
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
Για να εξασκηθείτε στο γράψιμο κώδικα (δηλαδή εντολών σε ΓΛΩΣΣΑ), μπορείτε να κατεβάσετε στον υπολογιστή σας δωρεάν τον Διερμηνευτή του Άλκη Γεωργόπουλου, ένα πολύ καλοφτιαγμένο περιβάλλον εκτέλεσης προγραμμάτων σε ΓΛΩΣΣΑ, που συνοδεύεται από συλλογή παραδειγμάτων.
Μπορείτε να κατεβάσετε Διερμηνευτή και παραδείγματα από εδώ .
Κυριακή 15 Φεβρουαρίου 2009
Τι είναι πρόβλημα;
Θέλησα να συνεχίσω με την έννοια [Πρόβλημα] και έριξα μια ματιά στο διαδίκτυο με ένα γνωστό ψαχτήρι (την Γούγλη). Μου έφερε 11,200,000 σελίδες που αναφέρουν την λέξη πρόβλημα.
Ούτε αν αφιερώσω την υπόλοιπη ζωή μου δεν πρόκειται να διαβάσω τόσες σελίδες.
Όμως, με ποιά σειρά τις δείχνει το ψαχτήρι; Πώς τις ταξινομεί και βγάζει κάποιες πρώτες και κάποιες επόμενες;
Απλά, με παρακολουθεί να βλέπω την μία μετά την άλλη τις προτάσεις του και σημειώνει ότι αυτές οι σελίδες που προσπέρασα δεν με ικανοποίησαν με το περιεχόμενό τους και δεν σταμάτησα το ψάξιμο. Άρα τους μειώνει την ιεραρχία.
Αν περισσότεροι χρήστες σταματούν το ψάξιμο σε κάποια σελίδα, τότε είναι μάλλον ικανοποιητική και το ψαχτήρι αυξάνει την ιεραρχία της.
Τελικά, αυτές που δείχνει πρώτες είναι κατά τεκμήριο ικανοποιητικές. Άρα οι χρήστες προτιμούν αυτό το ψαχτήρι, γιατί δεν τους ταλαιπωρεί με πολλές αναζητήσεις.
Ποιές σελίδες μου έφερε για να δω τι είναι το πρόβλημα;
Το Πρόβλημα του μήνα (από όμιλο φροντιστηρίων),
Πρόβλημα με ισπανικό πολεμικό αεροπλάνο (από εφημερίδα Καθημερινή),
Κυπριακό Πρόβλημα (από την Βικιπαίδεια),
Τρία Άλυτα Προβλήματα (Δήλιο πρόβλημα, τριχοτόμηση γωνίας, τετραγωνισμός του κύκλου από το telemath.gr),
Πρόβλημα με την Τουρκία,
Πρόβλημα με κατέβασμα βίντεο από το youtube.com,
Πρόβλημα με τον παίκτη Ντιαλό του Πανθρακικού,
Τεχνικό πρόβλημα χτύπησε την μηχανή της Google,
Πρόβλημα πρόσδεσης πλοίων,
Πρόβλημα τριχοφυΐας,
Γαλάζιο πρόβλημα στην Β' εκλογική περιφέρεια Αθηνών,
Το πρόβλημα της πρώτης αγάπης,
Αυξανόμενο το πρόβλημα των σκουπιδιών,
Σοβαρό το πρόβλημα στο Αφγανιστάν δήλωσε ο υπουργός Άμυνας Γκέιτς,
κλπ, κλπ.
Καταλαβαίνουμε ότι ο καθένας θεωρεί πρόβλημα αυτό που δεν μπορεί να λύσει ή που του αλλάζει τα σχέδια. Υπάρχουν προβλήματα υγείας, μαθηματικών, διοικητικά, συναισθηματικά, κλπ..
Με καλύτερη προσέγγιση στην έννοια [Πρόβλημα], βάζουμε κριτήρια (όπως στο μάθημα Πληροφορικής) και χωρίζουμε τα προβλήματα σε κατηγορίες:
Επιλύσιμα (ξέρουμε ότι λύνονται),
Ανοικτά (δεν ξέρουμε αν λύνονται),
Άλυτα (ξέρουμε ότι δεν λύνονται).
Δομημένα (ο τρόπος λύσης είναι γνωστός),
Ημιδομημένα (πρέπει να επιλέξουμε τρόπο λύσης),
Αδόμητα (πρέπει να επινοήσουμε τρόπο λύσης).
Απόφασης (προκύπτει μια απάντηση : Αληθής ή Ψευδής),
Υπολογισμού (προκύπτει ένα αποτέλεσμα αριθμητικό),
Βελτιστοποίησης (από πλήθος δυνατών λύσεων επιλέγεται μία, με χρήση κάποιων κριτηρίων).
Λένε, σαν αστείο, ότι δεν πρέπει να μας στενοχωρούν
(α) τα προβλήματα που λύνονται και
(β) τα προβλήματα που δεν λύνονται.
Υπάρχει μια εξαιρετική συμβουλή, που πρέπει να την εφαρμόζετε στην ζωή σας :
"Για να λύσεις ένα πρόβλημα, αρκεί να εντοπίσεις τους λύτες".
Ας βάλουμε τώρα ένα πρόβλημα, (Επιλύσιμο - Αδόμητο - Υπολογισμού), που για να το λύσετε πρέπει να ξεχάσετε όσα έχετε μάθει. Είναι για παιδάκια προσχολικής ηλικίας. Ξέρουν μόνο να αναγνωρίζουν σχήματα και να μετράνε από το 0 μέχρι το 9 :
2581 = ?
Αν σας έχει δυσκολέψει πολύ, μα πάρα πολύ, τότε ρίξτε μια ματιά εδώ. Θα βρείτε ότι έπρεπε να μετρήσετε (δύο) κλειστές καμπύλες.
Ούτε αν αφιερώσω την υπόλοιπη ζωή μου δεν πρόκειται να διαβάσω τόσες σελίδες.
Όμως, με ποιά σειρά τις δείχνει το ψαχτήρι; Πώς τις ταξινομεί και βγάζει κάποιες πρώτες και κάποιες επόμενες;
Απλά, με παρακολουθεί να βλέπω την μία μετά την άλλη τις προτάσεις του και σημειώνει ότι αυτές οι σελίδες που προσπέρασα δεν με ικανοποίησαν με το περιεχόμενό τους και δεν σταμάτησα το ψάξιμο. Άρα τους μειώνει την ιεραρχία.
Αν περισσότεροι χρήστες σταματούν το ψάξιμο σε κάποια σελίδα, τότε είναι μάλλον ικανοποιητική και το ψαχτήρι αυξάνει την ιεραρχία της.
Τελικά, αυτές που δείχνει πρώτες είναι κατά τεκμήριο ικανοποιητικές. Άρα οι χρήστες προτιμούν αυτό το ψαχτήρι, γιατί δεν τους ταλαιπωρεί με πολλές αναζητήσεις.
Ποιές σελίδες μου έφερε για να δω τι είναι το πρόβλημα;
Το Πρόβλημα του μήνα (από όμιλο φροντιστηρίων),
Πρόβλημα με ισπανικό πολεμικό αεροπλάνο (από εφημερίδα Καθημερινή),
Κυπριακό Πρόβλημα (από την Βικιπαίδεια),
Τρία Άλυτα Προβλήματα (Δήλιο πρόβλημα, τριχοτόμηση γωνίας, τετραγωνισμός του κύκλου από το telemath.gr),
Πρόβλημα με την Τουρκία,
Πρόβλημα με κατέβασμα βίντεο από το youtube.com,
Πρόβλημα με τον παίκτη Ντιαλό του Πανθρακικού,
Τεχνικό πρόβλημα χτύπησε την μηχανή της Google,
Πρόβλημα πρόσδεσης πλοίων,
Πρόβλημα τριχοφυΐας,
Γαλάζιο πρόβλημα στην Β' εκλογική περιφέρεια Αθηνών,
Το πρόβλημα της πρώτης αγάπης,
Αυξανόμενο το πρόβλημα των σκουπιδιών,
Σοβαρό το πρόβλημα στο Αφγανιστάν δήλωσε ο υπουργός Άμυνας Γκέιτς,
κλπ, κλπ.
Καταλαβαίνουμε ότι ο καθένας θεωρεί πρόβλημα αυτό που δεν μπορεί να λύσει ή που του αλλάζει τα σχέδια. Υπάρχουν προβλήματα υγείας, μαθηματικών, διοικητικά, συναισθηματικά, κλπ..
Με καλύτερη προσέγγιση στην έννοια [Πρόβλημα], βάζουμε κριτήρια (όπως στο μάθημα Πληροφορικής) και χωρίζουμε τα προβλήματα σε κατηγορίες:
Επιλύσιμα (ξέρουμε ότι λύνονται),
Ανοικτά (δεν ξέρουμε αν λύνονται),
Άλυτα (ξέρουμε ότι δεν λύνονται).
Δομημένα (ο τρόπος λύσης είναι γνωστός),
Ημιδομημένα (πρέπει να επιλέξουμε τρόπο λύσης),
Αδόμητα (πρέπει να επινοήσουμε τρόπο λύσης).
Απόφασης (προκύπτει μια απάντηση : Αληθής ή Ψευδής),
Υπολογισμού (προκύπτει ένα αποτέλεσμα αριθμητικό),
Βελτιστοποίησης (από πλήθος δυνατών λύσεων επιλέγεται μία, με χρήση κάποιων κριτηρίων).
Λένε, σαν αστείο, ότι δεν πρέπει να μας στενοχωρούν
(α) τα προβλήματα που λύνονται και
(β) τα προβλήματα που δεν λύνονται.
Υπάρχει μια εξαιρετική συμβουλή, που πρέπει να την εφαρμόζετε στην ζωή σας :
"Για να λύσεις ένα πρόβλημα, αρκεί να εντοπίσεις τους λύτες".
Ας βάλουμε τώρα ένα πρόβλημα, (Επιλύσιμο - Αδόμητο - Υπολογισμού), που για να το λύσετε πρέπει να ξεχάσετε όσα έχετε μάθει. Είναι για παιδάκια προσχολικής ηλικίας. Ξέρουν μόνο να αναγνωρίζουν σχήματα και να μετράνε από το 0 μέχρι το 9 :
8809 = 6
7111 = 0
2172 = 0
6666 = 4
1111 = 0
3213 = 0
7662 = 2
9312 = 1
0000 = 4
2222 = 0
3333 = 0
5555 = 0
8193 = 3
8096 = 5
7777 = 0
9999 = 4
7756 = 1
6855 = 3
9881 = 5
5531 = 02581 = ?
Αν σας έχει δυσκολέψει πολύ, μα πάρα πολύ, τότε ρίξτε μια ματιά εδώ. Θα βρείτε ότι έπρεπε να μετρήσετε (δύο) κλειστές καμπύλες.
Τρίτη 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 βήματα είναι τα ελάχιστα.
Περίπτωση όπου η βρύση έχει μόνο 12 lt νερού.
Σχόλιο : Εδώ τα γεμίσματα (12 lt) μείον τα αδειάσματα (7 lt) αφήνουν στα δοχεία 5 lt, (το Α έχει 5 lt, το Β είναι άδειο). Τα βήματα είναι περισσότερα, είναι 10.
Πρόβλημα 06 : Ακριβολογίες
Πήγατε στο περίπτερο και αγοράσατε με ένα δίευρο μια απλή εφημερίδα που κόστιζε 1 ευρώ και 30 λεπτά.
Ο περιπτεράς σάς έδωσε ρέστα δύο σύγχρονα μεταλλικά νομίσματα, κανονικές υποδιαιρέσεις του Ευρώ (όχι κάλπικα) συνολικής αξίας 70 λεπτών, αλλά το ένα δεν είναι πενηντάλεπτο. Υπάρχει εξήγηση;
Επίλυση : Κανονικά θα έπρεπε να μη γράψω την λύση. Οι περισσότεροι απαντούν ότι είναι αδύνατον.
Και όμως, υπάρχει εξήγηση : [Είναι το άλλο!]
Μπορεί να το είχατε βρει, ένα πενηντάλεπτο και ένα εικοσάλεπτο είναι η μοναδική λύση. Όμως, αν σας δυσκόλεψε, το πρόβλημα έλεγε [το ένα δεν είναι πενηντάλεπτο], δεν έλεγε [κανένα από τα δύο δεν είναι πενηντάλεπτο].
Τώρα, γιατί το μυαλό μας βάζει παραπανίσια στοιχεία στο πρόβλημα, είναι κάτι που αγνοώ.
Το ίδιο κάνουμε στην Γεωμετρία όταν μας δίνουν απλά [ένα τρίγωνο] και εμείς σχεδιάζουμε ένα [σχεδόν ισοσκελές] ή [σχεδόν ορθογώνιο] τρίγωνο.
Το ίδιο κάνουμε όταν μας δώσουν ένα κύκλο να τον κόψουμε [στα δύο με μια γραμμή] και εμείς τον κόβουμε [σε δύο ίσα κομμάτια με μια κατακόρυφη γραμμή]. (Το έχω δοκιμάσει σε πολλές τάξεις, και έχει πλάκα. Μόνο ο Οβελίξ έκοψε άνισα τα τρία κομμάτια στην τούρτα της Κλεοπάτρας!).
Πρέπει να έχουμε το μυαλό μας καθαρό.
Επειδή πιστεύουμε ότι όσα πιο πολλά προβλήματα λύνει κάποιος, τόσο πιο εύκολο είναι να λύσει κι άλλα, δίνουμε εδώ μερικά είδη προβλημάτων με την επίλυσή τους. Δοκιμάστε να τα λύσετε πριν διαβάσετε την λύση που ακολουθεί.
Πρόβλημα 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]) :
Ένα αρχαίο Fortran πρόγραμμα που έκανε στοιχειώδη μετατροπή έκφρασης σε Polish μορφή δίνεται παρακάτω :
Μετατρέψτε το στην γλώσσα που χρησιμοποιείτε συνήθως και δοκιμάστε το με εκφράσεις όπως οι παρακάτω (που δεν είναι όλες αλγεβρικά σωστές!) :
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+*
Καλή διασκέδαση!
Έχουμε ένα σύνολο 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+*
Καλή διασκέδαση!
Τετάρτη 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.
Ερώτηση 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 Συμπέρασμα
Ο υπολογιστής ξέρει να κάνει μόνο πρόσθεση. Έχει ειδικό κύκλωμα γιαυτό.
Με τα συμπληρώματα, που ορίσαμε, ο υπολογιστής μπορεί να κάνει αφαίρεση.
Με ολισθήσεις αριστερά και προσθέσεις, ο υπολογιστής κάνει πολλαπλασιασμό.
Υποψιάζεστε ότι η διαίρεση γίνεται με ολισθήσεις δεξιά και αφαιρέσεις;
Σωστό!
(Αλλά είναι θέμα για άλλη ανάρτηση).
Όλοι γνωρίζουν ότι οι ηλεκτρονικοί υπολογιστές χρησιμοποιούνται επειδή υπολογίζουν γρήγορα, επειδή εκτελούν γρήγορα ένα μεγάλο πλήθος από πράξεις.
Ποιές πράξεις γνωρίζουμε ότι μπορούμε να κάνουμε με δυό αριθμούς χ και ψ;
Απάντηση : Πρόσθεση χ+ψ, Αφαίρεση χ-ψ ή ψ-χ, Πολλαπλασιασμό χ*ψ, Διαίρεση χ/ψ ή ψ/χ, Ύψωση σε δύναμη χ^ψ ή ψ^χ, Εύρεση λογάριθμου του χ με βάση το ψ ή ...
Καλά, φτάνει! Έπρεπε να ρωτήσω ποιές απλές αριθμητικές πράξεις μπορούμε να κάνουμε με το ζεύγος αριθμών {χ, ψ} χωρίς να τους αλλάζουμε σειρά;
Απάντηση : Πρόσθεση χ+ψ, Αφαίρεση χ-ψ, Πολλαπλασιασμό χ*ψ, Διαίρεση χ/ψ (αν το ψ δεν είναι μηδενικό).
Ωραία, τέσσερις πράξεις.
Αν το ψάξουμε λίγο περισσότερο όμως, θα μάθουμε ότι τα κυκλώματα των υπολογιστών δεν γνωρίζουν πώς να εκτελέσουν αυτές τις πράξεις. Οι μόνες πράξεις που γίνονται από το κύκλωμα πράξεων του υπολογιστή είναι :
(α) Εύρεση συμπληρώματος ενός δυαδικού αριθμού. (Τα συμπληρώματα είναι μία μέθοδος για να μπορούμε να έχουμε αρνητικούς αριθμούς).
(β) Ολίσθηση ενός δυαδικού αριθμού κατά μία θέση αριστερά (ισοδυναμεί με πολλαπλασιασμό του αριθμού με την βάση 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
Παρακάτω θα γράφουμε τον αριθμό και δίπλα του, με έναν μικρό δείκτη κάτω δεξιά, θα δείχνουμε την βάση του αριθμητικού συστήματος που είναι γραμμένος. Αν δεν δείχνουμε την βάση, θα θεωρούμε ότι βάση είναι το δέκα (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
Το αρχαίο ελληνικό σύστημα αρίθμησης είχε κάποια σύμβολα (εκ των οποίων τα περισσότερα τα γνωρίζουμε σήμερα ως γράμματα. Τα ίδια σύμβολα χρησιμοποιήθηκαν επίσης για να γράφονται λέξεις και ως νότες για να γράφεται η μουσική). Οι μονάδες είχαν μια οξεία επάνω δεξιά. Οι χιλιάδες είχαν την οξεία κάτω αριστερά. Συγκεκριμένα:
Α' = 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.
Συγχαρητήρια σε όσους το λύσατε μόνοι σας!
Πληροφορική : από ορισμένα δεδομένα, με κατάλληλη επεξεργασία, παίρνουμε χρήσιμα αποτελέσματα που τα ονομάζουμε πληροφορίες . Τα αποτελέσματα που αναζητούμε καθορίζουν ποια από τα στοιχεία που γνωρίζουμε μπορούν να χρησιμοποιηθούν ως δεδομένα.
Η Πληροφορική είναι η επιστήμη που μας δίνει τις μεθόδους και τα εργαλεία για να συλλέγουμε /αποθηκεύουμε /αποστέλλουμε δεδομένα.
Η Πληροφορική καθορίζει τις μεθόδους και τα εργαλεία επεξεργασίας των δεδομένων. Οι μέθοδοι, που συνήθως είναι επαναληπτικές, μπορεί να δημιουργούν ενδιάμεσα δεδομένα.
Η Πληροφορική καθορίζει τις μεθόδους και τα εργαλεία αποθήκευσης /παρουσίασης /αποστολής των αποτελεσμάτων. Η μελέτη των αποτελεσμάτων μπορεί να εμπλουτίσει την Πληροφορική με νέες μεθόδους και νέα εργαλεία, χάρη στην επινοητικότητα και την ευστροφία των μελετητών.
Αν δεν υπάρχουν γνωστές μέθοδοι για να λύσουμε ένα πρόβλημα, φροντίζουμε να επινοήσουμε μια νέα διαδικασία που να το λύνει. Η διαδικασία μπορεί να είναι ανέφικτο να χρησιμοποιηθεί σε άλλα είδη προβλημάτων. Ο στόχος μας είναι πάντοτε η λύση των προβλημάτων, όχι μόνο η εφαρμογή γνωστών διαδικασιών σε κάποια δεδομένα.
Και τώρα,
Πρόβλημα 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.
Συγχαρητήρια σε όσους το λύσατε μόνοι σας!
Εγγραφή σε:
Αναρτήσεις (Atom)