本文主要是介绍HDU 1316(大数比较+二分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大数比较+二分：
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<iostream>
using namespace std;
#define M 105
char a[M+2],b[M+2];
char book[1000][M+2];
int cmp(char *s1,char *s2)
{
for(int i=0;i<=M;++i)
{
if(i==M)
{
return s1[i]-s2[i];//如果到最后一位相等,要保证返回0;
}
if(s1[i]==s2[i])
continue;
else
{
return s1[i]-s2[i];
}
}
}
//一下两个函数是二分查找上下界的位置.
//查找原则是下界数组坐标减一,上界数组坐标加一
int find1(int i,char *x)
{
int low=0,high=i,mid; //定义左右指针,中间指针
while(low<=high)
{
mid=(low+high)/2;
int t=cmp(book[mid],x);
if(t>0)
high=mid-1;//改变左右界,并偏移(为了使左右指针交错)
else if(t==0)
return mid-1;
else
low=mid+1;
}
return high; //跳出时, high 变量在左边
}
int find2(int i,char *x)
{
int low=0,high=i,mid;
while(low<=high)
{
mid=(low+high)/2;
int t=cmp(book[mid],x);
if(t>0)
high=mid-1;
else if(t==0)
return mid+1;
else
low=mid+1;
}
return low;
}
int main()
{
int p=M,i=2; //p用于标记最高位的位置
book[0][M]=1,book[1][M]=2;
while(book[i-1][M-100]<=1)
{
for(int j=M;j>=p;--j)
book[i][j]=book[i-1][j]+book[i-2][j];
for(int j=M;j>=p;--j)
{
int c=book[i][j]/10;
book[i][j]%=10;
book[i][j-1]+=c;
} //即时进位操作
if(book[i][p-1]>0) //判断是否最高位发生变化
--p;//如果当前的最高位的下一位不为零,则指针减一
++i;
}
while(scanf("%s%s",a,b),a[0]-'0'||b[0]-'0')
{
int cnt=0,p;
int last1=strlen(a)-1;
int last2=strlen(b)-1;
for(int j=last1,k=M;j>=0;--j,--k)
{
a[k]=a[j]-'0';
a[j]=0; //消除干扰比较的因素,置零操作
}
for(int j=last2,k=M;j>=0;--j,--k)
{
b[k]=b[j]-'0';
b[j]=0;
}
int l=find1(i-1,a);
int r=find2(i-1,b);
printf("%d\n",r-l-1);
memset(a,0,sizeof(a)); //清除上一次操作的数据遗留
memset(b,0,sizeof(b));
}
return 0;
}
java大数：
import java.math.BigInteger;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
int sum = 0;
BigInteger []b = new BigInteger[1005];
b[1] = BigInteger.valueOf(1);
b[2] = BigInteger.valueOf(2);
for(int i=3;i<1005;i++){
b[i] = b[i-1].add(b[i-2]);
}
Scanner s = new Scanner(System.in);
while(s.hasNextBigInteger()){
BigInteger n = s.nextBigInteger();
BigInteger m = s.nextBigInteger();
if(n.compareTo(BigInteger.ZERO)==0&&m.compareTo(BigInteger.ZERO)==0) return;
if(n.compareTo(m)>0){
BigInteger tt = n;
n = m;
m = tt;
}
for(int i=1;i<1005;i++){
if(b[i].compareTo(n)>=0&&b[i].compareTo(m)<=0){
sum++;
}
}
System.out.println(sum);
sum = 0;
}
}
}
这篇关于HDU 1316(大数比较+二分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
