题解 | #数字在升序数组中出现的次数#
跳台阶
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。
引入排列组合的思想,计算每种情况的的方法次数。
当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;
}