注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1316  

2012-07-03 17:03:39|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1316
大数。。
求给出的两个数间有多少个斐波数,比较麻烦,打的时候需要很耐心
先列出从1到10^100的所有斐波数,然后用二分查找找到输入的两个数所在的位置即可
这里用到了大数相加,大数比较大小,二分查找,所以比较麻烦
后来打不下去了,直接膜拜了大神:
http://www.cnblogs.com/Lyush/archive/2011/04/01/2002327.html
AC Code:
#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;
}
  评论这张
 
阅读(245)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018