UVa 10183 How Many Fibs? (统计斐波那契数个数&高精度)

10183 - How Many Fibs?

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1124

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 Specification

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 Specification

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

先打表，再从头开始枚举判断即可。

完整代码：

/*0.016s*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 105;///注意此值的设置要留意中间结果  

char numstr[maxn], numstr2[maxn]; ///输入输出接口  

struct bign
{
    int len, s[maxn];  

    bign()
    {
        memset(s, 0, sizeof(s));
        len = 1;
    }  

    bign(int num)
    {
        *this = num;
    }  

    bign(const char* num)
    {
        *this = num;
    }  

    bign operator = (const int num)
    {
        char s[maxn];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }  

    bign operator = (const char* num)
    {
        len = strlen(num);
        for (int i = 0; i < len; i++) s[i] = num[len - i - 1] & 15;
        return *this;
    }  

    ///输出
    const char* str() const
    {
        if (len)
        {
            for (int i = 0; i < len; i++)
                numstr[i] = '0' + s[len - i - 1];
            numstr[len] = '\0';
        }
        else strcpy(numstr, "0");
        return numstr;
    }  

    ///去前导零
    void clean()
    {
        while (len > 1 && !s[len - 1]) len--;
    }  

    ///加
    bign operator + (const bign& b) const
    {
        bign c;
        c.len = 0;
        for (int i = 0, g = 0; g || i < max(len, b.len); i++)
        {
            int x = g;
            if (i < len) x += s[i];
            if (i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }  

    ///减
    bign operator - (const bign& b) const
    {
        bign c;
        c.len = 0;
        for (int i = 0, g = 0; i < len; i++)
        {
            int x = s[i] - g;
            if (i < b.len) x -= b.s[i];
            if (x >= 0) g = 0;
            else
            {
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }  

    ///乘
    bign operator * (const bign& b) const
    {
        bign c;
        c.len = len + b.len;
        for (int i = 0; i < len; i++)
            for (int j = 0; j < b.len; j++)
                c.s[i + j] += s[i] * b.s[j];
        for (int i = 0; i < c.len - 1; i++)
        {
            c.s[i + 1] += c.s[i] / 10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }  

    ///除
    bign operator / (const bign &b) const
    {
        bign ret, cur = 0;
        ret.len = len;
        for (int i = len - 1; i >= 0; i--)
        {
            cur = cur * 10;
            cur.s[0] = s[i];
            while (cur >= b)
            {
                cur -= b;
                ret.s[i]++;
            }
        }
        ret.clean();
        return ret;
    }  

    ///模、余
    bign operator % (const bign &b) const
    {
        bign c = *this / b;
        return *this - c * b;
    }  

    bool operator < (const bign& b) const
    {
        if (len != b.len) return len < b.len;
        for (int i = len - 1; i >= 0; 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) && !(*this < b);
    }  

    bign operator += (const bign &a)
    {
        *this = *this + a;
        return *this;
    }  

    bign operator -= (const bign &a)
    {
        *this = *this - a;
        return *this;
    }  

    bign operator *= (const bign &a)
    {
        *this = *this * a;
        return *this;
    }  

    bign operator /= (const bign &a)
    {
        *this = *this / a;
        return *this;
    }  

    bign operator %= (const bign &a)
    {
        *this = *this % a;
        return *this;
    }
};  

bign f[500] = {1, 1};  

int main()
{
    bign a, b;
    int i, j;
    for (i = 2; i < 500; ++i)
        f[i] = f[i - 1] + f[i - 2];
    while (scanf("%s%s", numstr, numstr2), a = numstr, b = numstr2, b != 0)
    {
        i = 1;
        while (f[i++] < a)
            ;
        --i;
        j = i;
        while (f[j++] <= b)
            ;
        printf("%d\n", j - i - 1);
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

/*0.372s*/

import java.io.*;
import java.util.*;
import java.math.*;  

public class Main {
    static final int maxn = 500;
    static Scanner cin = new Scanner(new BufferedInputStream(System.in));  

    public static void main(String[] args) {
        BigInteger[] f = new BigInteger[maxn];
        f[1] = BigInteger.ONE;
        f[2] = new BigInteger("2");
        for (int i = 3; i < maxn; ++i)
            f[i] = f[i - 1].add(f[i - 2]);
        while (true) {
            BigInteger a = cin.nextBigInteger(), b = cin.nextBigInteger();
            if (b.compareTo(BigInteger.ZERO) == 0)
                break;
            int i = 1;
            while (f[i++].compareTo(a) < 0)
                ;
            --i;
            int j = i;
            while (f[j++].compareTo(b) < 1)
                ;
            System.out.println(j - i - 1);
        }
    }
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索斐波那契数列
， return
， this
， const
， numbers
， 斐波那契
， bool
， const auto&amp;amp;
， operator
斐波那契数
how many fibs pascal、function fibs、10183学校代码、乐高10183、gb10183，以便于您获取更多的相关知识。

时间： 2024-10-02 14:02:50

UVa 10183 How Many Fibs? (统计斐波那契数个数&amp;高精度)的相关文章

求助-斐波那契数运算时间？

问题描述 斐波那契数运算时间? WINDOWS 64位系统下.用递归运算,算斐波那契数列.第一第二项分别是0,1.算2013大概需要多久. 解决方案 楼主 你自己把算法实现 然后测试一下就好 每台机器的时间不一样的

求大神指教逻辑式程序是什么，能具体给出个例子吗？比方说写出求斐波那契数的逻辑式程序

问题描述 求大神指教逻辑式程序是什么,能具体给出个例子吗?比方说写出求斐波那契数的逻辑式程序 求大神指教逻辑式程序是什么,能具体给出个例子吗?比方说写出求斐波那契数的逻辑式程序 解决方案 斐波那契数列和阶乘的实现. fib(1,1). fib(2,1). fib(N,Ret) :- N > 2, N1 is N -1, N2 is N -2, fib(N1,Prv1), fib(N2,Prv2), Ret is Prv2 + Prv1. factorial(0,1). factorial(1,1

斐波那契数（C/C++，Scheme）

一.背景 斐波那契数的定义: f0=0 f1=1 fi=fi−1+fi−2(i>1) 二.代码 C++语言版 int fib_iter(int a, int b, int count) { if (count == 0) return b; else return fib_iter(a + b, a, count - 1); } int fib(int n) { return fib_iter(1, 0, n); } Common Lisp语言版 (defun fib (n) (fib-iter

C++求斐波那契数的实例代码_C 语言

题目内容:斐波那契数定义为:f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)(n>1且n为整数) 如果写出菲氏数列,则应该是: 0 1 1 2 3 5 8 13 21 34 -- 如果求其第6项,则应为8. 求第n项菲氏数. 输入描述:输入数据含有不多于50个的正整数n(0<=n<=46). 输出描述:对于每个n,计算其第n项菲氏数,每个结果应单独占一行. 题目分析:先把第0项到第46项的斐波那契数求出来,放在一个数组中,然后,直接查表即可,这样就不会超时. 参考代码:

UVa 10236 The Fibonacci Primes：斐波那契素数

10236 - The Fibonacci Primes Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1177 注意此题的描述和维基百科上Fibonacci Prime的描述不同. 上面加着重符的文字说明:可以用类似素数筛的方式筛出Fibonacci Pr

Problem 1049 - 斐波那契数

Description        斐波那契数列是如下的一个数列,0,1,1,2,3,5--,其通项公式为F(n)=F(n-1)+F(n-2),(n>=2) ,其中F(0)=0,F(1)=1,你的任务很简单,判定斐波契数列的第K项是否为偶数,如果是输出YES,否则输出NO Input 第一行,T,表示有T个测试样例. 接下来T行,每行一个数据K(0<=K<=10^10000),表示要判定的是哪一项. Output 如果第K项是偶数,输出YES,否则输出NO. Sample Input

使用模板元编程快速的得到斐波那契数。。

这是一种将运行时消耗转移到编译器消耗的方法,是c++模板的一种应用. 当你的程序运行时效率需要特别高的时候,可以考虑这样的方法. 模板实例化的时候需要常量: #include <iostream> using namespace std; template < unsigned N > struct Fib { enum { Val = Fib<N-1>::Val + Fib<N-2>::Val //递归.. }; }; template<> /

UVa 10229 Modular Fibonacci：矩阵快速幂求斐波那契

10229 - Modular Fibonacci Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1170 The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are defin

hdu 4549 M斐波那契数列

click here ~~ Problem Description M斐波那契数列F[n]是一种整数数列,它的定义如下: F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 ) 现在给出a, b, n,你能求出F[n]的值吗? Input 输入包含多组测试数据: 每组数据占一行,包含3个整数a, b, n( 0 <= a, b, n <= 10^9 ) Output 对每组测试数据请输出一个整数F[n],由于F[n]可能很大,你只需输出F[n