相关疑难解决方法(0)

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

我对Fibonacci数的迭代算法很感兴趣,所以我在wiki上找到了公式...它看起来很直接,所以我在Python中尝试了...它没有问题编译和公式看起来正确...不是确定为什么它给出了错误的输出......我没有实现它吗？

def fib (n): 
    if( n == 0):
        return 0
    else:
        x = 0
        y = 1
        for i in range(1,n):
            z = (x + y)
            x = y
            y = z
            return y

for i in range(10):
    print (fib(i))

产量

0
无
1
1
1
1
1
1

问题:

Fibonacci序列中的每个新术语都是通过添加前两个术语生成的.

从1和2开始,前10个术语将是:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

通过考虑Fibonacci序列中的值不超过四百万的项,找到偶数项的总和.

我的代码:(工作正常)

public static void main(String[] agrs){
    int prevFirst=0;
    int prevSecond=1;
    int bound=4_000_000;
    int evenSum=0;

    boolean exceed=false; //when fib numbers > bound
    while(!exceed){
        int newFib=prevFirst + prevSecond;
        prevFirst = prevSecond;
        prevSecond = newFib;

        if(newFib > bound){
            exceed=true;
            break;
        }

        if(newFib % 2 == 0){
            evenSum += newFib;
        }
    }

    System.out.println(evenSum);

}

我正在寻找一个更有效的算法来解决这个问题.任何提示？

# Uses python3
# Given two integers n and m, output Fn mod m (that is, the remainder of Fn when divided by m
def Huge_Fib(n,m):

    if n == 0 : return 0
    elif n == 1: return 1
    else:
        a,b = 0,1
        for i in range(1,n):
            a, b = b, (a+b) % m
        print(b);

n,m = map(int, input().split());   
Huge_Fib(n,m);

该代码运行得很好。但是，当我运行 n = 99999999999999999，m = 2 的案例时，需要花费很多时间。您有更好的解决方案吗？

我用Python编写了斐波纳契系列.无法弄清楚为什么第二个程序给出了错误答案,而第一个程序看起来是正确的.

以下程序给出正确的答案

def fib(n):
  a,b=0,1
  while b<n:
    print b
    a,b=b,a+b

fib(4)
1
1
2
3

以下程序给出了错误答案:

def fib(n):
  a = 0
  b = 1
  while b<n:
    print b
    a = b
    b = a+b

fib(4)

1
2

# Uses python3

# Compute the Last Digit of a Large Fibonacci Number
def Fib_Last_Digit(n):

    if n == 0 : return 0
    elif n == 1: return 1
    else:

        a,b = 0,1
        for i in range(1,n):
            c = a + b;
            a = b;
            b = c;
        # Calculate the last digit of the final number 
        lastdigit = int(repr(c)[-1]);
        print(lastdigit);

n = int(input(""));
Fib_Last_Digit(n);

这段代码运行得很好。但是，我想修改算法以节省更多时间和内存。顺便说一句，输入和输出应该与之前的版本保持一致。