杭电OJ(HDOJ)1316题:How many Fibs?(大数操作——比较)
题意:fib[1]=1,fib[2]=2,fib[n]=fib[n-1]+fib[n-2]。给一个区间[a,b],其中a<=b<=10^100,求出在些区间的Fibonacci数有多少个。测试示例有多个,当a与b都输入0时结束。 示例输入:10 100 示例输出:5 解决方案:用equals()函数,a.equals(b),如果a==b,返回true;a!=b,返回false。附:java 1.7 APIs 1、为了节省内存空间,先求出第一个大于10^100的Fib数,结果为480。所以数组最大只要开480。 import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n; BigInteger []arr = new BigInteger[1000]; BigInteger t = new BigInteger("10").pow(100); arr[0] = new BigInteger("1"); arr[1] = new BigInteger("2"); int i=2; while(arr[i-1].compareTo(t)<0){ arr[i]=arr[i-1].add(arr[i-2]); i++; } System.out.println(i+"n"+arr[i-1]+"n"+t); } } 运行输出: 480 2、循环结束条件:依次进行比较,当arr[i]>b时,说明已超出区间,结束循环。如果a<=arr[i]<=b,统计Fibs数个数的变量cnt加1。 import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { //声明部分 Scanner input = new Scanner(System.in); int i,cnt; BigInteger []arr = new BigInteger[480]; BigInteger a,b; //预处理 arr[0] = new BigInteger("1"); arr[1] = new BigInteger("2"); for( i = 2 ;i<480;i++) arr[i]=arr[i-1].add(arr[i-2]); //主体部分 while(true){ a=input.nextBigInteger(); b=input.nextBigInteger(); if(a.equals(BigInteger.ZERO)&&b.equals(BigInteger.ZERO)) break; i=0; cnt=0; while(arr[i].compareTo(b)<=0) { if(arr[i].compareTo(a)>=0) cnt++; i++; } System.out.println(cnt); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |