解法一
这里的青蛙比前面两道题的青蛙更厉害一些,他一次可以跳1
阶,2
阶,3
阶……
。所以要想跳到第n
个台阶,我们可以从第1
个台阶跳上来,也可以从第2
个台阶跳上来……,所以递推公式是
f(n)=f(n-1)+f(n-2)+……+f(2)+f(1);
同样如果我们想跳到第n-1
个台阶,也可以列出下面这个公式
f(n-1)=f(n-2)+……+f(2)+f(1);
通过这两个公式我们可以得出
f(n)=2*f(n-1)
实际上他是个等比数列,base case
当n
等于1
的时候结果为1
,来看下代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt() - 1;
System.out.println(1 << num);
}
}
我把部分算法题整理成了PDF
文档,截止目前总共有1000多页,大家可以下载阅读
链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ 提取码:6666