蓝桥杯省赛编程第一题 Fibonacci数列 求解答
蓝桥杯第十届研究生省赛编程题第一题：
Fibonacci数列，Fi=1，F2=1,
Fi=Fi-1+Fi-2，特殊性质，Fi/Fi+1会趋于黄金分割，为了验证这一性质，给定N，计算FN/FN+1，保留8位小数。
输入：N 1-2000000000
输出：保留八位小数。
样例：输入2 输出0.50000000
以下是我写的最无脑的递归，但是输入到50就算的很慢了，输入再高一点就字节栈溢出了，无法满足题目的2000000000，请问怎么做，我只想到动态规划，但是不会操作。
希望大佬给个代码学习以下。
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
long i=sc.nextLong();
long m=(long) fun(i);
System.out.println("m:"+m);
long n=(long) fun(i+1);
System.out.println("n:"+n);
float result=(float)m/(float)n;
//打印小数点后面8位
String[] data=String.valueOf(result).split("\\.");
System.out.println(data[0]);
System.out.println(data[1]);
ArrayList<String> list=new ArrayList<String>();
list.add(data[0]);
list.add(data[1]);
while(list.get(1).length()<8) {
list.set(1,list.get(1)+"0");
}
System.out.println(list.get(0)+"."+list.get(1));
}
public static float fun(long a) {
if(a==2||a==1) {
return 1;
}else {
return fun(a-1)+fun(a-2);
}
} ------------------以下是按照评论里大佬的提示用矩阵快速幂做的，但是输入到百万级效率又不够了，该咋办。
package lanqiao;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.Scanner;
public class Main4 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
long i=sc.nextLong();
BigInteger m=fun(i);
BigDecimal de1=new BigDecimal(m);
System.out.println("m:"+m);
BigInteger n= fun(i+1);
BigDecimal de2=new BigDecimal(n);
System.out.println("n:"+n);
BigDecimal result=de1.divide(de2,8,BigDecimal.ROUND_CEILING);
//打印小数点后面8位
System.out.println(result);
}
//调用函数运算
public static BigInteger fun(long o) {
if(o==1||o==2) {
return new BigInteger("1");
}
BigInteger[] i= {new BigInteger("1"),new BigInteger("1")};
BigInteger a[][]= {{new BigInteger("1"),new BigInteger("1")},{new BigInteger("1"),new BigInteger("0")}};
BigInteger result[][]=fast(a, a, o-2);
System.out.println(result[0][0]+" "+result[0][1]);
return result[0][0].add(result[0][1]);
}
//矩阵乘法
public static BigInteger[][] Matrix(BigInteger[][] a,BigInteger[][] b){
BigInteger[][] l={{new BigInteger("0"),new BigInteger("0")},{new BigInteger("0"),new BigInteger("0")}};
System.out.println("lkkk");
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
l[i][j]=l[i][j].add(a[i][k].multiply(b[k][j]));
}
}
}
return l;
}
//矩阵快速幂
public static BigInteger[][] fast(BigInteger[][] a,BigInteger[][] b,long n){
BigInteger[][] result= {{new BigInteger("1"),new BigInteger("0")},{new BigInteger("0"),new BigInteger("1")}};
while(n!=0) {
if((n & 1) !=0) {
result=Matrix(result, a);
}
n>>=1;
a=Matrix(a, a);
}
return result;
}
}
