题解 | #数字在升序数组中出现的次数#

跳台阶

http://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

纯数学解法:

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

由题可设,一共有n个台阶。 则青蛙每种跳法可以设有i个2级跳,就有(n-2i)个1级跳。

那么最多可以有几个2级跳呢?答案是⌊n / 2⌋个。

i 1级跳 2级跳
0 n 0
1 n - 2 1
2 n - 4 2
... ... ...
⌊n / 2⌋ ⌊n / 2⌋ ⌊n / 2⌋

带入数值来看一下: 设n = 5; 当i = 0时,即每次都跳一个台阶,n次跳上去。这种情况只有1种方法

当i = 1时,即有2次跳两个台阶,其他n-2i(即5-2=3)次跳一个台阶。这种情况有4种方法。分别是2111,1211,1121,1112。

当i = 2时,即有2次跳两个台阶,其他n-2i(即5-4=1)次跳一个台阶。这种情况有3种方法。分别是122,212,221。

引入排列组合的思想,计算每种情况的的方法次数。

alt

当i = 0时,即有5个坑位,选0个跳两个台阶。组合种类就是C(5,0) = 1;

当i = 1时,即有4个坑位,选1个跳两个台阶。组合种类就是C(4,1) = 4;

当i = 2时,即有3个坑位,选2个跳两个台阶。组合种类就是C(3,2) = 3;

综上,1 + 4 + 3 = 8。则当n = 5时,共有8种跳法。

坑位计算:跳一个台阶的个数+跳两个台阶的个数。(n-2i) + i = n - i。

/**
 * 
 * @param number int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */

//阶乘 
long factorial(int n, int m)
{
    int i = 1;
    long lNum = 1;
    if (0 == n)
        return 1;
    for (i = m; i <= n; i++)
    {
        lNum *= i;
    }
    return lNum;
}

//组合Cn(m)
int ConbinFunc(int n, int m)
{
    return (int)(factorial(n, n - m + 1) / factorial(m, 1));
}


int jumpFloor(int number ) {
    // write code here
    int i = 0;
    int iNum = 0;
    if (0 == number)
        return 0;
    for (i = 0; i <= number/2; i++)
    {
        iNum += ConbinFunc(number - i, i);
    }
    
    return iNum;
}
全部评论

相关推荐

评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务