一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
数据范围:
要求:时间复杂度: ,空间复杂度:
本题输入仅一行,即一个整数 n
输出跳上 n 级台阶有多少种跳法
2
2
青蛙要跳上两级台阶有两种跳法,分别是:先跳一级,再跳一级或者直接跳两级。因此答案为2
7
21
import java.math.BigInteger; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case int a = in.nextInt(); BigInteger count = BigInteger.valueOf(1); for (int i = 0; i < a; i++) { if ((a - i) % 2 == 0) { if (i > 0) { //数学的排列组合公式:排列总个数的阶乘/每个元素个数阶乘的乘积 count = count.add(jc(i + (a - i) / 2).divide(jc(i).multiply(jc((a - i) / 2)))); } else { count = count.add(BigInteger.valueOf(1)); } } } System.out.println(count); } } /**阶乘 */ private static BigInteger jc(int num) { BigInteger count = BigInteger.valueOf(num); for (int i = num - 1; i > 1; i-- ) { count = count.multiply(BigInteger.valueOf(i)); } return count; } }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case /*int a = in.nextInt(); int b = in.nextInt(); System.out.println(a + b);*/ int num = in.nextInt(); int arr[] = new int[num + 1]; if(num == 1 || num == 2){ System.out.println(num); return; } arr[1] = 1; arr[2] = 2; for(int i = 3;i <= num;i++){ arr[i] = arr[i - 2] + arr[i - 1]; } System.out.println(arr[num]); } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.close(); int res = helper(n); System.out.println(res); } public static int helper(int n) { // 跳一级有一种跳法,跳两级有两种跳法 if(n < 3) return n; int first = 1, second = 2; for(int i = 3; i <= n; i++) { int tmp = first + second; first = second; second = tmp; } return second; } }