Λοιπόν, για τις λύσεις - έκανε μια παρατήρηση ο 252 που θέλω να σταθώ ένα λεπτό.
Λύσεις της μίας γραμμής. Ναι, υπάρχουν.
Έχουν σημασία; Φυσικά.
Έχουν σημασία για το παρόν ερώτημα; Για μένα όχι. Να εξηγήσω γιατί.
Πριν από λίγα χρόνια, υπήρχε ένας διαγωνισμός ονλάην σε μία γλώσσα που δεν θέλω να αποκαλύψω (σε προηγ. ποστ) με σκοπό το να λυθούν προβλήματα με τον αποδοτικότερο κώδικα δυνατό. Όταν λέμε αποδοτικότερο, εννοούμε πως η λύση θα πρέπει να έχει το ελάχιστο parsing tree. Eξυπακούεται πως η μικρή απαίτηση σε μνήμη και ο μικρότερος χρόνος υπολογισμού λαμβάνονταν υπόψιν, κάτι που κάποιοι θα ισχυρίζονταν προκύπτει άμεσα από το προηγούμενο, μα φυσικά επιτρέπονταν και μικρές αλχημείες οι οποίες βοηθούν τη μεταγλώτισση να γίνει γρηγορότερη, ή να μη γίνει και καθόλου.
Ας το πούμε αυτό λίγο για να διασαφηνιστεί ότι δεν αναφέρω αυτό στα επόμενα.
Εδώ βλέπουμε ένα τέτοιο τρικ μεγατόννων. Δεξιά έχουμε τον κώδικα που έχει γράψει η γνωστή Μοντέλα-Προγραμματίστρια, Καρλι Κλοςς, για τον υπολογισμό του μεγίστου δύο αριθμών.
Αριστερά έχουμε έναν κάπως διάσημο κώδικα ο οποιος υπολογίζει την αντίστροφη τετραγωνική ρίζα (και προέρχεται από τη μηχανή του quake, αν κανείς εδώ ξόδεψε τα νειάτα του στα λαν πάρτυ).
Φαίνεται φυσικά πως το τρικ μοιάζει σχεδόν μαγικό για όσους δεν γνωρίζουν (μαζί και εγώ). Φαίνεται φυσικά το πως μια μοντέλα δεν χρειάζεται να μάθει προγραμματισμό, όχι για άλλο λόγο, αλλά για να μη λαμβάνει ο πιλότος ένδειξη 5 όταν οι είσοδοι στο πρόγραμμα είναι και οι δύο 7.
Aυτά λοιπόν τα τρικ υπάρχουν μα δεν μας αφορούν σε αυτό που θα πω τώρα (που δεν αφορά τη λύση, το λέω ξανά, μη βγεί κανείς να το πεί).
Ο διαγωνισμός λοιπόν για τον αποδοτικότερο κώδικα με βρήκε δεύτερο και καταενθουσιάστηκα, γιατί περίμενα πως η λύση του πρώτου θα είναι τόσο σουπερντούπερ μαγευτική που θα μας έστελνε όλους σπίτια μας να ασχοληθούμε με τα πρόβατα. Όταν λοιπόν μαθεύτηκε η λύση, έπεσα από τα σύννεφα, γιατί η λογική του κώδικα ήταν ακριβώς η δική μου, μα η διατύπωση γινόταν με χρήση regexp, άρα τεχνικά το parsing tree ελαττωνόταν.
Θα μου πείτε, γιατί δεν το έκανες εσύ έτσι ρε γκρινιάρη; Γιατί πολύ απλά με ενδιέφερε ο μηχανισμός της λύσης, και όχι τα κολπάκια που μπορούμε να κάνουμε ώστε να μην γράφουμε στο πληκτρολόγιο. Το ξαναλέω πως αυτό το κολπάκι δεν είναι το τρικ που μας δείχνει η καρλι κλοςς στον αριστερό κώδικα, το οποίο αποτελεί προϊόν συμφωνίας με τον Σατανά.
Με αυτή τη λογική, οι λύσεις της μίας γραμμής είναι δεκτές - μα όχι αυτοσκοπός. Αρκεί φυσικά να είναι γραμμένες χωρίς regexp.
Με βάση λοιπόν αυτό:
- Ο κώδικας του Σρικε είναι άμεσος, χρηστικός, και διαβάζεται ακόμα και αν δεν έχουμε επαφή με την VB6 (οπως εγώ).
Η λογική του είναι να εξετάζουμε από το 1 μέχρι το τελικό αριθμό και να ελέγχουμε τρείς συνθήκες.
Με είσοδο ν, κάθε συνθήκη έχει
πολυπλοκότητα Ο(ν) στη χειρότερη, και λόγω της επανάληψης, η συνολική πολυπλοκότητα είναι Ο(3ν^2).
Η λύση είναι δεκτή και εκτιμώ την απλότητά της.
- Ο κώδικας του Σπύρου252 είναι επίσης άμεσος, και διαβάζεται ακόμα και αν δεν έχουμε επαφή με την php (όπως εγώ).
Η λογική του είναι να αποθηκεύσουμε τους αριθμούς που μας ενδιαφέρουν σε τρείς λίστες και να αναζητούμε κάθε φορά.
Κάθε αναζήτηση θα υποθέσουμε είναι βέλτιστη, με την έννοια πως η πολυπλοκότητά της θα είναι Ο(logν). Συνεπώς, μαζί με την επανάληψη, θα έχουμε συνολική πολυπλοκότητα Ο(3νlogν).
Η λύση είναι δεκτή και εκτιμώ το ότι ο Σπ είχε το σθένος, αλλά και το θράσος, να μη χρησιμοποιήσει γλώσσα προγραμματισμού. Όπως και τον τρόπο με τον οποίο παρέκαμψε το πρόβλημα με τις συμβολοσειρές.
Ως προς την σύγκριση τώρα.
-Ο κώδικας του Σπ252 είναι γρηγορότερος, κάτι που πρέπει να λάβουμε υπόψιν λόγω την τεράστιων αριθμών.
-Ο κώδικας του Σρίκε δεν έχει απαιτήσεις μνήμης, κάτι που επίσης πρέπει να λάβουμε υπόψιν λόγω των τεραστίων αριθμών.
Συνεπώς, ποιός κώδικας είναι καλύτερος;
Αυτός που σέβεται τους περιορισμούς του μηχανήματος που εργαζόμαστε.
Τώρα για τις παρατηρήσεις:
- Ο Σταθ έκανε μια σημαντική παράτηση, οι αριθμοί είναι πρώτοι. Ο λόγος γι΄αυτό είναι πως, αν δεν ήταν πρώτοι, ο κώδικας που θα ετοιμάζουμε θα εξέταζε τις περιπτώσεις ανάλογα με την ανάλυσή τους σε πρώτους παράγοντες. Άρα το να μην είναι πρώτοι δεν προσφέρει κάτι ουσιώδες στο πρόβλημα.
- Ο νεημλεςς παρατήρησε ότι δεν χρειάζεται να κάνουμε τρείς συγκρίσεις. Και αυτή η παρατήρηση έχει αξία ώστε να ελαττωθεί ο χρόνος εκτέλεσης (Παρατήρηση Νεημλεςς)
Και τώρα μια δική μου λύση επειδή το έθεσα ο ίδιος το πρόβλημα. Η λογική της λύσης ειναι η εξής. Θα χρειαστούμε ούτως η άλλως επανάληψη για να διατρέξουμε τους αριθμούς από το 1 ως το 10^7. Εκτος αν κάνουμε τον κώδικα συνάρτηση Φ και την βάλουμε να καλεί τον ευατό της αναγωγικά, ξεκινώντας από το 10^7 (εισοδος) και κατεβούμε εώς το 1. Δηλαδή,
Φ(10^7)->Φ(Φ(10^7-1))->....->Φ(Φ(...Φ(1)...))
τυπώνοντας κάθε φορά το αποτέλεσμα του ελέγχου με βάση την Παρατήρηση Νεημλεςς.
Δεν κρατήθηκα φυσικά να μη βάλω και το χρόνο εκτέλεσης (*μονο για την εκτελεση της Φ). Αυτό είναι καγκουριά και θα φανεί σε ένα λεπτό γιατί.
Η λύση λοιπόν έχει μικρη πολυπλοκότητα και μηδαμινές απαιτήσεις μνήμης.
Παρ' όλα αυτά απορρίπτεται.
Ο λόγος είναι πως σε οποιοδήποτε μηχάνημα την χρησιμοποιήσετε, ο αριθμός των κλήσεων στον εαυτό της (recursion depth) υπερβαίνει το προκαθορισμένο όριο. Άρα σαν κώδικας είναι πρακτικά άχρηστος για τους μεγάλους αριθμούς που έχει ως απαιτήσεις το πρόβλημα.
Α να μην ξεχάσω, Χαο με το να ποστάρεις Νταλάρα με επιβεβαιώνεις σε αυτό που είπα.
Αυτά. Καλή κυριακή