Πρόγραμμα: roll.c (25 μονάδες)
Γράψτε ένα πρόγραμμα που παίρνει 3 αριθμούς ως ορίσματα (σε αναπαράσταση μη προσημασμένου 32-bit αριθμού) και ελέγχει αν είναι είναι μια rickroll τριπλέτα. Τρεις αριθμοί a, b και c λέγονται rickroll τριπλέτα εάν υπάρχουν ακέραιοι I, J, K (διαφορετικοί ο ένας από τον άλλον I <> J <> K) έτσι ώστε 2^I * a + 2^J * b = 2^K * c - όπου όλες οι πράξεις είναι μη προσημασμένες mod 2^32. Παραδείγματα εκτέλεσης ακολουθούν:
$ gcc -o roll roll.c
$ ./roll 17 42 101
Found rick-roll triplet: 2^30 * 17 + 2^25 * 42 = 2^26 * 101 = 2483027968
Found rick-roll triplet: 2^30 * 17 + 2^29 * 42 = 2^31 * 101 = 2147483648
Found rick-roll triplet: 2^31 * 17 + 2^26 * 42 = 2^27 * 101 = 671088640
$ ./roll 17 42 100
Found rick-roll triplet: 2^27 * 17 + 2^29 * 42 = 2^25 * 100 = 3355443200
Found rick-roll triplet: 2^28 * 17 + 2^25 * 42 = 2^24 * 100 = 1677721600
Found rick-roll triplet: 2^28 * 17 + 2^30 * 42 = 2^26 * 100 = 2415919104
Found rick-roll triplet: 2^29 * 17 + 2^26 * 42 = 2^25 * 100 = 3355443200
Found rick-roll triplet: 2^29 * 17 + 2^31 * 42 = 2^27 * 100 = 536870912
Found rick-roll triplet: 2^30 * 17 + 2^27 * 42 = 2^26 * 100 = 2415919104
Found rick-roll triplet: 2^30 * 17 + 2^31 * 42 = 2^28 * 100 = 1073741824
Found rick-roll triplet: 2^31 * 17 + 2^28 * 42 = 2^27 * 100 = 536870912
$ ./roll 3 5 7
No rick-roll triplets found.
$ ./roll 0 0 1
No rick-roll triplets found.
Πολλαπλασιασμός με 2^I είναι αριστερή ολίσθηση κατά I, και σε μη προσημασμένο 32-bit τύπο (uint32_t) η αναδίπλωση mod 2^32 γίνεται αυτόματα, οπότε μια εξαντλητική αναζήτηση στα I, J, K είναι αρκετά μικρή. Σκεφτείτε ποιο είναι το λογικό εύρος των εκθετών (τι παθαίνει μια ολίσθηση κατά 32 ή περισσότερα bits;) και ποια σειρά βρόχων δίνει τη σειρά εξόδου του παραδείγματος. Διαβάστε τα ορίσματα με strtoul και απορρίψτε ό,τι δεν χωράει σε 32 bits.
Αριθμός στον οδηγό: Α2.12
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2023-fall-ex4-q3 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2023-fall-ex4-q3.html ·
Markdown (GitHub)