Παραγγείλατε πίτσες για να δείτε τον τελικό του Euro και διαπιστώσατε τελευταία στιγμή πως ήρθαν υπερβολικά πολλοί καλεσμένοι (ως συνήθως κάποιοι αυτοπροσκλήθηκαν). Παρόλα αυτά κάνατε την καρδιά σας πέτρα και αποφασίσατε να ταΐσετε όσους περισσότερους γίνεται. Και τι καλύτερος τρόπος για να γίνει αυτό παρά μέσα από ένα πρόγραμμα - περνάς ευχάριστα τον χρόνο σου όσο παίζουν οι διαφημίσεις.
Γράψτε ένα πρόγραμμα το οποίο διαβάζει από την πρότυπη είσοδο: (1) τον αριθμό από πίτσες που έχουμε, (2) τον αριθμό κομματιών κάθε πίτσας, (3) τον αριθμό των ατόμων που έχουμε, (4) τον αριθμό των κομματιών που επιθυμεί το κάθε άτομο και τυπώνει στην πρότυπη έξοδο τον μέγιστο αριθμό ατόμων που μπορούμε να ικανοποιήσουμε πλήρως (αν κάποιο άτομο επιθυμεί 5 κομμάτια, πρέπει να φάει 5, αν απλά φάει 1 δεν αρκεί). Περιγράψτε την χρονική και χωρική πολυπλοκότητα του αλγορίθμου σας και εξηγήστε αν είναι η βέλτιστη (8/25 της βαθμολογίας). Παράδειγμα εκτέλεσης ακολουθεί:
$ ./pizza
Number of pizzas available: 3
Enter the number of slices for each pizza: 8 10 5
Number of people: 4
Number of slices desired by each person: 6 9 7 5
Max number of people that can be satisfied: 3
Για να ικανοποιήσετε όσο το δυνατόν περισσότερα άτομα, ποιους συμφέρει να εξυπηρετήσετε πρώτους; Σκεφτείτε μια άπληστη (greedy) στρατηγική που βασίζεται σε ταξινόμηση των επιθυμιών, και αιτιολογήστε γιατί καμία άλλη επιλογή δεν δίνει περισσότερα άτομα. Οι πίνακες έχουν μέγεθος που δίνεται στην είσοδο, και η πολυπλοκότητα καθορίζεται κυρίως από τον αλγόριθμο ταξινόμησης που θα διαλέξετε.
Αριθμός στον οδηγό: Α25.13
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2024-jul-q3 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2024-jul-q3.html ·
Markdown (GitHub)