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

Α6.14 · Η εικασία Collatz

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

Η εικασία Collatz είναι ένα από τα πιο διάσημα άλυτα προβλήματα των μαθηματικών. Η εικασία ισχυρίζεται ότι η επανάληψη δυο απλών αριθμητικών πράξεων με μια συγκεκριμένη διαδικασία μπορεί να μετατρέψει οποιονδήποτε θετικό ακέραιο στο 1. Η διαδικασία των πράξεων έχει ως εξής:

1. Διάλεξε οποιονδήποτε θετικό ακέραιο N.
2. Αν ο αριθμός είναι 1, τότε τερμάτισε την διαδικασία.
3. Αν είναι άρτιος, ο επόμενος αριθμός στην ακολουθία θα είναι ο N/2.
4. Αν είναι περιττός, ο επόμενος αριθμός στην ακολουθία θα είναι ο 3 × N + 1.
5. Επανάλαβε τα βήματα 2-4 μέχρι να φτάσουμε στο 1.

Για παράδειγμα, έστω N = 3. Η παραπάνω διαδικασία θα παράξει την ακολουθία: 3, 10, 5, 16, 8, 4, 2, 1. Για το 42 παίρνουμε την ακολουθία: 42, 21, 64, 32, 16, 8, 4, 2, 1.

Για κάθε θετικό ακέραιο N, ο αριθμός στοιχείων της ακολουθίας που παράγεται μέχρι να καταλήξουμε στο 1, λέγεται μήκος ακολουθίας Collatz. Για παράδειγμα, για N = 3, το μήκος της ακολουθίας είναι 8 (η ακολουθία έχει 8 στοιχεία: 3, 10, 5, 16, 8, 4, 2, 1). Αντίστοιχα για τον αριθμό 42, το μήκος ακολουθίας Collatz είναι 9. Αν N = 1, τότε έχουμε το ελάχιστο μήκος 1.

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

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

• Repository Name: progintro/hw0-<YourUsername>
• Αρχείο C (Filepath): collatz/src/collatz.c
• Το αρχείο C που θα υποβληθεί πρέπει να μεταγλωττίζεται χωρίς ειδοποιήσεις για λάθη και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το αρχείο σας πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με την ακόλουθη εντολή σε ένα από τα μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr): gcc -O0 -m32 -Wall -Wextra -Werror -pedantic -o collatz collatz.c
• README Filepath: collatz/README.md
• Ένα αρχείο που να περιέχει ένα στοιχείο εισόδου και ένα εξόδου *διαφορετικά* από αυτά της άσκησης. Συγκεκριμένα προτείνουμε να βάλετε έναν συνδυασμό που θεωρείται ότι είναι δύσκολος να γίνει σωστός κατά την υλοποίηση.
  • input Filepath: collatz/test/input
  • output Filepath: collatz/test/output

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

• Όλοι οι ακέραιοι που θα δοθούν στο πρόγραμμά σας θα είναι στο εύρος [−100000000, 100000000]
• Το ελάχιστο κάτω όριο που είναι δεκτό: 1.
• Το μέγιστο άνω όριο που είναι δεκτό: 100.000.000.
• Αν δοθεί οποιοσδήποτε μη θετικός αριθμός στα όρια η είσοδος θεωρείται μη αποδεκτή το πρόγραμμα πρέπει να τυπώνει: “0”.
• Πρέπει να ολοκληρώνει την εκτέλεση μέσα σε: 4 λεπτά.
• Μέγιστο μέγεθος αρχείου C που μπορεί να χρησιμοποιηθεί στην υποβολή: 8KB.

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

thanassis@linux14:~$ hostname
linux14
thanassis@linux14:~$ gcc -O0 -m32 -Wall -Wextra -Werror -pedantic -o collatz collatz.c
thanassis@linux14:~$ ./collatz 1 10
20
thanassis@linux14:~$ ./collatz 900 1000
174
thanassis@linux14:~$ ./collatz 80000 100000
333
thanassis@linux14:~$ ./collatz 100 1000000
525
thanassis@linux14:~$ ./collatz 100 100000000
950
thanassis@linux14:~$ ./collatz -1 100
0

Ενδεικτικοί χρόνοι:

thanassis@linux14:~$ time ./collatz 100 1000000
525

real 0m1,343s
user 0m1,338s
sys 0m0,004s
thanassis@linux14:~$ time ./collatz 100 100000000
950

real 3m0,212s
user 3m0,206s
sys 0m0,000s

Ο παραπάνω χρόνος μπορεί να είναι και πιο γρήγορος ανάλογα με την υλοποίηση / μεταγλώττιση / μηχάνημα στο οποίο τρέχει. Αν επιθυμείτε να τα βελτιώσετε ίσως χρειαστεί λίγο παραπάνω έρευνα από μέρους σας σε θέματα για τα οποία δεν έχουμε μιλήσει ακόμα στο μάθημα, αλλά φυσικά πιο γρήγορες υποβολές είναι ευπρόσδεκτες:

thanassis@linux14:~$ time ./collatz_fast 100 100000000
950

real 0m8,034s
user 0m6,789s
sys 0m1,244s

Στο αρχείο README.md πρέπει να προσθέσετε οποιεσδήποτε παρατηρήσεις σας κατά την διεκπεραίωση της άσκησης. Ο κώδικας απαιτείται να είναι καλά τεκμηριωμένος με σχόλια καθώς αυτό θα είναι μέρος της βαθμολόγησης. Για την υποβολή με την καλύτερη απόδοση (πιο γρήγορη από πλευράς χρόνου) θα ζητήσουμε μια γρήγορη (5λεπτη) παρουσίαση στο μάθημα, για την οποία θα λάβει +100% της βαθμολογίας (+50 Μονάδες).

Υπόδειξη

Γράψτε πρώτα μια συνάρτηση που υπολογίζει το μήκος για ένα N και μετά έναν βρόχο πάνω στο εύρος που κρατά το μέγιστο· τα όρια έρχονται από το argv με atoi. Προσέξτε ότι με -m32 ο int είναι 32 bit, ενώ οι ενδιάμεσοι όροι της ακολουθίας για N κοντά στο 10^8 ξεπερνούν κατά πολύ το 2^32: χρειάζεστε έναν ευρύτερο ακέραιο τύπο. Σκεφτείτε επίσης τι γίνεται αν το κάτω όριο είναι μεγαλύτερο από το άνω.

Δείτε επίσης

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

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