Γράψτε ένα πρόγραμμα το οποίο παίρνει ως όρισμα από την γραμμή εντολών έναν ακέραιο-στόχο (goal) και από την πρότυπη είσοδο (stdin) ένα σύνολο διαφορετικών υποψηφίων ακεραίων (candidates) και τυπώνει όλες τις πιθανές τριπλέτες υποψηφίων ακεραίων των οποίων το άθροισμα ισούται με τον στόχο. Ο κάθε υποψήφιος ακέραιος μπορεί να χρησιμοποιηθεί μέχρι μία φορά σε κάθε τριπλέτα. Για παράδειγμα αν δοθεί ο στόχος 10 και οι ακέραιοι 6, 1, 7, 2, 3 ως υποψήφιοι για τις τριπλέτες υπάρχουν ακριβώς δύο συνδυασμοί που οδηγούν στον στόχο: \(1 + 3 + 6 = 10\) και \(1 + 2 + 7 = 10\) (ο συνδυασμός \(6 + 2 + 2 = 10\) δεν είναι δεκτός καθώς ο ακέραιος 2 επαναλαμβάνεται).
Ο αλγόριθμός σας πρέπει να έχει χρονική πολυπλοκότητα γρηγορότερη από \(O(n^3)\), όπου \(n\) είναι ο αριθμός των ακεραίων που σας δίνονται. Παραδείγματα εκτέλεσης ακολουθούν:
$ ./triplet 10
Provide the numbers: 6 1 7 2 3
Triplet found: 1 + 2 + 7 = 10
Triplet found: 1 + 3 + 6 = 10
$ ./triplet 42
Provide the numbers: 1 2 3
No triplet leads to 42
$ ./triplet 42
Provide the numbers: 19 21 3 5 12 11
Triplet found: 11 + 12 + 19 = 42
$ ./triplet 42
Provide the numbers: 42 27 25 12 31 5 26 40 34 3 18
Triplet found: 3 + 5 + 34 = 42
Triplet found: 3 + 12 + 27 = 42
Triplet found: 5 + 12 + 25 = 42
Το πλήθος των αριθμών δεν είναι γνωστό από πριν, οπότε διαβάστε τους μέχρι το EOF σε
πίνακα που μεγαλώνει με realloc. Ταξινομήστε τον πρώτα: αυτό κάνει τις τριπλέτες να
βγαίνουν σε αύξουσα σειρά, όπως στα παραδείγματα, και σας επιτρέπει, για σταθερό
μικρότερο στοιχείο, να ψάξετε τα άλλα δύο με δύο δείκτες που κινούνται ο ένας προς τον
άλλον, αντί για τρίτο εμφωλευμένο βρόχο.
Αριθμός στον οδηγό: Α25.11
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2024-dec-q3 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2024-dec-q3.html ·
Markdown (GitHub)