Πρόγραμμα: chops.c
Ο Θάνος μόλις παρήγγειλε Ν παϊδάκια (τουλάχιστον 3) και αναρωτιέται με πόσους διαφορετικούς τρόπους μπορεί να τα φάει. Ξέρει ότι με κάθε του μπουκιά μπορεί να φάει 1 ή 2 παϊδάκια. Επειδή πεινάει πολύ σκοπεύει να φάει 3 παϊδάκια με ακριβώς μία μπουκιά. Για παράδειγμα, αν του φέρουν 5 παϊδάκια, μπορεί να τα φάει με 5 τρόπους: 1-1-3 (1 με μια μπουκιά, 1 με μια μπουκιά, 3 με μια μπουκιά), 1-3-1, 3-1-1, 2-3 και 3-2. Αν του φέρουν 3 παϊδάκια υπάρχει ακριβώς ένας τρόπος (3 με την μία). Αν του φέρουν 4 υπάρχουν 2 τρόποι (1-3, 3-1). Γράψτε ένα πρόγραμμα το οποίο παίρνει τον αριθμό από τα παϊδάκια ως ακέραιο όρισμα και τυπώνει τον αριθμό των διαφορετικών τρόπων με τους οποίους ο Θάνος μπορεί να τα φάει όλα. Παραδείγματα εκτέλεσης ακολουθούν:
$ ./chops 2
I would never order less than 3 chops.
$ ./chops 3
There are 1 different ways to eat 3 chops.
$ ./chops 4
There are 2 different ways to eat 4 chops.
$ ./chops 5
There are 5 different ways to eat 5 chops.
$ ./chops 6
There are 10 different ways to eat 6 chops.
$ ./chops 50
There are 168903452400 different ways to eat 50 chops.
Βρείτε πρώτα με πόσους τρόπους τρώγονται k παϊδάκια μόνο με μπουκιές 1 ή 2 (αναδρομική σχέση). Μετά σκεφτείτε πού μπορεί να μπει η μοναδική μπουκιά των 3 και τι μένει αριστερά και δεξιά της. Για N = 50 χρειάζεστε long long και αποφυγή της εκθετικής αναδρομής (υπολογισμός από κάτω προς τα πάνω).
Αριθμός στον οδηγό: Α25.10
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2023-fall-ex14-q4 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2023-fall-ex14-q4.html ·
Markdown (GitHub)