Somethings about Floors題解，

Somethings about Floors題解，

題目內容：一個樓梯有N級（N >=0）, 每次走1級或2級, 從底走到頂一共有多少種走法?

輸入要求：只有一行輸入，並且只有一個數N(如果N > 20，則N = N%21，即保證N的范圍控制為：0 <= N <= 20，當取模後的值為0時，輸出1)，代表這個樓梯的級數。

輸出要求：只有一行，輸出從底到頂的走法，後面有換行。

參考樣例：

    輸入： 3

    輸出： 3 

---

 

Hint:

問題分解。

---

分析： 這道題目應該用遞歸的思想去解決推導出公式。如果只有一級樓梯，那麼走法只有一種；如果有兩級樓梯，那麼走法有兩種；...如果有N(N > 2)級樓梯，因為一次可以上一級或者兩級，那麼我們可以考慮從N-1級和N-2級樓梯到N級的走法，那麼F(N) = F(N-1) + F(N-2)。  

---

我的代碼：

#include <stdio.h>
int main() {
    int f0, f1, a;
    int b, n, i;
    scanf("%d", &n);
    n = n % 21;
    if (n == 0 || n == 1) {
        printf("%d\n", 1);
        return 0;
    }
    f0 = 1;
    f1 = 2;
    for (i = 3; i <= n; i++) {
        a = f0 + f1;
        f0 = f1;
        f1 = a;
    }
    printf("%d\n", f1);
    return 0;
}

---

標答：

// from younglee
// solve the problem in two different way, with recursion and no recursion.
#include<stdio.h>
#include<string.h>
#define N 100
 
#define RECUR 1
#define MODE 0
 
int dealWithRecursion(int f);
int dealWithNoRecursion(int f);
// to save the result.
int arr[N];
 
int main(void) {
    int floor;
    scanf("%d", &floor);
    floor %= 21;
    if (MODE == RECUR) {
        printf("%d\n", dealWithRecursion(floor));
    } else {
        memset(arr, 0, sizeof(arr));
        printf("%d\n", dealWithNoRecursion(floor));
    }
    return 0;
}
 
int dealWithRecursion(int f) {
    if (f == 1 || f == 0) return 1;
    return (dealWithRecursion(f - 1) + dealWithRecursion(f - 2));
}
 
int dealWithNoRecursion(int f) {
    if (arr[f] != 0) return arr[f];
    int result;
    if (f == 0 || f == 1) result = 1;
    else result = dealWithNoRecursion(f - 1) + dealWithNoRecursion(f - 2);
    arr[f] = result;
    return result;
}

 

這裡用了兩種方法，遞歸與非遞歸。

 

---