实战编程-超级楼梯

2019-11-06 07:10:14

字体：大中小

来源：转载

供稿：网友

编程要求

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

输入描述:

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数 M（1<=M<=40）,表示楼梯的级数。

输出描述:

对于每个测试实例，请输出不同走法的数量

输入例子:

2 2 3

输出例子:

1 2

import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] array = new int[count]; for (int i = 0; i < array.length; i++) { array[i] = scanner.nextInt(); } for (int i = 0; i < array.length; i++) { System.out.PRintln(cale(array[i])); } } public static int cale(int level) { int[] array = new int[level]; if (level == 1) return 1; array[0] = 1; array[1] = 1; for (int i = 2; i < array.length; i++) { array[i] = array[i - 1] + array[i - 2]; } return array[level - 1]; }}

如果目标层数是1，输出结果为1，只有一种走法

0-1

如果目标层数是2，输出结果为2，总共两种走法

0-1-2 0-2

如果目标层数是3，输出结果为3，总共三种走法

0-1-2-3 0-1-3 0-2-3

如果目标层数是4，输出结果为5，总共五种走法

0-1-2-3-4 0-1-2-4 0-1-3-4 0-2-3-4 0-2-4

经过统计，我们发现了规律

1L—–1 2L—–2 3L—–3 4L—–5 5L—–8 6L—–13

每一层的走法总是前两层的两数之和，有了这个规律，代码就不难实现了。

其实这个规律很有名，叫《斐波那契数列》