相关疑难解决方法(0)

是否有任何算法来计算子线性时间内的第n个斐波纳契数？

在Fibonacci系列中找到第n项f(n)= f(n-1)+ f(n-2)可以通过记忆在O(n)时间内求解.

一种更有效的方法是使用除法和征服来找到矩阵[[1,1],[1,0]]的n次幂,以便在log n时间内求解Fibonacci.

是否有类似的方法可以遵循f(n)= f(n-1)+ f(nx)+ f(n-x + 1)[x是一些常数].

只是存储前面的x个元素,这可以在O(n)时间内解决.

有没有更好的方法来解决这种递归.

下面的代码能够使用数据类型确定直到70点的正确顺序unsigned long long.我知道序列会变大,因此我修改了10,000个结果.我想使用最佳数据类型确定10,000的第n个术语,或者改进算法来计算第n个术语.

#define MOD %10000

unsigned long long calc(long nth) {
    return (pow( 1 + sqrt(5), nth ) - pow( 1 - sqrt(5), nth )) / (pow(2.0, nth)*(sqrt(5)));
}

int main() {
    long t, nth;
    for (std::cin>>t;  t-- && std::cin>>nth; ) {
        std::cout<<calc(nth-2)MOD<<" "<<calc(nth-1)MOD<<" "<<calc(nth)MOD<<std::endl;
    }   
    return 0;
}