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 % ;

    if (n ==  || n == ) {

        printf("%d\n", );

        return ;

    }

    f0 = ;

    f1 = ;

    for (i = ; i <= n; i++) {

        a = f0 + f1;

        f0 = f1;

        f1 = a;

    }

    printf("%d\n", f1);

    return ;

}

标答：

// 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 %= ;

    if (MODE == RECUR) {

        printf("%d\n", dealWithRecursion(floor));

    } else {

        memset(arr, , sizeof(arr));

        printf("%d\n", dealWithNoRecursion(floor));

    }

    return ;

}

int dealWithRecursion(int f) {

    if (f ==  || f == ) return ;

    return (dealWithRecursion(f - ) + dealWithRecursion(f - ));

}

int dealWithNoRecursion(int f) {

    if (arr[f] != ) return arr[f];

    int result;

    if (f ==  || f == ) result = ;

    else result = dealWithNoRecursion(f - ) + dealWithNoRecursion(f - );

    arr[f] = result;

    return result;

}

这里用了两种方法，递归与非递归。

巴特西

Somethings about Floors题解

Hint:

最新文章

热门文章