P1255 数楼梯

题目描述

楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

走的方式几种。

输入输出样例

输入 #1复制

4

输出 #1复制

5

说明/提示

60% N<=50 100% N<=5000)

题解

这道题一眼就可以看出,是一道很经典的斐波那契递推问题.

易得公式 $$f[n]=f[n-1]+f[n+2](n>=3)$$ 然后代码写出来运行的时候才发现没那么简单,超时很严重.

这里需要用到java的高精度运算

实际上高精度就是说参与运算的数据和运算结果的范围，超出标准数据类型能表示的数据大小范围的运算。这个时候，如果要得到正确的计算结果，显然不能依靠普通方法实现了。而要在普通运算原理的基础上，加以辅助算法来实现超大数据的计算。例如：求两个100位的数据的和，或者计算两个100位的数字乘积。这时就要用到高精度算法了。

import java.math.BigInteger; import java.util.Scanner; public class P1255 { public static void main (String[]args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); BigInteger a[] = new BigInteger[n + 1]; a[0] = BigInteger.valueOf(0); if (n >= 1) { a[1] = BigInteger.valueOf(1); } if (n >= 2) { a[2] = BigInteger.valueOf(2); } for (int i = 3; i <= n; i++) { a[i] = a[i - 2].add(a[i - 1]); } System.out.println(a[n]); } }