首页 > 代码库 > poj 2413 How many Fibs?
poj 2413 How many Fibs?
How many Fibs?
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10748 | Accepted: 3982 |
Description
Recall the definition of the Fibonacci numbers:
Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b].
f1 := 1 f2 := 2 fn := fn-1 + fn-2 (n>=3)
Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b].
Input
The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a=b=0. Otherwise, a<=b<=10100. The numbers a and b are given with no superfluous leading zeros.
Output
For each test case output on a single line the number of Fibonacci numbers fi with a<=fi<=b.
Sample Input
10 100 1234567890 9876543210 0 0
Sample Output
5 4
解题思路:
用一个字符串数组记录位数小于101的所有fibs,然后对于给定的a,b,求出满足条件的个数;
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; char fibs[10005][102]; void add(int n){ int len_a=strlen(fibs[n-1]),len_b=strlen(fibs[n-2]); int p=len_a-1,q=len_b-1; int a[102],left=0; for (int i=0;i<102;i++){ a[i]=left; if (p>=0) a[i]+=fibs[n-1][p--]-'0'; if (q>=0) a[i]+=fibs[n-2][q--]-'0'; left=a[i]/10; a[i]%=10; } int i; for (i=101;i>=0;i--){ if (a[i]!=0) break; } int k=0; while (i>=0){ fibs[n][k++]=a[i--]+'0'; } fibs[n][k]=0; } bool cmp(char *a,char *b){ int len_a=strlen(a),len_b=strlen(b); if (len_a>len_b) return true; if (len_a<len_b) return false; int n=0; while (n<len_a){ if (a[n]-'0'>b[n]-'0') return true; if (a[n]-'0'<b[n]-'0') return false; n++; } return true; } int main(){ strcpy(fibs[0],"1"); strcpy(fibs[1],"2"); int k=1; while (strlen(fibs[k++])<101){ add(k); } char a[102],b[102]; while(scanf("%s %s",a,b),strcmp(a,"0")!=0||strcmp(b,"0")!=0){ int count=0; for (int i=0;i<=k;i++){ if (cmp(fibs[i],a)==false) continue; if (cmp(fibs[i],a)==true && cmp(b,fibs[i])==true) count++; if (cmp(b,fibs[i])==false) break; } cout<<count<<endl; } return 0; }
poj 2413 How many Fibs?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。