Möglichkeiten des Kletterns n Treppen mit einem Zwang auf dem 20. Stock

Question

Im Lösen eines Rekursionsproblems, in dem die Funktion int Treppe (int n) die Anzahl der Möglichkeiten beim Treppensteigen auf n zurückgibt, mit den Bedingungen von entweder 1 Schritt oder 2 Schritte. Der folgende Code löst dieses Problem:

int stairs(int n) 
{ 
    if (n<0) return 0; 
    if (n==0) return 1; 
    return stairs(n-1) + stairs(n-2); 
} 

Jetzt habe ich eine Einschränkung, die besagt: Wenn Sie den 20. Stock zu erreichen, müssen Sie einen Aufzug benutzen, die Sie automatisch den ganzen Weg bis zum n-ten Etage nimmt. Wenn du aus irgendeinem Grund Level 20 überspringst (zum Beispiel Level 19 erreichen und dann 2 Etagen bis Level 21 hochsteigen), fahre wie gewohnt fort. Suchen Sie die Anzahl der Möglichkeiten für die obige Einschränkung. Was ich bisher getan, ist dies:

int stairs20(int n) 
{ 
    if (n<=20) return stairs(n); 
    return stairs(20) + stairs(n-21); 
} 

Die Logik hinter dem Code ist die Anzahl der Möglichkeiten in dem Erreichen des 20. Etage, und die Anzahl der Möglichkeiten von der 21. Etage und bis zu berechnen. Ich nehme an, dass dies nicht die richtige Antwort findet und würde mich beraten lassen, wo ist mein Fehler oder was berechne ich nicht?

Answer 1

Wenn n>20,

• Sie zuerst 20. Etage erreichen, gehen Sie dann den ganzen Weg nach oben =>stairs(20)

• Sie auch 19. Etage erreichen, gehen Sie dann bis zum 21. Stock, von 21 Boden, haben Sie stairs(n-21) Wege zu Boden n, so => ​​stairs(19)*stairs(n-21)

es also zusammenzufassen ist stairs(20) + stairs(19) * stairs(n-21).

Sie können dynamische Programmierung verwenden, um die Berechnung desselben Werts zu vermeiden.

Answer 2

Die grundlegende Rekursion Schema ist das folgende

int stairs(unsigned int n) { 
    if (n < 2) 
     return 1; 
    return stairs(n-1) + stairs(n-2); 
} 

Nun ist die Frage, die Sie sich stellen müssen, ist, wie die Regel 20 bis treppe angewendet wird die Rekursion Schema ändern? Wenn n > 20, dann ist stairs(n) gleich stairs(20) + <number_of_ways_to_climb_to_n_without_reaching_floor20). Wie vermeidest du den Boden 20? Wenn Sie die 19. Etage erreichen und direkt auf die 21. Etage gehen, müssen Sie auf der 21. Etage bis zur Etage n aufsteigen. Es gibt also stairs(19)*stairs(n-21) Boden zu erreichen n ohne Boden zu stoppen 20.

Die endgültige Antwort lautet daher:

int stairs20(unsigned int n) { 
    if(n > 20) { 
     return stairs(20) + stairs(19)*stairs(n-21); 
    } else { 
     return stairs(n); 
    } 
}