当前位置:编程学习 > C/C++ >>

uva 10183 - How Many Fibs?(斐波那契数)

题目大意:给出a和b,求出a~b中有几个数时斐波那契数。
 
解题思路:模拟斐波那契数,找到临界的标号,相减的到答案。(大数,直接摘模板了,会比较长)
 
 
#include <stdio.h>  
#include <string.h>  
const int N = 105;  
  
struct bign {  
    int len, 易做图;  
    int s[N];  
  
    bign() {  
        this -> len = 1;  
        this -> 易做图 = 0;  
        memset(s, 0, sizeof(s));  
    }  
  
    bign operator = (const char *number) {  
        int begin = 0;  
        len = 0;  
        易做图 = 1;  
        if (number[begin] == '-') {  
            易做图 = -1;  
            begin++;  
        }  
        else if (number[begin] == '+')  
            begin++;  
  
        for (int j = begin; number[j]; j++)  
            s[len++] = number[j] - '0';  
    }  
  
    bign operator = (int number) {  
        char string[N];  
        sprintf(string, "%d", number);  
        *this = string;  
        return *this;  
    }  
  
    bign (int number) {*this = number;}  
    bign (const char* number) {*this = number;}  
  
    bool operator < (const bign& b) const {  
        if (len != b.len)  
            return len < b.len;  
        for (int i = 0; i < len; i++)  
            if (s[i] != b.s[i])  
                return s[i] < b.s[i];  
        return false;  
    }  
    bool operator > (const bign& b) const { return b < *this; }  
    bool operator <= (const bign& b) const { return !(b < *this); }  
    bool operator >= (const bign& b) const { return !(*this < b); }  
    bool operator != (const bign& b) const { return b < *this || *this < b;}  
    bool operator == (const bign& b) const { return !(b != *this); }  
  
    bign change(bign cur) {  
        bign now;  
        now = cur;  
        for (int i = 0; i < cur.len; i++)  
            now.s[i] = cur.s[cur.len - i - 1];  
        return now;  
    }  
  
    bign operator + (const bign &cur){    
        bign sum, a, b;    
        sum.len = 0;  
        a = a.change(*this);  
        b = b.change(cur);  
  
        for (int i = 0, g = 0; g || i < a.len || i < b.len; i++){    
            int x = g;    
            if (i < a.len) x += a.s[i];    
            if (i < b.len) x += b.s[i];    
            sum.s[sum.len++] = x % 10;    
            g = x / 10;    
        }    
        return sum.change(sum);    
    }   
};  
  
int l, r;  
char a[N], b[N];  
bign f, s;  
bign begin, end;  
  
void solve() {  
    int flag = 1;  
    for (int i = 1; ; i++) {  
        if (i % 2) {  
            s = f + s;  
            if (s >= begin && flag) {  
                l = i;  
                flag = 0;  
            }  
            if (s > end) {  
                r = i;  
                return ;  
            }  
        } else {  
            f = f + s;    
            if (f >= begin && flag) {  
                l = i;  
                flag = 0;  
            }  
            if (f > end) {  
                r = i;  
                return ;  
            }  
        }  
    }  
}  
int main () {  
    while (scanf("%s%s", a, b) == 2) {  
        if (a[0] == '0' && b[0] == '0') break;  
        begin = a, end = b;  
        f = 1, s = 0;  
        solve();  
        printf("%d\n", r - l);  
    }  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,