hdu1316(大数的斐波那契数)

题目信息:求两个大数之间的斐波那契数的个数(C++/JAVA)

http://acm.hdu.edu.cn/showproblem.php?pid=1316

这里给出java代码和c++代码

C++：AC代码

#include<iostream>
#include<string>
using namespace std;
string add(string s1,string s2){//字符串模拟大数加法
??? string s;
??? int len1,len2;
??? len1=s1.size()-1; len2=s2.size()-1;
??? int i=0,flag=0;
??? while(len1>-1&&len2>-1){
??????? int sum=flag+(s1[len1--]-'0')+(s2[len2--]-'0');
??????? s+=char ((sum)%10+'0');
??????? flag=sum/10;
??? }
??? while(len1>-1){
??????? int sum=flag+(s1[len1--]-'0');
??????? s+=char ((sum)%10+'0');
??????? flag=sum/10;
??? }
??? while(len2>-1){
??????? int sum=flag+(s2[len2--]-'0');
??????? s+=char ((sum)%10+'0');
??????? flag=sum/10;
??? }
??? if(flag) s+=char ('0'+flag);
??? //cout<<s<<endl;
??? for(int i=0;i<s.size()/2;i++){
??????? char c=s[i];
??????? s[i]=s[s.size()-i-1];
??????? s[s.size()-i-1]=c;
??? }
??? return s;
}
int compareto(string s,string s1){//模拟大数(字符串)比较

??? int j,i,len=s.size(),len1=s1.size();
??? for(i=0;s[i]=='0';i++);//去掉前导0
??? for(j=0;s1[j]=='0';j++);//去掉前导0
??? if(len-i>len1-j) return 1;
??? else if(len-i<len1-j) return -1;
??? else for(;s[i]==s1[j]&&i<len;i++,j++);
??? if(s[i]>s1[j]) return 1;//s>s1
??? if(s[i]<s1[j]) return -1;//s<s1
??? return 0;
}
string s[501];
int main()
{
??? string a,b;
??? s[1]="1"; s[2]="2";
??? for(int i=3;i<=500;i++){
??????? s[i]=add(s[i-1],s[i-2]);
??????? //if(i<10) cout<<s[i]<<endl;
??? }
??? while(cin>>a>>b){
??????? if(a=="0"&&b=="0") break;
??????? //cout<<compareto(a,b)<<endl;
??????? int sum=0;
??????? for(int i=1;i<=500;i++){
??????????? if(compareto(s[i],a)>=0&&compareto(s[i],b)<=0){
??????????????? sum++;
??????????? }
??????? }
??????? cout<<sum<<endl;
??? }

??? return 0;
}

java代码：

import java.math.BigInteger; import java.util.Scanner; public class Main { ?? ?public static void main(String[] args) { ?? ??? ?BigInteger a,b; ?? ??? ?BigInteger s[] = new BigInteger[1501]; ?? ??? ?s[0]=BigInteger.ZERO; ?? ??? ?s[1]=BigInteger.ONE; ?? ??? ?s[2]=BigInteger.valueOf(2); ?? ??? ?for(int i=3;i<=1500;i++){ ?? ??? ??? ?s[i]=s[i-1].add(s[i-2]); ?? ??? ?} ?? ??? ?//System.out.println(s[1500]); ?? ??? ?Scanner sc = new Scanner(System.in); ?? ??? ?while(sc.hasNext()){ ?? ??? ??? ?a=sc.nextBigInteger(); ?? ??? ??? ?b=sc.nextBigInteger(); ?? ??? ??? ?if(a.add(b).compareTo(BigInteger.ZERO)==0) break; ?? ??? ??? ?int cnt=0; ?? ??? ??? ?//提高程序的鲁棒性 ?? ??? ??? ?if(a.compareTo(b)>0){ ?? ??? ??? ??? ?BigInteger tmp=a; ?? ??? ??? ??? ?a=b; ?? ??? ??? ??? ?b=tmp; ?? ??? ??? ?} ?? ??? ??? ?for(int i=1;i<=1500;i++){ ?? ??? ??? ??? ?if(s[i].compareTo(a)>=0&&s[i].compareTo(b)<=0){ ?? ??? ??? ??? ??? ?cnt++; ?? ??? ??? ??? ?} ?? ??? ??? ?} ?? ??? ??? ?System.out.println(cnt); ?? ??? ?} ?? ?} }