题目描述
这是一个斐波那契数列:
f1 = 1
f2 = 2
fn = fn-1 + fn-2 (n>=3)
蔡老板想知道,给你两个数a、b,你能否求出在区间[a,b]里有多少个斐波那契数。
第四届“图灵杯”NEUQ-ACM程序设计竞赛 C: 来简单地数个数【Java大数】。
这是一个斐波那契数列:
f1 = 1
f2 = 2
fn = fn-1 + fn-2 (n>=3)
蔡老板想知道,给你两个数a、b,你能否求出在区间[a,b]里有多少个斐波那契数。
多组数据输入。一行为一组输入数据,包括两个非负整数a、b(a <= b <= 10^100),当a=b=0时输入终止。
对每组输入,输出单独一行,包含一个整数表示区间[a,b]里的斐波那契数个数。
10 100 1234567890 9876543210 0 0
5 4
思路:
Java暴力求一波大数即可。
import java.io.*; import java.util.*; import java.math.BigInteger; public class Main{ public static void main(String args[]) throws Exception { Scanner cin=new Scanner(System.in); BigInteger[] f = new BigInteger[1200]; f[1]=BigInteger.valueOf(1); f[2]=BigInteger.valueOf(2); for(int i=3;i<=1100;i++) { f[i]=f[i-1].add(f[i-2]); } while (cin.hasNext()) { int cont=0; BigInteger l,r; BigInteger Zero=BigInteger.valueOf(0); l = cin.nextBigInteger(); r = cin.nextBigInteger(); if(l.compareTo(Zero)==0&&r.compareTo(Zero)==0) // { break; // } for(int i=1;i<=1100;i++) { if(f[i].compareTo(l)>=0&&f[i].compareTo(r)<=0)cont++; } System.out.println(cont); // c=a.add(b); // c = a+b; // System.out.println(f[2].toString()); } } }