Πρόγραμμα: levelup.c (25 μονάδες)
Ένα pokémon μπορεί να ανέβει 1, 2 ή 3 επίπεδα σε κάθε αγώνα ανάλογα με το πόσο δύσκολος είναι ο αντίπαλος (εύκολος, μεσαίος, δύσκολος). Γράψτε ένα πρόγραμμα που παίρνει ένα επίπεδο “στόχο” ως όρισμα και τυπώνει στην πρότυπη έξοδο με πόσους διαφορετικούς τρόπους μπορεί να φτάσει σε αυτό. Έστω ότι θέλουμε να φτάσουμε στο επίπεδο 5. Ένας τρόπος να φτάσουμε είναι 1-1-1-1-1, δηλαδή να κερδίσουμε 5 εύκολους αντιπάλους. Ένας άλλος είναι ο 2-2-1 (δύο μεσαίους και μετά έναν εύκολο). Άλλοι πιθανοί τρόποι είναι οι 3-2, 2-3, 3-1-1, κ.ο.κ - σε κάθε περίπτωση θέλουμε να φτάσουμε ακριβώς στο επίπεδο στόχο. Παραδείγματα εκτελέσεων ακολουθούν:
$ gcc -o levelup.c levelup
$ ./levelup 3
There are 4 different ways to reach level 3
$ ./levelup 5
There are 13 different ways to reach level 5
$ ./levelup 6
There are 24 different ways to reach level 6
$ ./levelup 50
There are 10562230626642 different ways to reach level 50
Σκεφτείτε αναδρομικά: με πόσους τρόπους φτάνω στο n αν ο τελευταίος αγώνας μού έδωσε 1, 2 ή 3 επίπεδα; Η απλή αναδρομή όμως ξαναϋπολογίζει τα ίδια υποπροβλήματα εκθετικά πολλές φορές και δεν θα τελειώσει για n = 50· αποθηκεύστε τα ενδιάμεσα αποτελέσματα ή υπολογίστε από κάτω προς τα πάνω. Το αποτέλεσμα ξεπερνά τον int, και οι αρχικές τιμές (τα n 1, 2, 3 ή 0) θέλουν προσοχή.
Αριθμός στον οδηγό: Α25.7
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2023-fall-ex2-q4 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2023-fall-ex2-q4.html ·
Markdown (GitHub)