Το usaco.org είναι ο αμερικάνικος οργανισμός ολυμπιάδων πληροφορικής για μαθητές δευτεροβάθμιας εκπαίδευσης που από Δεκέμβριο μέχρι Μάρτιο οργανώνει μηνιαίους online διαγωνισμούς.
Απρ 25
Τελική (Γ) φάση 28ου Πανελλήνιου Διαγωνισμού Πληροφορικής (23 Απριλίου 2016 )
Θέματα τελικής φάσης:
PDP-28_C
Θέμα 1ο: Εκδρομή για σκι
Έχουμε έναν μονοδιάστατο πίνακα μέχρι 2.000.000 φυσικών αριθμών Α (με θετικές τιμές μεταξύ 1 και 1.000.000.000). Να βρεθεί η μέγιστη απόσταση μεταξύ των θέσεων i και j, ώστε i<j και A[i]<=A[j].
Μια δυνατή λύση:
skitrip5
Βασική ιδέα για την παραπάνω λύση:
αποθηκεύουμε σε εναν τριγωνικό πίνακα τιμές.
Ο πίνακας θα μοιάζει με το γνωστο μας ισορροπημένο δυαδικό δέντρο.
Στην βάση A[Line][i] (line==0, 0<=i<N), έχουμε τα Ν στοιχεία εισόδου.
Στην επόμενη γραμμή/επίπεδο A[1][i] (line==1, 0<=i<N/2 ή 0<=i<N/2+1) έχουμε Ν/2 στοιχεία (αν Ν άρτιος) ή Ν/2+1 (αν Ν περιττός)
Συνεχιζουμε έως ότου να έχουμε μόνο 1 στοιχειο (το οποίο συμβαίνει στην γραμμη last_line).
Κάθε στοιχείο i της γραμμης line, με line>0, είναι αποθηκευμένο στη θεση A[line][i] και έχει το ελάχιστο και μεγιστο στοιχείο απο τα A[line-1][i*2] και (αν υπάρχει) του A[line-1][i*2+1].
Μνήμη που απαιτείται για τον τριγωνικό πίνακα: 32Mbytes για 2.000.000 "στάσεις" τρένου. Το όριο της άσκησης είναι 128Mbyte.
Η ταχύτερη λύση (πολυπλοκότητας Ο(Ν)) ακολουθεί:
skitrip6_linear
Για κάθε αριθμό (ύψος) από την αριστερή πλευρά του πίνακα, αγνοούμε αυτά που έχουν μικρότερο αριθμό αριστερότερα από αυτά (διότι η Κατερίνα θα επιβιβαζόταν στην αριστερότερη στάση).
Από την δεξιά πλευρά, αγνοούμε όσους σταθμούς έχουν ύψος μικρότερο από κάποιον δεξιότερο τους (γιατί η Κατερίνα θα κατέβαινε στον δεξιότερο για να ξεκινήσει να κάνει σκι).
Τα στοιχεία που απομένουν είναι ταξινομημένα (από την αριστερή πλευρά με αύξουσα σειρά) και από την δεξιά με φθίνουσα.
Αφού βρούμε τις αγνοημένες στάσεις, κάνουμε μία προσπέλαση στον πίνακα για κάθε μη αγνοημένο στοιχείο A[i] και βρίσκουμε το πρώτο (ή το επόμενο) δεξιότερο A[right] που είναι μεγαλύτερο ή ίσο με το A[i]
Μαρ 10
Μάθημα 5: έλεγχος (αν)
Σε όλα τα προγράμματα χρειαζόμαστε να ελέγξουμε κάποιες καταστάσεις. Π.χ βρες τον μεγαλύτερο από δυο αριθμούς που θα πληκτρολογήσει ο χρήστης
Η εντολή if κάνει τον έλεγχο και ΑΝ το αποτέλεσμα του ελέγχου είναι ΑΛΗΘΕΙΑ τότε θα εκτελεστεί η εντολή που ακολουθεί την παρένθεση, αλλιώς θα αγνοηθεί η εντολή αυτή και θα συνεχίσουμε στην επόμενη.
Η εντολή if ακολουθείται από παρενθέσεις που μέσα τους υπάρχει η παράσταση για έλεγχο.
Στο παραπάνω παράδειγμα, η if της γραμμής 11, ελέγχει αν το περιεχόμενο της μεταβλητής a είναι μεγαλύτερο από το περιεχόμενο της b και ΑΝ αυτό είναι αλήθεια, τότε αποθηκεύει στην μεταβλητή c την τιμή του a.
Στη γραμμή 14 υπάρχει ένα if που ελέγχει αν η τιμή της μεταβλητής a είναι μικρότερη της τιμής της b και ΑΝ είναι αλήθεια, τότε θα αποθηκευτεί στην μεταβλητή c η τιμή της b.
Αποτέλεσμα των παραπάνω ελέγχων, είναι η μεταβλητή c να έχει πάρει την μεγαλύτερη τιμή από τα a και b.
Ακολουθεί η εκτύπωση της μεταβλητής c με το ανάλογο μήνυμα.
Ασκήσεις:
1) Βρες τον μικρότερο από δύο αριθμούς.
2) Βρες αν δυο αριθμοί είναι ίσοι.
3) Βρες αν δυο αριθμοί είναι άνισοι.
Σημειώσεις στους τελεστές συγκρίσεων
Περισσότερες πληροφορίες για τους τελεστές:
https://el.wikiversity.org/wiki/C/Μάθημα_3ο
Μαρ 07
Μάθημα 4: μια απλή αριθμομηχανή
Επεξηγήσεις:
Κάθε εντολή της C++ ακολουθείτε από το σύμβολο της αγγλικής άνω τελείας (δηλαδή το ελληνικό ερωτηματικό).
Οι εντολές που ξεκινούν με τη δίεση (#), δεν ακολουθούνται από ερωτηματικό (δεν είναι εντολές τις C++ αλλά οδηγίες για τον μεταγλωττιστή της).
Γραμμές νούμερο 1 και 3: ζητάμε από την C++ να χρησιμοποιήσουμε την βιβλιοθήκη std::iostream. Αυτές τις εντολές θα τις βάλουμε σε όλα τα μαθήματα μας στη C++.
Γραμμή νούμερο 5: η main είναι η συνάρτηση που από εδώ ξεκινούν οι εντολές του προγράμματος μας. Όλα τα προγράμματα σε C++ έχουν μια main.
Γραμμές νούμερο 6 και 19: έχουν τα σύμβολα { και }. Τα σύμβολα αυτά ακολουθούν την main. Τα σύμβολα αυτά ονομάζονται άγκιστρα και ανάμεσα σε αυτά τα δυο γράφουμε τις εντολές μας.
Γραμμή νούμερο 9: εκτύπωση ενός μηνύματος στην οθόνη.
Με cout συμβολίζεται η οθόνη και με τα δύο σύμβολα “μικρότερο” δείχνουμε ότι ότι εμφανίζεται στο δεξί μέρος τους θέλουμε να αποσταλεί στο cout. To endl είναι συντομογραφία του end line (αλλαγή γραμμής).
Όταν θέλουμε να τυπώσουμε ένα μήνυμα (κείμενο) στην οθόνη, το μήνυμα πρέπει να περιέχεται ανάμεσα σε διπλά εισαγωγικά.
Γραμμή νούμερο 10: διάβασμα δυο ακέραιων αριθμών από το πληκτρολόγιο (cin). Οι αριθμοί αυτοί θα αποθηκευτούν στις μεταβλητές a και b.
Γραμμή νούμερο 12: υπολογισμός του αθροίσματος των ακεραίων που είναι αποθηκευμένοι στις μεταβλητές a και b και αποθήκευση του αποτελέσματος στην μεταβλητή c.
Γραμμή 13: εκτύπωση του αθροίσματος
κλπ
Μαρ 02
Μάθημα 3: μεταβλητές και μνήμη
Πολλές φορές χρειαζόμαστε να αποθηκεύσουμε κάποια στοιχεία που δεν τα ξέρουμε όταν φτιάχνουμε το πρόγραμμα μας. Παράδειγμα όταν κάποιος έφτιαξε το πρόγραμμα Super Mario δεν ήξερε ποιο είναι το όνομα σας, ούτε τι σκορ θα κάνετε, ούτε ποιο θα είναι το High score την Τρίτη 8 Μαρτίου 2016 ή την Τετάρτη 16 Μαρτίου 2016.
Αυτά τα στοιχεία λοιπόν που δεν τα ξέρουμε όταν ετοιμάζουμε το πρόγραμμα μας, τα αποθηκεύουμε στη μνήμη του υπολογιστή σε θέσεις που τις ονομάζουμε μεταβλητές. Αν μάλιστα θέλουμε να τα θυμάται το πρόγραμμα μας και αφού θα έχει σβήσει ο υπολογιστής, πρέπει επιπρόσθετα να τα αποθηκεύσουμε και στο σκληρό δίσκο.
Οι μεταβλητές που όπως είπαμε, όταν σχεδιάζουμε το πρόγραμμα, δεν ξέρουμε τι τιμές έχουν, τις χρησιμοποιούμε με το όνομα που τους δίνουμε.
Π.χ. μερικά κατάλληλα ονόματα για μεταβλητή που θα κρατά το σκορ σε ένα παιχνίδι, είναι:
sk,
sc,
skor,
Skor,
Score,
score
ενώ το όνομα
aaa
παρόλο που είναι αποδεκτό όνομα για μια μεταβλητή, δεν είναι κατανοητό με την πρώτη ματιά που χρησιμεύει.
Ανάλογα με τι μορφή έχουν αυτά τα στοιχεία που θέλουμε να αποθηκεύσουμε, διαλέγουμε και τον ΤΥΠΟ της μεταβλητής.
Ο πιο συνηθισμένος τύπος είναι ο int (από τη λέξη integer που σημαίνει ακέραιος αριθμός) . Αυτός ο τύπος κρατάει χώρο στην μνήμη για αποθήκευση ακέραιου αριθμού (περίπου από -2 τρισεκατομμύρια, έως +2 τρισεκατομμύρια). Δεν μπορεί να αποθηκεύσει αριθμούς με υποδιαστολή.
Δηλαδή οι αριθμοί:
3
8
11
20000
27001
1000000010
μπορούν να αποθηκευτούν σε μια μεταβλητή τύπου int, ενώ οι αριθμοί:
3/7
3,14
45,001
δεν μπορούν να αποθηκευτούν σε μεταβλητή int.
παράδειγμα:
Ένας άλλος τύπος μεταβλητής είναι ο string, στον οποίο μπορούμε να αποθηκεύσουμε λέξεις ή φράσεις.
Μετά την εκτέλεση του παραπάνω προγράμματος, αφού μας ρωτήσει όνομα και ηλικία και απαντήσουμε, περιμένουμε να δούμε κάτι σαν αυτό:
Μαρ 02
Μάθημα 2: Επεξήγηση του πρώτου προγράμματος Hello World
Η γλώσσα C++ και κάθε γλώσσα προγραμματισμού, έχει μια αυστηρή σύνταξη. Δηλαδή απαιτεί από εμάς να χρησιμοποιούμε με ακρίβεια τα σύμβολα της.
Αυτό συμβαίνει διότι ο υπολογιστής είναι πιο “χαζός” από τον άνθρωπο και δεν έχει την δυνατότητα να διορθώνει τα λάθη του ανθρώπου.
Όταν όμως χρησιμοποιήσουμε τη σύνταξη και τα σύμβολα σωστά, ο υπολογιστής θα κάνει ακριβώς ότι του πούμε.
Κάθε εντολή στη γλώσσα C++ τελειώνει με το σύμβολο ; (ελληνικό ερωτηματικό).
Η C++ είναι μια γλώσσα με λίγες αγγλικές λέξεις για εντολές και στα αγγλικά η άνω τελεία είναι το σύμβολο ; (ελληνικό ερωτηματικό).
Αυτός είναι ο λόγος που χρησιμοποιούμε αυτό το σύμβολο και όχι για να κάνουμε ερώτηση.
Μαρ 01
Μάθημα 1: Προετοιμασία για το πρώτο μας πρόγραμμα σε C++.
Για να φτιάξουμε οποιοδήποτε πρόγραμμα που να δουλεύει σε υπολογιστή, θα πρέπει να καταφέρουμε να μιλήσουμε την ίδια “γλώσσα” με αυτόν. Οι υπολογιστές, φυσικά, δεν έχουν την δυνατότητα να αντιληφθούν την γλώσσα ομιλίας του ανθρώπου και να ανταποκριθούν σε αυτή, εκτός αν ο “υπολογιστής” βρίσκεται σε ταινία επιστημονικής φαντασίας.
Εφόσον λοιπόν ο υπολογιστής δεν μπορεί να μιλήσει τη δικιά μας γλώσσα, θα προσπαθήσουμε να μιλήσουμε εμείς τη δικιά του…
Να ένα δείγμα της γλώσσας ενός υπολογιστή:
Ναι! Οι υπολογιστές μιλάνε μόνο με τα ψηφία 0 και 1 και εμείς οι άνθρωποι τα ομαδοποιούμε σε 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F για οικονομία χώρου (και το ονομάζουμε δεκαεξαδικό σύστημα αρίθμησης).
Για να μην μας πιάνει ζαλάδα κάθε φορά που θέλουμε να φτιάξουμε ένα πρόγραμμα, δημιουργήσαμε τις γλώσσες υψηλού επιπέδου (όπως είναι η C++), που είναι πιο κοντά στον τρόπο σκέψης του ανθρώπου και χρησιμοποιούμε κάποιο πρόγραμμα για να την μετατρέψουμε στα 0 και 1 που θέλει ο υπολογιστής.
Τη διαδικασία μετατροπής την ονομάζουμε μεταγλώττιση (compilation).
Ένα δωρεάν πρόγραμμα για μεταγλώττιση, είναι το codeblocks.
Μπορείτε να το κατεβάσετε από εδώ: http://www.codeblocks.org/downloads/
επιλέγουμε Download the binary release
και κατεβάζουμε το: codeblocks-16.01-setup.exe αν έχουμε υπολογιστή με Windows ή την αντίστοιχη έκδοση αν έχουμε Linux ή Mac.
Προσοχή: όταν πατήσουμε το σύνδεσμο για να το κατεβάσει (το αρχείο θα κατέβει από την ιστοσελίδα sourceforge.com), απλά περιμένουμε. Το αρχείο θα κατέβει μόνο του μετά από λίγο και θα το βρούμε στις λήψεις του φυλλομετρητή μας.
Δεν χρειάζεται να πατήσουμε σε κανέναν σύνδεσμο της ιστοσελίδας (έχει αρκετούς διαφημιστικούς συνδέσμους).
Όταν κατέβει το πρόγραμμα και το εγκαταστήσουμε στον υπολογιστή (δεν χρειάζεται να αλλάξουμε καμία από τις τυπικές του ρυθμίσεις), μπορούμε να το ξεκινήσουμε:
Κάθε πρόγραμμα που κάνουμε πρέπει να ανήκει σε ένα project.
Πρέπει να δημιουργήσουμε ένα project, επιλέγοντας Create new project και από τις κατηγορίες που θα εμφανιστούν, επιλέγουμε Console Application.
Θα επιλέξουμε C++ και όταν φτάσουμε στην καρτέλα με το όνομα του project:
και πληκτρολογούμε το όνομα του project μας (στην εικόνα έχω βάλει prog1) και αν θέλουμε επιλέγουμε φάκελο αποθήκευσης (με τις 3 τελείες).
Ένα παράδειγμα προγράμματος με εντολές που τυπώνουν το “Hello World”, υπάρχει μέσα στο project:
Happy coding!
Μαρ 01
Εισαγωγή στον προγραμματισμό για μαθητές Πρωτοβάθμιας και Δευτεροβάθμιας Εκπαίδευσης
Με αφόρμιση την ολοκλήρωση της Α φάσης του 28ου Πανελλήνιου Διαγωνισμού Πληροφορικής , θα παραθέσω μια σειρά από άρθρα με οδηγίες για την εκμάθηση των απαραίτητων λειτουργιών της γλώσσας C/C++ με σκοπό την επίλυση των προβλημάτων των Πανελληνίων, Βαλκανικών και Διεθνών διαγωνισμών πληροφορικής.
Δεκ 25
Hello World!
Στο πρώτο άρθρο της ιστοσελίδας μου, που ασχολείται με τον προγραμματισμό με C, δεν θα μπορούσε να μην υπάρχει αναφορά στον Dennis M. Ritchie και το πασίγνωστο πια:
#include <stdio.h>
int main(){
printf("Hello World!\n");
return 0;
}
Η δουλειά του υπάρχει παντού. Μέσα στο κινητό μας, στο tablet, στον υπολογιστή μας, στο ρολόι μας, στις ιστοσελίδες που επισκεπτόμαστε, ακόμα και στο κλιματιστικό μας!
Μαζί με τον Brian Kernighan, έγραψαν το πασίγνωστο K&R.
R.I.P. Dennis Ritchie