Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α15.16 · Κατοπτρικά Πρώτα Τετράγωνα

Εργασία 1 (2023-24), Άσκηση 2 · Δυσκολία ★★★ · programming · Κεφάλαια: 15, 3, 2

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

Ορισμός 1. Ένας φυσικός αριθμός λέγεται τέλειο τετράγωνο (perfect square), όταν μπορεί να γραφεί σαν το τετράγωνο ενός άλλου φυσικού αριθμού. Για παράδειγμα τα 4 (= 2²), 16 (= 4²), 625 (= 25²) είναι όλα τέλεια τετράγωνα. Αντίθετα οι αριθμοί 7, 8, 624 και ένα σωρό άλλοι δεν είναι.

Ορισμός 2. Ένας φυσικός αριθμός μεγαλύτερος του 1 ονομάζεται πρώτος (prime) όταν έχει σαν μόνους διαιρέτες (το υπόλοιπο της διαίρεσης είναι 0) το 1 και τον εαυτό του. Για παράδειγμα, το 17 είναι πρώτος αριθμός, ενώ το 42 δεν είναι, αφού έχει σαν διαιρέτες το 2, το 3 και το 7, εκτός από τους 1 και 42. Μπορείτε να επιβεβαιώσετε ότι οι πρώτοι αριθμοί που είναι μικρότεροι από το 100 είναι οι εξής:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Ορισμός 3. Ένας φυσικός αριθμός λέγεται παλινδρομικός (palindromic) όταν διαβάζεται το ίδιο είτε ευθέως (από αριστερά προς τα δεξιά) είτε αντιστρόφως. Κάποια παραδείγματα παλινδρομικών αριθμών είναι τα ακόλουθα: 1, 9, 151, 484, 12321, 98766789.

Ορισμός 4. Ένα ζευγάρι αριθμών λέγεται κατοπτρικό (mirror) εάν τα ψηφία του πρώτου διαβάζοντάς τα από αριστερά προς τα δεξιά ταυτίζονται με τα ψηφία του δεύτερου όταν τα διαβάζουμε από τα δεξιά προς τα αριστερά και αντίστροφα. Για παράδειγμα, τα ακόλουθα ζεύγη αριθμών είναι κατοπτρικά: 1234 και 4321, 18437 και 73481, 837465 και 564738. Σε ένα κατοπτρικό ζεύγος αριθμών, λέμε ότι ο ένας είναι κάτοπτρο του άλλου.

Ορισμός 5. Ένας φυσικός αριθμός είναι ένα κατοπτρικό πρώτο τετράγωνο όταν:

1. Είναι τέλειο τετράγωνο ενός πρώτου αριθμού.
2. Το κάτοπτρό του είναι επίσης τέλειο τετράγωνο ενός πρώτου αριθμού.
3. Δεν είναι παλινδρομικός.

Για παράδειγμα, ο αριθμός 12769 είναι ένα κατοπτρικό πρώτο τετράγωνο, καθώς: (α) είναι το τετράγωνο ενός πρώτου αριθμού (113² = 12769), (β) το κάτοπτρό του 96721 είναι επίσης το τετράγωνο ενός πρώτου αριθμού (311² = 96721) και (γ) δεν είναι παλινδρομικός.

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

Τεχνικές Προδιαγραφές

• Repository Name: progintro/hw1-<YourUsername>
• C Filepath: mirror/src/mirror.c
• Το πρόγραμμά θα πρέπει να παίρνει δύο ορίσματα από την γραμμή εντολών στην μορφή ./mirror low high, με το πρώτο (low) να είναι το κάτω όριο και το δεύτερο να είναι το άνω όριο (high). Τα δύο όρια είναι κλειστά, δηλαδή η αναζήτηση πρέπει να γίνει στο σύνολο [low, high]. Για οποιαδήποτε είσοδο δεν είναι μέσα στις προδιαγραφές το πρόγραμμα πρέπει να επιστρέφει με κωδικό εξόδου (exit code) 1. Εάν δοθεί άνω όριο χαμηλότερο του κάτω ορίου το πρόγραμμα πρέπει να τερματίσει με κωδικό εξόδου 1.
• Όλοι οι φυσικοί που θα δοθούν στο πρόγραμμά σας θα είναι στο εύρος: [1, 10^15]. Εάν δοθούν μη-θετικοί ακέραιοι ή ακέραιοι άνω του 10^15 το πρόγραμμά σας πρέπει να τερματίζει με κωδικό εξόδου 1. Οποιαδήποτε άλλη μη ακέραια είσοδος – για παράδειγμα το string “mpampis” – είναι εκτός προδιαγραφών και δεν θα ελεγχθεί.
• Το αρχείο C που θα υποβληθεί πρέπει να μεταγλωττίζεται χωρίς ειδοποιήσεις για λάθη και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το αρχείο σας πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με την ακόλουθη εντολή σε ένα από τα μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr): gcc -O3 -Wall -Wextra -Werror -pedantic -o mirror mirror.c -lm
• README Filepath: mirror/README.md
• Ένα αρχείο που να περιέχει ένα στοιχείο εισόδου και ένα εξόδου *διαφορετικά* από αυτά της άσκησης. Συγκεκριμένα προτείνουμε να βάλετε έναν συνδυασμό που θεωρείται ότι είναι δύσκολος να γίνει σωστός κατά την υλοποίηση.
  • input Filepath: mirror/test/input
  • output Filepath: mirror/test/output

  Για παράδειγμα, το περιεχόμενο του input αρχείου μπορεί να είναι: “1 100000” και του αντίστοιχου output: “110620”. Προσοχή: αυτό το παράδειγμα δεν θα γίνει δεκτό από την άσκηση επειδή αυτό το input-output ζευγάρι υπάρχει ήδη παρακάτω, επομένως πρέπει να διαλέξετε κάποιο άλλο.

• Πρέπει να ολοκληρώνει την εκτέλεση μέσα σε: 60 δευτερόλεπτα.
• Δεν επιτρέπεται να γίνει χρήση πινάκων/δεικτών πέρα από το διάβασμα των ορισμάτων της main.
• Δεν επιτρέπεται χρήση προϋπολογισμένων αποτελεσμάτων. Το πρόγραμμά σας πρέπει να υπολογίζει το αποτέλεσμα χωρίς “πρότερη γνώση”, δηλαδή χωρίς να έχετε ήδη κωδικοποιήσει τα κατοπτρικά πρώτα τετράγωνα που έχετε βρει από προηγούμενους υπολογισμούς σας μέσα στον κώδικα.

Παρακάτω παραθέτουμε την αλληλεπίδραση με μια ενδεικτική λύση:

thanassis@linux14:~$ gcc -O3 -Wall -Wextra -Werror -pedantic -o mirror mirror.c -lm
thanassis@linux14:~$ ./mirror 1 100000
110620
thanassis@linux14:~$ ./mirror 1 10000000
15633754
thanassis@linux14:~$ ./mirror 1 1000000000000
53009475688
thanassis@linux14:~$ time ./mirror 1 1000000000000
53009475688

real    0m0,025s
user    0m0,023s
sys     0m0,000s

Κατά την διάρκεια της αποσφαλμάτωσης του προγράμματος, μπορούμε να επιβεβαιώσουμε τα επιμέρους αποτελέσματα τυπώνοντας τους αριθμούς που αποτελούν κάθε άθροισμα. Για παράδειγμα, το πρώτο αποτέλεσμα είναι 110620 = 169 + 961 + 12769 + 96721 - και αυτοί οι 4 αριθμοί είναι τα μόνα κατοπτρικά πρώτα τετράγωνα στο εύρος [1, 100000].

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

Υπόδειξη

Μην διατρέχετε όλους τους αριθμούς του εύρους (μέχρι 10^15): διατρέξτε τους υποψήφιους πρώτους p με p² στο εύρος, δηλαδή μέχρι την τετραγωνική ρίζα του high. Χρειάζεστε μικρές συναρτήσεις για «είναι πρώτος», «κάτοπτρο αριθμού» (με % και /) και «είναι τέλειο τετράγωνο» (προσοχή στη στρογγυλοποίηση της sqrt σε μεγάλους αριθμούς). Οι τιμές και το άθροισμα δεν χωράνε σε int, και θυμηθείτε ότι δεν επιτρέπονται πίνακες.

Δείτε επίσης

• Υποδειγματική υποβολή φοιτητή (περιέχει λύση: δείτε την αφού λύσετε την άσκηση)

Αριθμός στον οδηγό: Α15.16 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: hw-2023-hw1-mirror · Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2023-hw1-mirror.html · Markdown (GitHub)