Ένα παιδί ανεβαίνει μια σκάλα και σε κάθε βήμα του ανεβαίνει 1, 2 ή 3 σκαλιά. Έστω
ότι η σκάλα έχει 5 σκαλιά. Ένας τρόπος να τα ανέβει είναι 1-1-1-1-1, δηλαδή ένα σκαλί
την φορά. Ένας άλλος είναι ο 2-2-1 (δύο σκαλιά στα πρώτα δύο βήματα και μετά ένα
σκαλί). Άλλοι πιθανοί τρόποι είναι οι 3-2, 2-3, 3-1-1, κ.ο.κ - σε κάθε περίπτωση ο
συνολικός αριθμός των σκαλιών που ανέβηκε πρέπει να ισούται με τον αριθμό των σκαλιών
της σκάλας. Γράψτε ένα πρόγραμμα C το οποίο διαβάζει τον συνολικό αριθμό των
σκαλοπατιών και επιστρέφει τον αριθμό των διαφορετικών τρόπων με τους οποίους το
παιδί μπορεί να ανέβει την σκάλα. Το πρόγραμμά σας θέλουμε να βγάζει σωστά
αποτελέσματα για σκάλες μέχρι 50 σκαλιά. Λάβετε υπόψη σας ότι στην C δεν μπορούν να
αναπαρασταθούν ακέραιοι μεγαλύτεροι από το ^{64}-1$, δεδομένου ότι ο ευρύτερος
τύπος ακεραίου που μπορούμε να έχουμε είναι ο unsigned long long (των 8 bytes). Ο
αλγόριθμός σας πρέπει να έχει χρονική πολυπλοκότητα γρηγορότερη από (n^2)$, όπου
$ ο αριθμός των σκαλιών. Ακολουθούν ενδεικτικές εκτελέσεις:
$ ./step
Please provide the number of steps: 4
There are 7 different ways to climb the ladder
$ ./step
Please provide the number of steps: 5
There are 13 different ways to climb the ladder
$ ./step
Please provide the number of steps: 6
There are 24 different ways to climb the ladder
$ ./step
Please provide the number of steps: 50
There are 10562230626642 different ways to climb the ladder
Σκεφτείτε το τελευταίο βήμα του παιδιού: ήταν 1, 2 ή 3 σκαλιά, οπότε οι τρόποι για
$ σκαλιά εκφράζονται μέσω των τρόπων για λιγότερα σκαλιά. Η απλή αναδρομή
επαναϋπολογίζει τα ίδια υποπροβλήματα εκθετικά πολλές φορές· υπολογίστε τις τιμές από
κάτω προς τα πάνω (ή απομνημονεύστε τις) ώστε να πετύχετε (n)$. Προσέξτε τις
αρχικές περιπτώσεις και χρησιμοποιήστε unsigned long long με %llu.
Αριθμός στον οδηγό: Α25.5
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2023-dec-q3 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2023-dec-q3.html ·
Markdown (GitHub)