首页 > 代码库 > How many Fibs?（高精度）

How many Fibs?（高精度）

2024-07-15 02:13:57   222人阅读

Description

Recall the definition of the Fibonacci numbers: 
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

解题思路：

题目大意是给个区间，问这区间内有多少个斐波那契数。区间给的很大，得用高精度来求。先把斐波那契数求出来，再根据区间进行查找，我求了前两千个斐波那契数，反正是绝对够了。只有查找我发现自己十分不机智了。竟然自己辛辛苦苦写了个比较函数，而且还是非常龊那种。完全可以把斐波那契数存入字符串中，由于字符串的比较函数是按照字典序来比较的，正符合我的需求。用字符串的比较函数就方便多了。哎！太TMD不机智了！！！！不过不想再写一次了，反正能AC就行，就不再优化了。。。。我的代码就像老太婆的裹脚布，又臭又长，有木有！有木有！

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 500;
int fib[2000][maxn];
void Fibs()
{
    memset(fib, 0, sizeof(fib));
    fib[1][0] = 1;
    fib[2][0] = 2;
    for(int i = 3; i < 1500; i++)
    {
        int ans = 0;
        for(int j = 0; j < maxn; j++)
        {
            fib[i][j] = fib[i - 1][j] + fib[i - 2][j] + ans;
            ans = fib[i][j] / 10;
            fib[i][j] %= 10;
        }
    }
}
int main()
{
    char str_1[maxn], str_2[maxn];
    int num_1[maxn], num_2[maxn], length_1, length_2;
    Fibs();
    while(scanf("%s%s", str_1, str_2))
    {
        int begin, end, len_1, len_2;
        if(str_1[0] == '0' && str_2[0] == '0')
            break;
        length_1 = strlen(str_1);
        length_2 = strlen(str_2);
        for(int i = 0; i < length_1; i++)
            num_1[i] = str_1[length_1 - i - 1] - '0';
        for(int i = 0; i < length_2; i++)
            num_2[i] = str_2[length_2 - i - 1] - '0';
        for(int i = 1; i < 1500; i++)
        {
            bool isFind = false;
            for(int j = maxn - 1; j >= 0; j--)
            {
                if(fib[i][j])
                {
                    len_1 = j + 1;
                    break;
                }
            }
            if(len_1 < length_1)
                    continue;
            if(len_1 > length_1)
            {
                begin = i;
                break;
            }
            for(int j = len_1 - 1; j >= 0; j--)
            {
                if(j == 0 && fib[i][j] == num_1[j])
                    isFind = true;
                if(fib[i][j] == num_1[j])
                    continue;
                if(fib[i][j] > num_1[j])
                    isFind = true;
                break;
            }
            if(isFind)
            {
                begin = i;
                break;
            }
        }
        for(int i = 1499; i > 0; i--)
        {
            bool isFind = false;
            for(int j = maxn - 1; j >= 0; j--)
            {
                if(fib[i][j])
                {
                    len_2 = j + 1;
                    break;
                }
            }
            if(len_2 > length_2)
                    continue;
            if(len_2 < length_2)
            {
                end = i;
                break;
            }
            for(int j = len_2 - 1; j >= 0; j--)
            {
                if(j == 0 && fib[i][j] == num_2[j])
                    isFind = true;
                if(fib[i][j] == num_2[j])
                    continue;
                if(fib[i][j] < num_2[j])
                    isFind = true;
                break;
            }
            if(isFind)
            {
                end = i;
                break;
            }
        }
        printf("%d\n",end - begin + 1);
    }
    return 0;
}



联系
我们