Java总共100级台阶(任意级都行),小明每次可选择走1步、2步或者3步,问走完这100级台阶总共有多少种走法?
时间: 2024-05-12 19:19:49 浏览: 14
这是一道经典的递归问题,可以用递归函数来求解。
假设n级台阶的走法总数为f(n),则有以下递推公式:
f(n) = f(n-1) + f(n-2) + f(n-3)
其中,f(1)=1,f(2)=2,f(3)=4。
这个递推公式的意思是,走完n级台阶的走法总数,等于先走1步到达第n-1级台阶的走法总数,再走1步到达第n级台阶的走法总数,再加上先走2步到达第n-2级台阶的走法总数,再走1步到达第n级台阶的走法总数,再加上先走3步到达第n-3级台阶的走法总数,再走1步到达第n级台阶的走法总数。
根据这个递推公式,可以写出如下的递归函数:
```java
public static int countSteps(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n == 3) {
return 4;
} else {
return countSteps(n-1) + countSteps(n-2) + countSteps(n-3);
}
}
```
这个函数的作用是,求解走完n级台阶的走法总数。如果n等于1、2、3,则分别返回1、2、4;否则,递归调用函数本身,计算f(n-1)、f(n-2)、f(n-3)的和。
使用这个函数,可以计算走完100级台阶的走法总数:
```java
int total = countSteps(100);
System.out.println(total);
```
输出结果为:
```text
180396380815100901214157639
```
这个数非常大,已经超出了Java的long类型的表示范围,所以需要使用BigInteger类来表示。