超过时间限制 - 斐波那契

Question

列表中有 'n' 个斐波那契数列，其中 'n' 由用户提供。阅读后，mod通过将 mod 与 10 相结合来确定数字（例如，如果我阅读 2，则应将其 mod 确定为 2%10，即 2，如果是 13，则它应该是 13%10 即 3）。然后，从该列表中删除每个奇数位置的数字（1、3、5 ...定位的项目），直到只剩下一个项目。

我已经解决了这个问题。但是，问题是我遇到了 TLE 错误。我试过缩短代码，但仍然可以在一秒钟内完成。

#include <stdio.h>
#include <math.h>

int fib(int n)
{
    if(n == 0 || n == 1)
    {
        return n;
    }
    else
    {
        return(fib(n-1)+fib(n-2));
    }
}

int main()
{
    int ip, d, i=0, j, n;
    scanf("%d", &n);
    for(j=0; j<n; j++)
    {
        scanf("%d", &ip);
        if(ip == 1)
        {
            printf("0\n");
        }
        else if(ip == 2)
        {
            printf("1\n");
        }
        else if(ip == 4)
        {
            printf("2\n");
        }
        else
        {
            while(1)
            {
                d = pow(2, i++);
                if(d >= ip)
                {
                    d = pow(2, i-2);
                    break;
                }
            }
            printf("%d", fib(d-1)%10);
        }
        i = 0;
    }
}

Answer 1

优化通常是分步进行的。

您从显而易见的解决方案开始。

iterate_fibs_mod10; remove_odds(n);

然后你意识到你真的只需要对一个元素进行一次昂贵的模数。

nth_fib(remove_odds(n))%10;

然后您意识到如果您可以确定性地找到应该保留的节点，则不需要删除这些节点。

nth_fib(as_if_remove_odds(n))%10;

然后你算出这个元素对应一个数学函数

nth_fib((int)log2(n))%10;

然后你意识到这对应于二进制表示中的最高有效位。

nth_fib(msb_only(n))%10; //compiler builtins exist for most significant bit

然后你注意到，由于你只做最后一位，序列必须在 100 次迭代内重复（恰好是 60），所以你可以进行查找 table.

unsigned char fib_1s[60] = {...};
fib_1s[msb_only(n)%60];

超过时间限制 - 斐波那契

Time limit exceeded - Fibonacci

c

linked-list

fibonacci