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

ゞ浴缸里的玫瑰 2022-05-14 13:52 77阅读 0赞

[题目连接：uva 10183 - How Many Fibs?][uva 10183 - How Many Fibs]

题目大意：给出a和b，求出a~b中有几个数时斐波那契数。

解题思路：模拟斐波那契数，找到临界的标号，相减的到答案。(大数，直接摘模板了，会比较长）

#include <stdio.h>
    #include <string.h>
    const int N = 105;
    
    struct bign {
    	int len, sex;
    	int s[N];
    
    	bign() {
    		this -> len = 1;
    		this -> sex = 0;
    		memset(s, 0, sizeof(s));
    	}
    
    	bign operator = (const char *number) {
    		int begin = 0;
    		len = 0;
    		sex = 1;
    		if (number[begin] == '-') {
    			sex = -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;
    }

[uva 10183 - How Many Fibs]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1124