首页 > 代码库 > 百度之星题--斐波拉契数列

百度之星题--斐波拉契数列

2024-07-02 10:04:01   226人阅读

题目：

du熊学斐波那契I

Time Limit : 2000/1000ms (C/Other) Memory Limit : 65535/32768K (C/Other)

本次组委会推荐使用C、C++

Problem Description

du熊对数学一直都非常感兴趣。最近在学习斐波那契数列的它，向你展示了一个数字串，它称之为“斐波那契”串：

11235813471123581347112358........

聪明的你当然一眼就看出了这个串是这么构造的：1.先写下两位在0~9范围内的数字a, b，构成串ab；2.取串最后的两位数字相加，将和写在串的最后面。

上面du熊向你展示的串就是取a = b = 1构造出来的串。

显然，步骤1之后不停地进行步骤2，数字串可以无限扩展。现在，du熊希望知道串的第n位是什么数字。

Input

输入数据的第一行为一个整数T（1 <= T <= 1000）, 表示有T组测试数据；

每组测试数据为三个正整数a, b, n（0 <= a, b < 10, 0 < n <= 10^9）。

Output

对于每组测试数据，输出一行“Case #c: ans”（不包含引号）

c是测试数据的组数，从1开始。

Sample Input

3

1 1 2

1 1 8

1 4 8

Sample Output

Case #1: 1

Case #2: 3

Case #3: 9

Hint

对于第一、二组数据，串为112358134711235......

对于第三组数据，串为14591459145914......

我随笔写了点代码，因为我很少去训练这样的竞赛题，欢迎指点。

    register unsigned char ii = 1;
    register unsigned char jj = 4;
    register unsigned int nn = 6;
    register const unsigned char nine = 9;
    register const unsigned char ten = 10;
    register const unsigned char four = 4;
    register const unsigned char one = 1;
    register unsigned char *pi = &ii;
    register unsigned char *pj = &jj;
    register unsigned char *pv = &jj;


    LxTimer tt;
    tt.start(); 

    if (! --nn)
    {
        pv = &ii;
    }
    else if (! --nn)
    {
        pv = &jj;
    }
    else

    while(nn)
    {
        *pi += *pj;

        if (*pi> nine)
        {
            if (--nn)
            {
                if (--nn)
                {
                    if (--nn)
                    {
                        *pi -= ten;
                        *pj = *pi + one;
                        *pi += *pj;

                    }
                    else
                    {
                        *pi -= nine;
                        pv = pi;
                        break;
                    }
                }
                else
                {
                    *pi -= ten;
                    pv = pi;
                    break;
                }
            }
            else
            {
                *pv = one;
                break;
            }
        }

       pv = pi;
       pi = pj;
       pj = pv;

        --nn;
    }

    double cc = tt.stop();
    cc *= 1000;

    std::cout <<cc<<std::endl;
    std::cout <<(int)*pv<<std::endl;

复杂度为O(n),n为一百万时运行时间也基本上几ms（VC2008、win7,2G）。


联系
我们