Η εικασία Collatz είναι ένα από τα πιο διάσημα άλυτα προβλήματα των μαθηματικών. Πολλοί μαθηματικοί έχουν επιχειρήσει κατά καιρούς να την αποδείξουν και μέχρι στιγμής δεν έχουμε ακόμα μια ευρέως αποδεκτή απόδειξη. Η εικασία ισχυρίζεται κάτι πολύ απλό: ότι η επανάληψη δυο απλών αριθμητικών πράξεων με μια συγκεκριμένη διαδικασία μπορεί να μετατρέψει οποιονδήποτε θετικό ακέραιο στο 1. Η διαδικασία των πράξεων έχει ως εξής:
Για παράδειγμα, έστω \(N = 3\). Η παραπάνω διαδικασία θα παράξει την ακολουθία: 3, 10, 5, 16, 8, 4, 2, 1. Μπορείτε να δοκιμάσετε το ίδιο με τον αγαπημένο σας θετικό ακέραιο και να ελέγξετε την ακολουθία που παράγεται. Ας πάρουμε για παράδειγμα το 42, που οδηγεί στην ακολουθία: 42, 21, 64, 32, 16, 8, 4, 2, 1. Λογικά και η δική σας επιλογή κατέληξε στο 1 μετά από μερικά βήματα - αν όχι ίσως έχετε την ευκαιρία να γίνετε εκατομμυριούχοι (ποιος είπε ότι τα μαθηματικά δεν έχουν λεφτά!).
Για κάθε θετικό ακέραιο \(N\), ο αριθμός στοιχείων της ακολουθίας που παράγεται μέχρι να καταλήξουμε στο 1, λέγεται μήκος ακολουθίας Collatz. Για παράδειγμα, για \(N = 3\), το μήκος της ακολουθίας είναι 8 (η ακολουθία έχει 8 στοιχεία: 3, 10, 5, 16, 8, 4, 2, 1). Αντίστοιχα για τον αριθμό 42, το μήκος ακολουθίας Collatz είναι 9. Αν \(N = 1\), τότε έχουμε το ελάχιστο μήκος 1.
Σε αυτήν την άσκηση, καλείστε να γράψετε ένα πρόγραμμα collatz.c που να βρίσκει το μήκος
της ακολουθίας collatz για έναν αριθμό.
1.1 Κατασκευάστε τη συνάρτηση int isodd(int n) που δέχεται σαν όρισμα έναν ακέραιο
n και επιστρέφει 1, αν ο αριθμός είναι περιττός, ή 0, αν ο αριθμός είναι άρτιος.
1.2 Γράψτε σε γλώσσα C μια συνάρτηση int collatz_it(int n) που υπολογίζει το μήκος
ακολουθίας collatz - δηλαδή το πλήθος των αριθμών της ακολουθίας που ξεκινά από τον n
και καταλήγει στο 1 (συμπεριλαμβανομένων και των δύο). Ολοκληρώστε την υλοποίηση με δομή
επανάληψης.
Ορισμός συνάρτησης
<τύπος επιστροφής> <όνομα συνάρτησης>(<τυπικές παράμετροι>) { <εντολές και δηλώσεις> }Ο τύπος επιστροφής είναι ο τύπος της τιμής που επιστρέφει η συνάρτηση μέσω της εντολής
return <παράσταση>;. Αν η συνάρτηση δεν επιστρέφει τιμή, ο τύπος επιστροφής της ορίζεται ωςvoid.Οι τυπικές παράμετροι είναι οι μεταβλητές - μαζί με τους τύπους τους - που χρησιμοποιεί η συνάρτηση και παίρνουν τιμές από την καλούσα συνάρτηση. Γράφονται χωρισμένες με κόμμα.
Αν μια συνάρτηση καλείται πριν οριστεί, πρέπει να έχει προηγηθεί η προαναγγελία του πρωτοτύπου της - ο ορισμός της χωρίς σώμα, με ερωτηματικό στο τέλος:
int collatz_it(int n); /* πρωτότυπο: προαναγγέλλει τη συνάρτηση */
int main(void)
{
/* εδώ μπορούμε πλέον να καλέσουμε την collatz_it */
}
int collatz_it(int n) /* ο ορισμός της συνάρτησης */
{
/* ... */
}
1.3 Υλοποιήστε τον ίδιο αλγόριθμο σε μια συνάρτηση int collatz(int n) κάνοντας χρήση
αναδρομής και χωρίς να χρησιμοποιήσετε άλλη δομή επανάληψης.
1.4 Ελέγξτε τα αποτελέσματά σας ώστε να βεβαιωθείτε ότι το πρόγραμμά σας λειτουργεί σωστά για διάφορες αρχικές τιμές:
$ ./collatz
Number to find the length of the collatz sequence: 42
Iterative result: 9
Recursive result: 9
$ ./collatz
Number to find the length of the collatz sequence: 950000001
Iterative result: 199
Recursive result: 199
Κάποιο από τα αποτελέσματά μας δεν συμφωνεί; Τι μπορεί να πηγαίνει στραβά;
1.5 (Προχωρημένο, Προαιρετικό) Κάνετε το πρόγραμμά σας να δέχεται τον ακέραιο από την γραμμή εντολών, για παράδειγμα:
$ ./collatz 950000001
Iterative result: 199
Recursive result: 199
Για την αναδρομική εκδοχή, διατυπώστε το μήκος για τον n μέσω του μήκους για τον
επόμενο αριθμό της ακολουθίας, με βάση την περίπτωση \(n = 1\). Για το 1.4, υπολογίστε με
το χέρι πόσο γίνεται το \(3 \cdot 950000001 + 1\) και συγκρίνετέ το με το μέγιστο int:
τι τύπος χρειάζεται για τους ενδιάμεσους όρους;
Αριθμός στον οδηγό: Α11.15
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: lab-lab05-collatz ·
Σύνδεσμος: https://progintro.github.io/study/questions/labs/lab-lab05-collatz.html ·
Markdown (GitHub)