这里的青蛙比前面两道题的青蛙更厉害一些,他一次可以跳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); } }