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

Α11.20 · Άψογα Τετράγωνα (Bonus)

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

Αυτή η άσκηση είναι Bonus, δηλαδή η λύση της δεν είναι απαραίτητη για να πάρει κάποιος/α όλες τις μονάδες της Εργασίας 1. Σε αυτήν την άσκηση θα ασχοληθούμε με μια κατηγορία αριθμών που ονομάσαμε άψογα τετράγωνα.

Ορισμός 6. Ένας φυσικός αριθμός λέγεται άψογο τετράγωνο (flawless square), όταν είναι τέλειο τετράγωνο και ταυτόχρονα ισούται με το τετράγωνο του αθροίσματος διαδοχικών ψηφίων του. Τονίζουμε ότι όλα τα ψηφία πρέπει να χρησιμοποιηθούν. Για παράδειγμα, ο αριθμός 1 είναι ένα άψογο τετράγωνο καθώς είναι το τετράγωνο ενός αριθμού (1) και ταυτόχρονα το άθροισμα των ψηφίων του στο τετράγωνο (1²) ισούται με τον αρχικό αριθμό. Αντίστοιχα, ο αριθμός 81 είναι ένα άψογο τετράγωνο, καθώς είναι τέλειο (9²) και ταυτόχρονα το άθροισμα των ψηφίων του στο τετράγωνο ισούται με τον αρχικό αριθμό ((8 + 1)² = 81). Παρακάτω παραθέτουμε μερικά ακόμα παραδείγματα άψογων αριθμών:

1296    = (1 + 29 + 6)^2                  = 36^2
3025    = (30 + 25)^2                     = 55^2
8281    = (8 + 2 + 81)^2 = (82 + 8 + 1)^2 = 91^2
998001  = (998 + 0 + 0 + 1)^2             = 999^2
4941729 = (494 + 1729)^2                  = 2223^2

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

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

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

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

• Πρέπει να ολοκληρώνει την εκτέλεση μέσα σε: 10 δευτερόλεπτα.
• Δεν επιτρέπεται να γίνει χρήση πινάκων/δεικτών πέρα από το διάβασμα των ορισμάτων της main.
• Δεν επιτρέπεται χρήση προϋπολογισμένων αποτελεσμάτων. Το πρόγραμμά σας πρέπει να υπολογίζει το αποτέλεσμα χωρίς “πρότερη γνώση”, δηλαδή χωρίς να έχετε ήδη κωδικοποιήσει τα άψογα τετράγωνα που έχετε βρει από προηγούμενους υπολογισμούς σας μέσα στον κώδικα.
• Καθώς αυτή η εργασία είναι Bonus, θα ελέγξουμε και ποιοτικά χαρακτηριστικά της υποβολής. Μια ιδιαίτερα δυσνόητη ή μη διαχειρίσιμη λύση (π.χ., 6 nested if-else, 35 μεταβλητές στην ίδια συνάρτηση κτλ) θα οδηγήσει σε αφαίρεση μονάδων κατά την κρίση του εξεταστή.

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

thanassis@linux14:~$ gcc -O3 -Wall -Wextra -Werror -pedantic -o flawless flawless.c -lm
thanassis@linux14:~$ ./flawless 1 1000
182
thanassis@linux14:~$ ./flawless 1 100000
184768
thanassis@linux14:~$ ./flawless 1 10000000
30940314
thanassis@linux14:~$ time ./flawless 1 10000000000
499984803178

real    0m0,204s
user    0m0,203s
sys     0m0,001s

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

Υπόδειξη

Διατρέξτε τις ρίζες k (από √low έως √high) αντί για όλους τους αριθμούς του εύρους, και για κάθε k² ρωτήστε: «μπορώ να κόψω τα ψηφία του σε διαδοχικά κομμάτια με άθροισμα k;». Αυτό γράφεται φυσικά αναδρομικά: αφαιρέστε ένα κομμάτι από το τέλος του αριθμού (με % και / σε δύναμη του 10) και ρωτήστε το ίδιο για το υπόλοιπο με μικρότερο στόχο. Κόψτε νωρίς τους κλάδους όπου το μερικό άθροισμα ήδη ξεπέρασε το k, και προσέξτε τα ενδιάμεσα μηδενικά (π.χ. 998001).

Δείτε επίσης

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

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