C语言 超过时限 - 斐波那契

Question

列表中有"n"斐波那契数，其中"n"由用户提供。阅读后，通过用 10 的 mod 修改数字(例如。如果我读 2，那么它应该修改为 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("0n");
}
else if(ip == 2)
{
printf("1n");
}
else if(ip == 4)
{
printf("2n");
}
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 次(，所以你可以做一个查找表。

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