HDU (1893 Sibonacci Numbers)

spoiler posted @ 2011年5月11日 02:45 in Fibonacci 的相关规律题及计算 , 2483 阅读

题目大意:

f(1)=1
f(2)=1
f(n)=f(n-1)+f(n-2) (n>=3)

Now Sempr found another Numbers, he named it "Sibonacci Numbers", the definition is below:
f(x)=0 (x<0)
f(x)=1 (0<=x<1)
f(x)=f(x-1)+f(x-3.14) (x>=1)

题目分析:

这个题目是黑书上的弱化版,黑书有对这一系列问题进行讨论,然后这里,你只需要把数放大100倍,这样只要递归求解就可以了,注意要用字符串里出来输入的数据哦,因为我们最多只需要小数点后的2位,后面都舍去‘

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long s[100100];
int init(){
    int i;
    for(i=0;i<=100;i++)
        s[i]=1;
    for(i=100;i<=100100;i++){
        if(i<314)
            s[i]=s[i-100]%1000000007;
        else
            s[i]=(s[i-100]+s[i-314])%1000000007;
    }
    return 0;
}
int main(){
    int cas,n,i;
    char ch[20];
    init();
    scanf("%d",&cas);
    while(cas--){
        scanf("%s",ch);
        if(ch[0]=='-'){
            printf("0\n");
            continue;    
        }
        i=0;
        n=0;
        int len=strlen(ch);
        while(ch[i]!='.'&&i<len)
            n=n*10+ch[i++]-'0';
        if(i+1<len)
            n=n*10+ch[i+1]-'0';
        else
            n=n*10;
        if(i+2<len)
            n=n*10+ch[i+2]-'0';
        else
            n=n*10;
        printf("%lld\n",s[n]);
    }
    return 0;
}

 

Avatar_small
leo_h 说:
2012年8月29日 16:18

黑书是什么书?

Avatar_small
leo_h 说:
2012年9月06日 15:09

我找到黑书了,可是哪里有讲?同类的题目,并不是用乘以100这个方法解决的,为什么可以乘以100,有解释么?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter